Skip to content

Instantly share code, notes, and snippets.



Created Feb 7, 2017
What would you like to do?
import java.util.*;
* Nondeterministic finite automaton for recognising language of {aa, aab}*{b}
* @see
* @author Dennis Grinch
public class NFA {
* 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(false), Q1(false), Q2(false), Q3(false), Q4(true);
final boolean accept;
Set<States> a;
Set<States> b;
// transition table
static {
Q0.a = new HashSet(Arrays.asList(Q1, Q2));
Q0.b = new HashSet(Arrays.asList(Q4));
Q1.a = new HashSet<>(Arrays.asList(Q0));
Q1.b = Collections.EMPTY_SET;
Q2.a = new HashSet<>(Arrays.asList(Q3));
Q2.b = Collections.EMPTY_SET;
Q3.a = Collections.EMPTY_SET;
Q3.b = new HashSet<>(Arrays.asList(Q0));
Q4.a = Collections.EMPTY_SET;
Q4.b = Collections.EMPTY_SET;
// 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;
return Collections.EMPTY_SET;
* 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<>();
for (int i = 0; i < string.length(); i++)
currStates = union(currStates, string.charAt(i));
return -> 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)
return nextStates;

This comment has been minimized.

Copy link

@kasare kasare commented Jan 5, 2019

how do i run this program in netbeans

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.