Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
* Deterministic finite automata for recognising language of strings with
* following conditions:
*
* 1. It must contain only :, ), (, and _ characters.
* 2. :has to be followed by ) or (.
* 3. Has to have at least one smiley :) or sad :( face.
* 4. If string has more than one face, then all of them have to be separated by at least one _ character.
* 5. Each string can start and end with zero or more _ characters.
*
* @see http://www.dennis-grinch.co.uk/tutorial/dfa-in-java
* @author Dennis Grinch
*/
public class DFA {
/**
* Enum representing set of states Q. Each state has boolean
* variable "accept" which indicates if it is an accept
* state or not. All states with "true" accept value
* represents subset of accept states F.
* <p>
* Every state has an instance variable corresponding to the
* symbol in the subset of alphabet Σ. Thus "eyes" stands for :,
* smile - for ), sad - for (, and space for _.
*
*/
private enum States {
Q0(false), Q1(false), Q2(true), Q3(true), Q4(false);
// transition table
static {
Q0.eyes = Q1; Q0.space = Q0;
Q1.smile = Q2; Q1.sad = Q2;
Q2.space = Q3;
Q3.eyes = Q1; Q3.space = Q3;
}
States eyes;
States smile;
States sad;
States space;
final boolean accept;
// Constructor for sate. Every state is either accepting or not.
States(boolean accept) {this.accept = accept;}
/**
* Represents transition function δ : Q × Σ → Q.
*
* @param ch is a symbol from alphabet Σ (Unicode)
* @return state from codomain Q
*
*/
States transition(char ch) {
switch (ch) {
case ':':
return this.eyes == null? Q4 : this.eyes;
case ')':
return this.smile == null? Q4: this.smile;
case '(':
return this.sad == null? Q4: this.sad;
case '_':
return this.space == null? Q4: this.space;
default:
return Q4;
}
}
}
/**
* Checks if DFA accepts supplied string.
*
* @param string to check
* @return true if it does accept, false otherwise
*/
public boolean accept(String string) {
States state = States.Q0;
for (int i = 0; i < string.length(); i++) {
state = state.transition(string.charAt(i));
}
return state.accept;
}
}
@ernestoMM94

This comment has been minimized.

Copy link

@ernestoMM94 ernestoMM94 commented Feb 20, 2020

Hello I Implanted a similar DFA to a program am working on but am curious nothing seems to be showing when I run the program. Was wondering if its accepting the whole program?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.