Last active
March 5, 2020 05:07
-
-
Save grrinchas/534614339f786c7528a588426f08d4ef to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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
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?