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 labelled 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 addEpsilonDialog()
          Queries user regarding which epsilon transition to add.
protected  void addNewStart()
          Adds a new start state, shifting all other states to make room.
protected  void addTransitionDialog()
          Queries user regarding which symbol-consuming transition to add.
 Alphabet alpha()
          Returns a copy of the Alphabet.
protected  void changeTransition(int n)
          Takes action based on provided transition change choice code.
protected  int changeTransitionDialog()
          Queries user regarding desired transition change.
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.
protected  int constructorMenu()
          Displays constructor menu options and prompts user to choose an action.
protected  boolean constructorMenuHandler(int choice)
          Takes action based on the provided constructor menu choice code.
 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.
 boolean[][] epsilon()
          Returns a copy of the epsilon transition array.
 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.
 boolean[] isFinal()
          Returns a copy of the isFinal array.
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 in form "(i,x) -> j".
protected  void queryAlphabet()
          Queries user to obtain alphabet of input symbols.
protected  void queryFinal()
          Queries user to determine which states are final.
protected  int queryNumStates()
          Prints constructor menu heading, and queries user until valid (positive) number of states is obtained.
protected  boolean queryPredefined()
          Asks user if they want to use a pre-defined NFA.
 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.
protected  void removeEpsilonDialog()
          Queries user regarding which epsilon transition to remove.
protected  void removeTransitionDialog()
          Queries user regarding which symbol-consuming transition to remove.
protected  int runMenu()
          Displays run menu options and prompts user to make a choice of action.
protected  boolean runMenuHandler(int choice)
          Takes action based on the provided run menu choice code.
 void starClosure()
          Replaces this NFA by its star closure.
protected  void testingDialog()
          Allows the user to repeatedly test strings on this NFA.
 boolean[][][] transition()
          Returns a copy of the symbol-consuming transition array.
 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

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.

transition

public boolean[][][] transition()
Returns a copy of the symbol-consuming transition array.

Returns:
deep copy of this.transition

epsilon

public boolean[][] epsilon()
Returns a copy of the epsilon transition array.

Returns:
deep copy of this.epsilon

isFinal

public boolean[] isFinal()
Returns a copy of the isFinal array.

Returns:
deep copy of this.isFinal

queryPredefined

protected boolean queryPredefined()
Asks user if they want to use a pre-defined NFA.

Returns:
true iff user response begins with 'Y' or 'y'

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

queryNumStates

protected int queryNumStates()
Prints constructor menu heading, and queries user until valid (positive) number of states is obtained.

Returns:
positive integer for numStates

queryAlphabet

protected void queryAlphabet()
Queries user to obtain alphabet of input symbols.

Postcondition:
Alphabet of this NFA is initialized according to user response

queryFinal

protected void queryFinal()
Queries user to determine which states are final.

Postcondition:
isFinal array is initialized according to user responses

constructorMenu

protected int constructorMenu()
Displays constructor menu options and prompts user to choose an action.

Returns:
valid choice number (1 thru 6)

constructorMenuHandler

protected boolean constructorMenuHandler(int choice)
Takes action based on the provided constructor menu choice code.

Parameters:
choice - constructor menu choice code
Returns:
true iff user is done with menu options
Precondition:
1 <= choice <= 6

runMenu

protected int runMenu()
Displays run menu options and prompts user to make a choice of action.

Returns:
integer choice code (1 through 9)

runMenuHandler

protected boolean runMenuHandler(int choice)
Takes action based on the provided run menu choice code.

Parameters:
choice - run menu choice code
Returns:
true iff user is done with menu options
Precondition:
1 <= choice <= 9

changeTransitionDialog

protected int changeTransitionDialog()
Queries user regarding desired transition change.

Returns:
transition change choice code (1 through 4)

changeTransition

protected void changeTransition(int n)
Takes action based on provided transition change choice code.

Parameters:
n - transition change choice code
Postcondition:
makes changes to transition array and re-calculates the equivalent DFA

removeEpsilonDialog

protected void removeEpsilonDialog()
Queries user regarding which epsilon transition to remove.

Postcondition:
if user provides valid state numbers i and j, epsilon[i][j] is set to false and the equivalent DFA is re-calculated

removeTransitionDialog

protected void removeTransitionDialog()
Queries user regarding which symbol-consuming transition to remove.

Postcondition:
if user provides valid state numbers i and j, and valid symbol s, the transition array is changed accordingly and the equivalent DFA is re-calculated

addEpsilonDialog

protected void addEpsilonDialog()
Queries user regarding which epsilon transition to add.

Postcondition:
if user provides valid state numbers i and j, epsilon[i][j] is set to true and the equivalent DFA is re-calculated

addTransitionDialog

protected void addTransitionDialog()
Queries user regarding which symbol-consuming transition to add.

Postcondition:
if user provides valid state numbers i and j, and valid symbol s, the transition array is changed accordingly and the equivalent DFA is re-calculated

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

testingDialog

protected void testingDialog()
Allows the user to repeatedly test strings on this NFA.

Postcondition:
Each input string is echoed back to the console with a report of the string's length and whether or not it is accepted

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 in form "(i,x) -> j".


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

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)