finiteAutomata
Class NFA

java.lang.Object
  extended by finiteAutomata.NFA

public class NFA
extends java.lang.Object

Nondeterministic Finite Automaton.

An nfa has a non-empty, finite set of states Q; an alphabet S; a transition function d which maps Q x (S U {epsilon}) to P(Q); a unique "start" state; and zero or more "final" states. Notice that in an nfa, there can be zero, one, two, or multiple transitions from a given state on a given alphabet symbol, and epsilon transitions are also allowed (transitioning without processing an input symbol). The language L which is accepted by the nfa is the set of all strings s in S* which direct the nfa from "start" to any "final" state along at least one branch of the computation entailed by the transition function d. Though nfas seem quite different from dfas, it is a fact that they have no additional expressive power: every nfa has an equivalent dfa (a dfa which accepts the same language).

Data Fields: NFA states are labeled 0, 1, 2, etc., where state 0 is always the start state. There are data fields "numStates" for recording the number of states in the NFA, and "alpha" for storing the NFA's alphabet of input symbols. Final states are indicated with a boolean array, "isFinal".

With n states and m alphabet symbols, there are n x m possible inputs to the transition function (not counting epsilon transitions). An output from the transition function has to specify a list of zero or more destination states; we will represent this output with a 1-dimensional boolean array where "true" values indicate valid transitions. Thus, each NFA has a 3-dimensional boolean "transition" array: for each possible "from" state i, for each possible "to" state j, for the kth alphabet symbol, transition[i][j][k] is "true" iff we can transition from state i to state j on the kth alphabet symbol. Epsilon transitions are recorded in a separate boolean array: epsilon[i][j] is true iff we can transition from state i to state j on epsilon.

Each NFA has an equivalent DFA "D" whose states are a subset of the power set of {0,1,2,3,...,numStates-1}. Computations on the NFA are simulated by the corresponding computations on the equivalent DFA.

Version:
Fall 2007
Author:
Barbara Wahl

Field Summary
protected  Alphabet alpha
          input symbols
protected  DFA D
          an equivalent DFA
protected  boolean[][] epsilon
          for epsilon transitions; epsilon[i][j] is true iff we can transition from state i to state j on epsilon
protected  boolean[] isFinal
          to indicate final states
protected  int numStates
          number of states (positive)
protected  boolean[][][] transition
          for symbol-consuming transitions; transition[i][j][k] is true iff we can transition from state i to state j on the kth alphabet symbol.
 
Constructor Summary
NFA()
          0-parameter constructor.
NFA(int n, java.lang.String a, boolean[][][] t, boolean[][] e, boolean[] f)
          5-parameter constructor.
 
Method Summary
 boolean accepts(java.lang.String inString)
          Tests whether this NFA accepts a given input string.
protected  void addNewStart()
          Adds a new start state, shifting all other states to make room.
 Alphabet alpha()
          Returns a copy of the Alphabet.
protected  void constructN1()
          Makes "this" into an NFA corresponding to Sipser, Figure 1.27.
protected  void constructN2()
          Makes "this" into an NFA corresponding to Sipser, Figure 1.31.
protected  void constructN3()
          Makes "this" into an NFA corresponding to Sipser, Figure 1.34.
protected  void constructN4()
          Makes "this" into an NFA corresponding to Sipser, Figure 1.36.
 DFA convertToDFA()
          Returns a DFA which is equivalent to this NFA.
 boolean[] dfaGetFinal()
          Returns an array of boolean values for "isFinal" array of an equivalent DFA.
 int[][] dfaSetTransitions()
          Returns an array of DFA transitions for an equivalent DFA.
 IntSet[] getE()
          Returns the "E" array, where E[i] = set of all states reachable from state i in 0-or-more epsilon transitions.
 IntSet getE(IntSet set)
          Returns set of all states which are reachable from at least one state in the given set via 0-or-more epsilon transitions.
 IntSet getFinalSet()
          Returns the set of final states.
static void main(java.lang.String[] args)
           
 int numStates()
          Returns number of states.
protected  void predefinedDialog()
          Queries user which of 4 pre-defined NFAs they will use.
 void printFinal()
          Prints list of final states in this NFA.
 void printLanguage(int n)
          Prints the language accepted by this NFA up through a given maximum length.
 void printNFA()
          Pretty-prints this NFA's specifications.
 void printTransitions()
          Prints all the transitions (including epsilon transitions) in form "(i,x) -> j".
 IntSet reachable(int s, char c)
          Returns set of all states which are reachable from the given state on consuming the given input symbol.
 IntSet reachable(IntSet set, char c)
          Returns set of all states which are reachable from at least one state in the given set on consuming the given input symbol.
 void starClosure()
          Replaces this NFA by its star closure.
 boolean validState(int i)
          Returns true if the given integer is in the correct range to be a state in this NFA.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

numStates

protected int numStates
number of states (positive)


alpha

protected Alphabet alpha
input symbols


isFinal

protected boolean[] isFinal
to indicate final states


transition

protected boolean[][][] transition
for symbol-consuming transitions; transition[i][j][k] is true iff we can transition from state i to state j on the kth alphabet symbol.


epsilon

protected boolean[][] epsilon
for epsilon transitions; epsilon[i][j] is true iff we can transition from state i to state j on epsilon


D

protected DFA D
an equivalent DFA

Constructor Detail

NFA

public NFA()
0-parameter constructor. Uses console input to construct the NFA.

Postcondition:
constructs an NFA according to user's specifications

NFA

public NFA(int n,
           java.lang.String a,
           boolean[][][] t,
           boolean[][] e,
           boolean[] f)
5-parameter constructor.

Parameters:
n - number of desired states
a - input symbols
t - array of symbol-consuming transitions
e - array of epsilon transitions
f - array to indicate final states
Precondition:
n > 0, a is a non-null String of symbols with no whitespace or repeated characters, t is an array of size n x n x a.length(), e is an array of size n x n, f is an array of size n x 1
Postcondition:
constructs this NFA to have data fields as given by the arguments (arrays are deep-copied); initializes the dfa D
Method Detail

printNFA

public void printNFA()
Pretty-prints this NFA's specifications.

Postcondition:
prints report on numStates, Alphabet, start state, final states, and transitions

printFinal

public void printFinal()
Prints list of final states in this NFA.


printTransitions

public void printTransitions()
Prints all the transitions (including epsilon transitions) in form "(i,x) -> j".

Postcondition:
Each transition is pretty-printed on a separate line.

numStates

public int numStates()
Returns number of states.

Returns:
number of states in this NFA

alpha

public Alphabet alpha()
Returns a copy of the Alphabet.

Returns:
alpha.toString()

validState

public boolean validState(int i)
Returns true if the given integer is in the correct range to be a state in this NFA.

Parameters:
i - the integer to be tested
Returns:
true iff 0 <= i < numStates

getFinalSet

public IntSet getFinalSet()
Returns the set of final states.

Returns:
IntSet containing the state numbers of all final states.

reachable

public IntSet reachable(int s,
                        char c)
Returns set of all states which are reachable from the given state on consuming the given input symbol.

Parameters:
s - the current state
c - the input symbol to be read
Returns:
ignoring the effects of epsilon transitions, this method returns an IntSet (set of integers) of all the states which are possible to reach from state s on consuming input symbol c
Precondition:
s is a valid state number, c is a symbol in the input alphabet

reachable

public IntSet reachable(IntSet set,
                        char c)
Returns set of all states which are reachable from at least one state in the given set on consuming the given input symbol.

Parameters:
set - current states
c - the input symbol to be read
Returns:
ignoring the effects of epsilon transitions, returns an IntSet of all the states which are reachable from at least one state in "set" on consuming input symbol c.

getE

public IntSet[] getE()
Returns the "E" array, where E[i] = set of all states reachable from state i in 0-or-more epsilon transitions.

Returns:
array of IntSets; E[i] is all states reachable from i in 0-or-more epsilon transitions

getE

public IntSet getE(IntSet set)
Returns set of all states which are reachable from at least one state in the given set via 0-or-more epsilon transitions.

Parameters:
set - current states
Returns:
IntSet of all states reachable from "set" via 0-or-more epsilon transitions

dfaSetTransitions

public int[][] dfaSetTransitions()
Returns an array of DFA transitions for an equivalent DFA.

Returns:
an int array of size 2^numStates x alpha.size() holding all the transitions for an equivalent DFA

dfaGetFinal

public boolean[] dfaGetFinal()
Returns an array of boolean values for "isFinal" array of an equivalent DFA.

Returns:
correct boolean values for "isFinal" array of an equivalent DFA whose set of states is equal to the power set of {0,1,2,...,numStates-1}

convertToDFA

public DFA convertToDFA()
Returns a DFA which is equivalent to this NFA.

Returns:
a DFA which is equivalent to this NFA; the DFA will not have inaccessible states and will recognize the same language as this NFA

starClosure

public void starClosure()
Replaces this NFA by its star closure.

Postcondition:
this NFA is replaced by the star-closure of this NFA: a new, final start state is created, with epsilon transition to old start; epsilon transitions are added from ALL final states to old start; the equivalent dfa "D" is re-calculated

addNewStart

protected void addNewStart()
Adds a new start state, shifting all other states to make room.

Postcondition:
each state "i" becomes "i+1"; new state 0 is added; numStates is incremented; arrays "transition", "epsilon", and "isFinal" are updated to maintain all previous transitions and final states; does NOT update the dfa "D"; this must be done separately

accepts

public boolean accepts(java.lang.String inString)
Tests whether this NFA accepts a given input string.

Parameters:
inString - the String to be tested
Returns:
true iff this NFA accepts inString

printLanguage

public void printLanguage(int n)
Prints the language accepted by this NFA up through a given maximum length.

Parameters:
n - maximum string length to be printed
Precondition:
n >= 0
Postcondition:
prints the language accepted by this NFA, in lexicographic order, up through strings of length n

predefinedDialog

protected void predefinedDialog()
Queries user which of 4 pre-defined NFAs they will use.

Postcondition:
initializes this NFA to match user's choice of NFA

constructN1

protected void constructN1()
Makes "this" into an NFA corresponding to Sipser, Figure 1.27.

Postcondition:
all data fields are initialized to represent the desired NFA

constructN2

protected void constructN2()
Makes "this" into an NFA corresponding to Sipser, Figure 1.31.

Postcondition:
all data fields are initialized to represent the desired NFA

constructN3

protected void constructN3()
Makes "this" into an NFA corresponding to Sipser, Figure 1.34.

Postcondition:
all data fields are initialized to represent the desired NFA

constructN4

protected void constructN4()
Makes "this" into an NFA corresponding to Sipser, Figure 1.36.

Postcondition:
all data fields are initialized to represent the desired NFA

main

public static void main(java.lang.String[] args)