/** | |
* 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
This comment has been minimized.
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?