Skip to content

Instantly share code, notes, and snippets.

@grrinchas grrinchas/DFA.java
Last active Feb 7, 2017

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;
}
}
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.