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.
protected void	constructD1() Initializes this to be the DFA corresponding to Sipser, Figure 1.4.
protected void	constructD2() Initializes this to be the DFA corresponding to Sipser, Figure 1.8.
protected void	constructD3() Initializes this to be the DFA corresponding to Sipser, Figure 1.10.
protected void	constructD4() Initializes this to be the DFA corresponding to Sipser, Figure 1.12.
protected void	constructD5() Initializes this to be the DFA corresponding to Sipser, Figure 1.14.
protected void	constructD6() Initializes this to be the DFA corresponding to Sipser, Figure 1.22.
IntSet	finalStates() Returns the set of state numbers of all final states.
java.util.Vector	getLanguage(int n) Returns the language accepted by this DFA, thru a given max length.
static void	main(java.lang.String[] args)
protected void	makePredefined() Initializes this DFA according to the user's choice of pre-defined DFA object.
void	printDFA() Pretty-prints the DFA specifications.
void	printLanguage(int n) Prints the language accepted by this DFA, thru a given 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.
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.
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 equals one of the strings 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, deep copies are made of all the arguments so that subsequent changes to any of these arguments will not affect the DFA constructed by this method

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.

getLanguage

public java.util.Vector getLanguage(int n)

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

Parameters:

n - maximum string length

Returns:

Vector (of Strings) containing the language accepted by this DFA, in lexicographic order, up through strings of length n (returns null if n < 0)

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 this DFA, in lexicographic order, up through strings of length n, prints nothing if n < 0, prints "" if n >= 0 and no strings of length n or less are accepted

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

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

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, ...)

makePredefined

protected void makePredefined()

Initializes this DFA according to the user's choice of pre-defined DFA object.

Postcondition:

initializes "this" DFA to match user choice

constructD1

protected 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

protected 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

protected 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

protected 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

protected 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

protected 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)