Input: A nondeterministic finite automaton (NFA) is a 5-tuple (Q, y, qa, A, 5),
ID: 3853026 • Letter: I
Question
Input: A nondeterministic finite automaton (NFA) is a 5-tuple (Q, y, qa, A, 5), where Q is a finite set of states, is a finite input alphabet, qo E Q is the initial state, A c Q is the set of accepting states, and Q x U{A) 2 is the transition function. Note: The values of are not single states, but sets of states. For every element q of Q and every element of NU A), we interpret o(q, G) as the set of states to which the NFA can move from state q on input o. Defining is a little harder than for an FA, since (q, x) is a set, as is 5(p, o) for any p in the first set: u{6(p, o) l p E (q, x)) is a first step towards o*. We must also consider A-transitions, which could potentially occur at any stage. Suppose M (Q, y, qo, A, o) is an NFA and Sg Q is a set of states. The A-closure of S is the set A(S) that can be defined recursively as follows: SgA (S) For every q E A(S), (q, A) cA(S). As for any finite set that is defined recursively, we can easily formulate an algorithm to calculate A(S):Explanation / Answer
/*
* JFLAP - Formal Languages and Automata Package
* JFLAP is open source software. Please see the LICENSE for terms.
*
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.StringTokenizer;
import automata.AlphabetRetriever;
import automata.Automaton;
import automata.AutomatonChecker;
import automata.ClosureTaker;
import automata.State;
import automata.StatePlacer;
import automata.Transition;
public class NFAToDFA {
/**
* Creates an instance of <CODE>NFAToDFA</CODE>
*/
public NFAToDFA() {
}
/**
* Returns the initial state for <CODE>dfa</CODE>. A state is created to
* represent the initial state from <CODE>nfa</CODE> (and its closure),
* and added to <CODE>dfa</CODE>. The initial state of <CODE>dfa</CODE>
* is set to the returned state.
*/
public State createInitialState(Automaton nfa, Automaton dfa) {
/** get closure of initial state from nfa. */
State initialState = nfa.getInitialState();
State[] initialClosure = ClosureTaker.getClosure(initialState, nfa);
/**
* create state in dfa to represent closure of initial state in nfa.
*/
State state = createStateWithStates(dfa, initialClosure, nfa);
dfa.setInitialState(state);
return state;
}
/**
* Returns true if one or more of the states in <CODE>states</CODE> are
* final.
*/
public boolean hasFinalState(State[] states, Automaton automaton) {
for (int k = 0; k < states.length; k++) {
if (automaton.isFinalState(states[k]))
return true;
}
return false;
}
/**
* Returns the State array mapped to <CODE>state</CODE>.
*/
public State[] getStatesForState(State state, Automaton automaton) {
if (state.getLabel() == null)
return new State[0];
StringTokenizer tokenizer = new StringTokenizer(state.getLabel(),
" ,q");
ArrayList states = new ArrayList();
while (tokenizer.hasMoreTokens())
states.add(automaton.getStateWithID(Integer.parseInt(tokenizer
.nextToken())));
return (State[]) states.toArray(new State[0]);
}
/**
* Returns a string representation of <CODE>states</CODE>.
*/
public String getStringForStates(State[] states) {
StringBuffer buffer = new StringBuffer();
for (int k = 0; k < states.length - 1; k++) {
buffer.append(Integer.toString(states[k].getID()));
buffer.append(",");
}
buffer.append(Integer.toString(states[states.length - 1].getID()));
return buffer.toString();
}
/**
* Returns all states reachable on <CODE>terminal</CODE> from <CODE>states</CODE>,
* including the closure of all reachable states.
*/
public State[] getStatesOnTerminal(String terminal, State[] states,
Automaton automaton) {
ArrayList list = new ArrayList();
for (int k = 0; k < states.length; k++) {
State state = states[k];
Transition[] transitions = automaton.getTransitionsFromState(state);
for (int i = 0; i < transitions.length; i++) {
FSATransition transition = (FSATransition) transitions[i];
if (transition.getLabel().equals(terminal)) {
State toState = transition.getToState();
State[] closure = ClosureTaker.getClosure(toState,
automaton);
for (int j = 0; j < closure.length; j++) {
if (!list.contains(closure[j])) {
list.add(closure[j]);
}
}
}
}
}
return (State[]) list.toArray(new State[0]);
}
/**
* Returns true if <CODE>states</CODE> contains <CODE>state</CODE>
*
*/
private boolean containsState(State state, State[] states) {
for (int k = 0; k < states.length; k++) {
if (states[k] == state)
return true;
}
return false;
}
/**
* Returns true if <CODE>states1</CODE> and <CODE>states2</CODE> are
* identical (i.e. they contain exactly the same states, and no extras).
*
*/
public boolean containSameStates(State[] states1, State[] states2) {
int len1 = states1.length;
int len2 = states2.length;
if (len1 != len2)
return false;
Arrays.sort(states1, new Comparator<State>(){
public int compare(State s, State t){
return s.hashCode() - t.hashCode();
}
});
Arrays.sort(states2, new Comparator<State>(){
public int compare(State s, State t){
return s.hashCode() - t.hashCode();
}
});
for (int k = 0; k < states1.length; k++) {
// if (!containsState(states1[k], states2))
// return false;
if (states1[k] != states2[k])
return false;
}
return true;
}
/**
* Returns the State mapped to <CODE>states</CODE>.
*
*/
public State getStateForStates(State[] states, Automaton dfa, Automaton nfa) {
State[] dfaStates = dfa.getStates();
for (int k = 0; k < dfaStates.length; k++) {
State[] nfaStates = getStatesForState(dfaStates[k], nfa);
if (containSameStates(nfaStates, states)) {
return dfaStates[k];
}
}
return null;
}
/**
* Returns a list of States created by expanding <CODE>state</CODE> in
* <CODE>dfa</CODE>. <CODE>state<CODE> is a state in <CODE>dfa</CODE>
* that represents a set of states in <CODE>nfa</CODE>. This method adds
* transitions to <CODE>dfa</CODE> from <CODE>state</CODE> on all
* terminals in the alphabet of <CODE>nfa</CODE> for which it is relevant.
* For each letter in the alphabet, you determine the reachable states (from
* <CODE>nfa</CODE>) from the set of states represented by <CODE>state</CODE>.
* You then create a state in <CODE>dfa</CODE> that represents all these
* reachable states and add a transition to DFA connecting <CODE>state</CODE>
* and this newly created state.
*/
public ArrayList expandState(State state, Automaton nfa, Automaton dfa) {
ArrayList list = new ArrayList();
AlphabetRetriever far = new FSAAlphabetRetriever();
String[] alphabet = far.getAlphabet(nfa);
/** for each letter in the alphabet. */
for (int k = 0; k < alphabet.length; k++) {
/**
* get states reachable on terminal from all states represented by
* state.
*/
State[] states = getStatesOnTerminal(alphabet[k],
getStatesForState(state, nfa), nfa);
/** if any reachable states on terminal. */
if (states.length > 0) {
/**
* get state from dfa that represents list of reachable states
* in nfa.
*/
State toState = getStateForStates(states, dfa, nfa);
/** if no such state. */
if (toState == null) {
/** create state, add to list */
toState = createStateWithStates(dfa, states, nfa);
// StatePlacer sp = new StatePlacer();
// Point point = sp.getPointForState(dfa);
// toState = dfa.createState(point);
// toState.setLabel(getStringForStates(states));
// if(hasFinalState(states, nfa)) {
// dfa.addFinalState(toState);
// }
list.add(toState);
}
/**
* add transition to dfa from state to state that represents
* reachables states on terminal from nfa.
*/
Transition transition = new FSATransition(state, toState,
alphabet[k]);
dfa.addTransition(transition);
}
}
return list;
}
/**
* Creates a state in <CODE>dfa</CODE>, labelled with the set of states
* in <CODE>states</CODE>, which are all states from <CODE>nfa</CODE>.
*
*/
public State createStateWithStates(Automaton dfa, State[] states,
Automaton nfa) {
StatePlacer sp = new StatePlacer();
State state = dfa.createState(sp.getPointForState(dfa));
state.setLabel(getStringForStates(states));
if (hasFinalState(states, nfa)) {
dfa.addFinalState(state);
}
return state;
}
/**
* Returns a deterministic finite state automaton equivalent to <CODE>automaton</CODE>.
* <CODE>automaton</CODE> is not at all affected by this conversion.
*/
public FiniteStateAutomaton convertToDFA(Automaton automaton) {
/** check if actually nfa. */
AutomatonChecker ac = new AutomatonChecker();
if (!ac.isNFA(automaton)) {
return (FiniteStateAutomaton) automaton.clone();
}
/** remove multiple character labels. */
if (FSALabelHandler.hasMultipleCharacterLabels(automaton)) {
FSALabelHandler.removeMultipleCharacterLabelsFromAutomaton(automaton);
}
/** create new finite state automaton. */
FiniteStateAutomaton dfa = new FiniteStateAutomaton();
State initialState = createInitialState(automaton, dfa);
/**
* get initial state and add to list of states that need to be expanded.
*/
ArrayList list = new ArrayList();
list.add(initialState);
/** while still more states to be expanded. */
while (!list.isEmpty()) {
ArrayList statesToExpand = new ArrayList();
Iterator it = list.iterator();
while (it.hasNext()) {
State state = (State) it.next();
/** expand state. */
statesToExpand.addAll(expandState(state, automaton, dfa));
it.remove();
}
list.addAll(statesToExpand);
}
return dfa;
}
}