Created
February 7, 2017 12:01
-
-
Save grrinchas/7c7fc7de3863ca67debd156dd09b7bea to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
how do i run this program in netbeans