Skip to content

Instantly share code, notes, and snippets.

@grrinchas grrinchas/NFA.java
Created Feb 7, 2017

Embed
What would you like to do?
import java.util.*;
/**
* Nondeterministic finite automaton for recognising language of {aa, aab}*{b}
*
* @see http://www.dennis-grinch.co.uk/tutorial/nfa
* @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;
default:
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<>();
currStates.add(States.Q0);
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)
nextStates.addAll(cState.transition(ch));
return nextStates;
}
}
@kasare

This comment has been minimized.

Copy link

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.