finiteAutomata
Class DFA

java.lang.Object
  finiteAutomata.DFA

public class DFA
extends java.lang.Object

Deterministic Finite Automaton.

A dfa has a non-empty, finite set of states Q; an alphabet S; a transition function d which maps Q x S to Q; a unique "start" state; and zero or more "final" states. The language L which is accepted by the dfa is the set of all strings s in S* which direct the dfa from "start" to any "final" state (according to the transition function d).

Data Fields: In the DFA class we represent a DFA's transition function as a 2-dimensional array of integers. Suppose the DFA has n states and m alphabet symbols. For any integer i from 0 through n-1 and any integer j from 0 through m-1, transition[i][j] indicates where to transition to (from state i) on reading the j-th alphabet symbol. A 1-dimensional boolean array "isFinal" is used to indicate which states (if any) are final. In addition, each DFA has a Vector (stateLabel) of Strings to label the states, an Alphabet (alpha) of input symbols, a counter (numStates) for |Q|, and a variable start state (start).

Methods: The DFA class has methods for generating the language of all strings accepted by the DFA (in lexicographic order, up through strings of the specified length n), for testing whether or not a given input string is accepted by the DFA, for demonstrating the Pumping Lemma for Regular Languages on a given language string, and for pruning inaccessible states from the DFA.

Note: From the user's point of view, states are referred to by label. Internally, states are numbered 0,1,2,... where 0 is not necessarily the start state.

Version:

Fall 2007

Author:

Barbara Wahl

Field Summary

protected Alphabet	alpha Alphabet of input symbols
protected boolean[]	isFinal boolean array to designate final states
protected int	numStates number of states
protected int	start start state
protected java.util.Vector	stateLabel list of labels for the states
protected int[][]	transition transition[i][j] tells where to transition to (from state i) on reading the j-th alphabet symbol

Constructor Summary

DFA()
0-parameter constructor, uses console input.

DFA(int n, java.lang.String[] L, java.lang.String startL, java.lang.String a, int[][] t, boolean[] f)
6-parameter constructor.

Method Summary

boolean	accepts(java.lang.String inString) Tests whether this DFA accepts a given String.
IntSet	accessible() Returns all the states which are reachable from start.
IntSet	accessible(IntSet S, int steps) Returns all the states which are reachable from a given set of states in a given number of steps.
private void	changeTransitionDialog() Changes one transition based on user input.
private void	constructD1() Initializes this to be the DFA corresponding to Sipser, Figure 1.4.
private void	constructD2() Initializes this to be the DFA corresponding to Sipser, Figure 1.8.
private void	constructD3() Initializes this to be the DFA corresponding to Sipser, Figure 1.10.
private void	constructD4() Initializes this to be the DFA corresponding to Sipser, Figure 1.12.
private void	constructD5() Initializes this to be the DFA corresponding to Sipser, Figure 1.14.
private void	constructD6() Initializes this to be the DFA corresponding to Sipser, Figure 1.22.
private int	constructorMenu() Displays constructor menu options until user makes a valid choice.
IntSet	finalStates() Returns the set of state numbers of all final states.
static void	main(java.lang.String[] args)
private boolean	menuHandler(int choice) Takes the appropriate action based on constructorMenu options.
private void	predefinedDialog() Queries user which pre-defined DFA they will use.
void	printDFA() Pretty-prints the DFA specifications.
void	printLanguage(int n) Prints the language accepted by this DFA, thru a given max length.
protected void	printLanguageDialog() Reports language of DFA up through user-specified max length.
void	printTransitions() Pretty-prints the DFA transitions.
void	prune() Eliminates inaccessible states.
void	pump(java.lang.String inString) Demonstrates the Pumping Lemma for Regular Languages.
private boolean	pumpTest(java.lang.String inString) Prints header for pump report and tests the pumping preconditions.
private void	queryAlphabet() Initializes alpha according to user input.
private void	queryFinal() Initializes isFinal array according to user input.
private void	queryLabels() Obtains and initializes state labels based on user input.
private int	queryNumStates() Prints constructor menu banner and asks user how many states in DFA.
private boolean	queryPredefined() Asks user if they want to use a pre-defined DFA.
private int	queryStart() Asks user for start state.
private void	queryTransition() For each state and each alphabet symbol, asks user for destination.
private int	queryValidState() Queries user repeatedly to enter a state label.
private int	queryValidSymbol() Queries user repeatedly to enter an input symbol.
private int	queryValidTransition(int i, int j) Queries user repeatedly to enter a valid destination state.
java.lang.String	stateName(int i) Returns the label for a given state number.
int	stateNumber(java.lang.String s) Returns the index of a given String in the stateLabel vector.
protected void	testEpsilonDialog() Tests whether the epsilon string is accepted.
protected void	testingHandler() Allows the user to repeatedly test strings or print this DFA's language.
private int	testingMenu() Presents testing menu options to user and obtains valid choice.
protected void	testStringDialog() Queries user for string to test and reports back.
boolean	validLabel(java.lang.String s) Tests whether a given String is a valid state label.
boolean	validState(int i) Tests whether a given int is in the proper range to be a state number.

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

stateLabel

protected java.util.Vector stateLabel

list of labels for the states

alpha

protected Alphabet alpha

Alphabet of input symbols

transition

protected int[][] transition

transition[i][j] tells where to transition to (from state i) on reading the j-th alphabet symbol

isFinal

protected boolean[] isFinal

boolean array to designate final states

start

protected int start

start state

Constructor Detail

DFA

public DFA()

0-parameter constructor, uses console input.

Postcondition:

constructs a DFA according to information obtained from the user

DFA

public DFA(int n,
           java.lang.String[] L,
           java.lang.String startL,
           java.lang.String a,
           int[][] t,
           boolean[] f)

6-parameter constructor.

Parameters:

n - number of states

L - String array of state labels

startL - String label for the start state

a - String representation of the input alphabet

t - array representation of the transition function

f - boolean array to determine final states

Precondition:

n > 0, L is an array containing n non-null String objects, startL is one of the String objects in L, a is a non-empty String with no repeated characters or whitespace, t has dimensions n by a.length(), every integer i in array t satisfies 0 <= i < n

Postcondition:

constructs an n-state DFA with alphabet a and transition array t, state labels given by L, and final states given by f

Method Detail

accepts

public boolean accepts(java.lang.String inString)

Tests whether this DFA accepts a given String.

Parameters:

inString - the String to be tested

Returns:

true iff this DFA accepts inString

Precondition:

inString is non-null

accessible

public IntSet accessible()

Returns all the states which are reachable from start.

Returns:

IntSet of all the states which are reachable from start in 0 or more transitions

accessible

public IntSet accessible(IntSet S,
                         int steps)

Returns all the states which are reachable from a given set of states in a given number of steps.

Parameters:

S - IntSet of states from which to start

steps - maximum number of transitions allowed

Returns:

IntSet of all the states which are reachable from some state in S in steps or fewer transitions

Precondition:

each state i in S satisfies 0 <= i < numStates, steps >= 0

finalStates

public IntSet finalStates()

Returns the set of state numbers of all final states.

Returns:

an IntSet containing the state numbers of all final states

printDFA

public void printDFA()

Pretty-prints the DFA specifications.

printLanguage

public void printLanguage(int n)

Prints the language accepted by this DFA, thru a given max length.

Parameters:

n - maximum string length

Postcondition:

prints the language accepted by the DFA, in lexicographic order, up through strings of length n

printTransitions

public void printTransitions()

Pretty-prints the DFA transitions.

Postcondition:

prints each transition on its own line in the form "(from,x) -> to", where "from" and "to" are state names and x is an input symbol

prune

public void prune()

Eliminates inaccessible states.

Postcondition:

eliminates all inaccessible states from this DFA; alpha is unchanged, but all the other data fields may change

pump

public void pump(java.lang.String inString)

Demonstrates the Pumping Lemma for Regular Languages.

Parameters:

inString - String to be pumped

Precondition:

inString.length() >= numStates, inString is accepted by this DFA

Postcondition:

prints info to the console to answer the following: (i) What is a "pumping length" p? (ii) What are values of x, y, and z which satisfy Sipser's Thm 1.70 (Pumping Lemma for Regular Languages)? (iii) Which strings are generated by pumping inString down or up? (xz, xyyz, xyyyz, xyyyyz, ...)

stateName

public java.lang.String stateName(int i)

Returns the label for a given state number.

Parameters:

i - the state number

Returns:

the label for state i

Precondition:

i is a valid state number

stateNumber

public int stateNumber(java.lang.String s)

Returns the index of a given String in the stateLabel vector.

Parameters:

s - state label

Returns:

int i such that s equals stateLabel.elementAt(i), or -1 if not found

Precondition:

s is not null

validLabel

public boolean validLabel(java.lang.String s)

Tests whether a given String is a valid state label.

Parameters:

s - String to be tested

Returns:

true iff s is contained in the stateLabel vector

Precondition:

s is not null

validState

public boolean validState(int i)

Tests whether a given int is in the proper range to be a state number.

Parameters:

i - int value to be tested

Returns:

true iff 0 <= i < numStates

constructorMenu

private int constructorMenu()

Displays constructor menu options until user makes a valid choice.

Returns:

choice (int from 1 thru 8)

menuHandler

private boolean menuHandler(int choice)

Takes the appropriate action based on constructorMenu options.

Parameters:

choice - user's desired action code

Returns:

true iff user is done with menu

Precondition:

1 <= choice <= 8

testingHandler

protected void testingHandler()

Allows the user to repeatedly test strings or print this DFA's language.

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

testingMenu

private int testingMenu()

Presents testing menu options to user and obtains valid choice.

Returns:

choice (int from 1 thru 4)

testEpsilonDialog

protected void testEpsilonDialog()

Tests whether the epsilon string is accepted.

Postcondition:

reports string length (0) and result

testStringDialog

protected void testStringDialog()

Queries user for string to test and reports back.

Postcondition:

reports string length and result

printLanguageDialog

protected void printLanguageDialog()

Reports language of DFA up through user-specified max length.

Postcondition:

queries user for max string length; reports language of DFA up through that max length

queryNumStates

private int queryNumStates()

Prints constructor menu banner and asks user how many states in DFA.

Returns:

positive int obtained from user for numStates

queryLabels

private void queryLabels()

Obtains and initializes state labels based on user input.

Postcondition:

user is prompted to enter a label for each state; responses are stored in stateLabel vector

queryPredefined

private boolean queryPredefined()

Asks user if they want to use a pre-defined DFA.

Returns:

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

predefinedDialog

private void predefinedDialog()

Queries user which pre-defined DFA they will use.

Postcondition:

initializes "this" DFA to match user choice

queryStart

private int queryStart()

Asks user for start state.

Returns:

valid state number (int from 0 thru numStates - 1)

queryAlphabet

private void queryAlphabet()

Initializes alpha according to user input.

Postcondition:

input Alphabet is initialized

queryFinal

private void queryFinal()

Initializes isFinal array according to user input.

Postcondition:

final states are initialized as requested by user

queryValidState

private int queryValidState()

Queries user repeatedly to enter a state label.

Returns:

corresponding state number of the first valid state label obtained

queryValidSymbol

private int queryValidSymbol()

Queries user repeatedly to enter an input symbol.

Returns:

corresponding symbol number of the first valid symbol obtained

queryValidTransition

private int queryValidTransition(int i,
                                 int j)

Queries user repeatedly to enter a valid destination state.

Parameters:

i - current state number

j - index of input symbol being read (position in alpha)

Returns:

destination state number (int from 0 thru numStates - 1)

Precondition:

0 <= i < numStates and 0 <= j < alpha.size()

queryTransition

private void queryTransition()

For each state and each alphabet symbol, asks user for destination.

Postcondition:

transition array is filled with valid state numbers as given by user

changeTransitionDialog

private void changeTransitionDialog()

Changes one transition based on user input.

Postcondition:

transition array is altered in zero or one places, as requested by user

pumpTest

private boolean pumpTest(java.lang.String inString)

Prints header for pump report and tests the pumping preconditions.

Parameters:

inString - String to be pumped

Returns:

true iff inString.length() >= numStates and inString is accepted

Postcondition:

(1) prints header for "pump" report (2) reports error if inString.length() < numStates (3) reports error if inString is not accepted

constructD1

private void constructD1()

Initializes this to be the DFA corresponding to Sipser, Figure 1.4.

Postcondition:

all data fields are initialized to make a DFA equivalent to Sipser, Figure 1.4

constructD2

private void constructD2()

Initializes this to be the DFA corresponding to Sipser, Figure 1.8.

Postcondition:

all data fields are initialized to make a DFA equivalent to Sipser, Figure 1.8

constructD3

private void constructD3()

Initializes this to be the DFA corresponding to Sipser, Figure 1.10.

Postcondition:

all data fields are initialized to make a DFA equivalent to Sipser, Figure 1.10

constructD4

private void constructD4()

Initializes this to be the DFA corresponding to Sipser, Figure 1.12.

Postcondition:

all data fields are initialized to make a DFA equivalent to Sipser, Figure 1.12

constructD5

private void constructD5()

Initializes this to be the DFA corresponding to Sipser, Figure 1.14.

Postcondition:

all data fields are initialized to make a DFA equivalent to Sipser, Figure 1.14

constructD6

private void constructD6()

Initializes this to be the DFA corresponding to Sipser, Figure 1.22.

Postcondition:

all data fields are initialized to make a DFA equivalent to Sipser, Figure 1.22

main

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