import java.util.*; | |
/** | |
* Nondeterministic finite automaton (ε-NFA) for recognising language of (ab ∪ a)*. | |
* | |
* @see http://www.dennis-grinch.co.uk/tutorial/enfa | |
* @author Dennis Grinch | |
*/ | |
public class eNFA { | |
/** | |
* Enum representing set of states Q. Each state has boolean instance variable | |
* "accept" which indicates if it is an accept state or not. All states with | |
* "true" accept value represents subset of accept states F. | |
*/ | |
private enum States { | |
Q0(true), Q1(false), Q2(false), Q3(false), Q4(false), Q5(true), Q6(false), Q7(true); | |
final boolean accept; | |
Set<States> a; | |
Set<States> b; | |
Set<States> epsilon; | |
// transition table | |
static { | |
Q0.a = Collections.EMPTY_SET; | |
Q0.b = Collections.EMPTY_SET; | |
Q0.epsilon = new HashSet<>(Arrays.asList(Q1)); | |
Q1.a = Collections.EMPTY_SET; | |
Q1.b = Collections.EMPTY_SET; | |
Q1.epsilon = new HashSet<>(Arrays.asList(Q2, Q6)); | |
Q2.a = new HashSet<>(Arrays.asList(Q3)); | |
Q2.b = Collections.EMPTY_SET; | |
Q2.epsilon = Collections.EMPTY_SET; | |
Q3.a = Collections.EMPTY_SET; | |
Q3.b = Collections.EMPTY_SET; | |
Q3.epsilon = new HashSet<>(Arrays.asList(Q4)); | |
Q4.a = Collections.EMPTY_SET; | |
Q4.b = new HashSet<>(Arrays.asList(Q5)); | |
Q4.epsilon = Collections.EMPTY_SET; | |
Q5.a = Collections.EMPTY_SET; | |
Q5.b = Collections.EMPTY_SET; | |
Q5.epsilon = new HashSet<>(Arrays.asList(Q1)); | |
Q6.a = new HashSet<>(Arrays.asList(Q7)); | |
Q6.b = Collections.EMPTY_SET; | |
Q6.epsilon = Collections.EMPTY_SET; | |
Q7.a = Collections.EMPTY_SET; | |
Q7.b = Collections.EMPTY_SET; | |
Q7.epsilon = new HashSet<>(Arrays.asList(Q1)); | |
} | |
// Constructor for state. Every state is either accepting or not. | |
States(boolean accept) {this.accept = accept;} | |
/** | |
* Represents transition function δ : Q × Σ ∪ {ε} → P(Q). | |
* | |
* @param ch symbol from alphabet, Σ = {a, b} | |
* @return set of states | |
*/ | |
Set<States> transition(char ch) { | |
switch (ch) { | |
case 'a': | |
return this.a; | |
case 'b': | |
return this.b; | |
default: | |
return Collections.EMPTY_SET; | |
} | |
} | |
/** | |
* Represents ε-closure. | |
* | |
* @return ε-closure of this state. | |
*/ | |
Set<States> eClose() { | |
Set<States> states = new HashSet<>(); | |
states.add(this); | |
for(States e: this.epsilon) | |
states.addAll(e.eClose()); | |
return states; | |
} | |
} | |
/** | |
* Checks if εNFA accept string or not | |
* | |
* @param string to check | |
* @return true if yes, false otherwise | |
*/ | |
public boolean accept(String string) { | |
Set<States> currStates = new HashSet<>(States.Q0.eClose()); | |
for (int i = 0; i < string.length(); i++) | |
currStates = union(currStates, string.charAt(i)); | |
return currStates.stream().anyMatch(s -> s.accept); | |
} | |
// helper function which returns set of next states | |
private Set<States> union(Set<States> currStates, char ch) { | |
Set<States> nextStates = new HashSet<>(); | |
for (States cState : currStates) | |
for(States s: cState.transition(ch)) | |
nextStates.addAll(s.eClose()); | |
return nextStates; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment