Skip to content

Instantly share code, notes, and snippets.

@grrinchas grrinchas/eNFA.java
Created Feb 10, 2017

Embed
What would you like to do?
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
You can’t perform that action at this time.