Skip to content

Instantly share code, notes, and snippets.

@grrinchas
Created February 7, 2017 12:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save grrinchas/7c7fc7de3863ca67debd156dd09b7bea to your computer and use it in GitHub Desktop.
Save grrinchas/7c7fc7de3863ca67debd156dd09b7bea to your computer and use it in GitHub Desktop.
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
Copy link

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