finiteAutomata
Class CNF

java.lang.Object
  finiteAutomata.CNF

public class CNF
extends java.lang.Object

Chomsky Normal Form grammar. Every context-free grammar can be represented by an equivalent CNF grammar.

A CNF grammar has a non-empty set of variables, a non-empty set of terminal symbols (disjoint from the set of variables), and a set of production rules for transforming the variables. One of the variables is singled out as the "start" variable.

Data Fields: The terminal symbols of a CNF object are stored as an Alphabet, "alpha". The variables are denoted v0, v1, v2, etc., where v0 is always the start variable. "numVars" records the number of variables in the grammar.

The grammar rules are stored in a two-dimensional array (numVars x 2) of Vectors of CNFRule objects. If vn is one of the variables, all the type 0 rules for transforming vn (form "vn -> vi vj" are stored in the Vector "rule[n][0]", and all the type 1 rules for transforming vn (form "vn -> terminal") are stored in the Vector "rule[n][1]".

If the rule "v0 -> epsilon" is included in the grammar, the boolean variable "startToEpsilon" is set to true (this is the only rule not stored in the rule array).

Version:

Fall 2007

Author:

Barbara Wahl

Field Summary

protected Alphabet	alpha terminal symbols
protected int	numVars number of variables
protected java.util.Vector[][]	rule array of Vectors of CNFRule objects; rule[i][j] contains all the type j rules which transform vi
protected boolean	startToEpsilon true if "v0 -> epsilon" is a rule

Constructor Summary

CNF()
0-parameter constructor, prompts the user for CNF information.

CNF(java.lang.String a, int n, boolean b, java.util.Vector[][] r)
4-parameter constructor.

Method Summary

void	addTypeOne(int n, char t) Adds rule "vn -> t" to the rule set.
void	addTypeZero(int n, int i, int j) Adds rule "vn -> vi vj" to the rule set.
protected void	constructC1() Initializes this to be a CNF grammar equivalent to Sipser's G1 (p.100).
protected void	constructC2() Initializes this to be a CNF grammar equivalent to Sipser's G3 (p.103).
protected void	constructC3() Initializes this to be a CNF grammar equivalent to Sipser's G6 (p.108).
protected void	constructC4() Initializes this to be a CNF grammar which generates 0*10*, strings with exactly one '1'.
protected void	constructC5() Initializes this to be a CNF grammar which generates all palindromes over the alphabet {0,1}.
java.util.Vector	getLanguage(int maxLength) Returns all NON-EMPTY terminal strings derivable in this grammar, up to a specified maximum string length.
java.util.Vector	getLanguageUnambiguous(int maxLength) Returns all NON-EMPTY terminal strings derivable in this grammar, up to a specified maximum string length.
boolean	isValidVariable(int i) Tests whether a given integer is a valid variable number for this CNF.
static void	main(java.lang.String[] args)
void	printCNF() Reports number of variables, alphabet of terminal symbols, and rule set.
protected void	printLanguage(java.util.Vector v, boolean printDeriv) Prints the strings in the given Vector, preceded by "epsilon" if epsilon is generated by this CNF.
void	printRules() Pretty-prints the rule set.
void	removeTypeOne(int n, char t) Removes rule "vn -> t" from the rule set.
void	removeTypeZero(int n, int i, int j) Removes rule "vn -> vi vj" from the rule set.
StringVarTerm	testString(java.lang.String s) Tests whether a given String is a NON-EMPTY terminal string which can be generated by this CNF.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

alpha

protected Alphabet alpha

terminal symbols

numVars

protected int numVars

number of variables

startToEpsilon

protected boolean startToEpsilon

true if "v0 -> epsilon" is a rule

rule

protected java.util.Vector[][] rule

array of Vectors of CNFRule objects; rule[i][j] contains all the type j rules which transform vi

Constructor Detail

CNF

public CNF()

0-parameter constructor, prompts the user for CNF information.

Postcondition:

constructs a CNF grammar with all data fields set according to user input

CNF

public CNF(java.lang.String a,
           int n,
           boolean b,
           java.util.Vector[][] r)

4-parameter constructor.

Parameters:

a - String representation of the desired alphabet with characters listed in the desired lexicographic order

n - int number of desired variables

b - true iff "v0 -> epsilon" is to be a rule

r - 2-dimensional array of Vectors of CNFRule objects

Precondition:

a is a non-empty string with no repeated characters, n > 0, r is size n x 2, and for each 0 <= i < n, r[i][j] is a non-null Vector (possibly empty) of CNFRule objects of type j which transform the variable vi (j = 0, 1)

Postcondition:

constructs a CNF grammar with Alphabet a, n variables, with rules given by the array r (and v0 -> epsilon iff b == true); the data field "rule" simply references r (r is not copied)

Method Detail

addTypeOne

public void addTypeOne(int n,
                       char t)

Adds rule "vn -> t" to the rule set.

Parameters:

n - integer specifying LHS variable

t - char specifying terminal symbol for RHS

Precondition:

n is a valid variable number for this CNF, t is a valid terminal symbol for this CNF

Postcondition:

if preconditions are met, and if the rule does not currently exist, the rule "vn -> t" is added to this CNF's rule set; otherwise, warning message is printed

addTypeZero

public void addTypeZero(int n,
                        int i,
                        int j)

Adds rule "vn -> vi vj" to the rule set.

Parameters:

n - integer specifying LHS variable

i - integer specifying first RHS variable

j - integer specifying second RHS variable

Precondition:

n, i, and j are valid variable numbers for this CNF

Postcondition:

if preconditions are met, if i>0 and j>0, and if the rule does not currently exist, rule "vn -> vi vj" is added to this CNF's rule set; otherwise, warning message is printed

getLanguage

public java.util.Vector getLanguage(int maxLength)

Returns all NON-EMPTY terminal strings derivable in this grammar, up to a specified maximum string length.

Parameters:

maxLength - int upper bound on string length

Returns:

Vector containing all NON-EMPTY terminal strings of length no more than maxLength which are derivable from start (v0); strings with multiple derivations will appear multiple times (demonstrating that the grammar is ambiguous)

getLanguageUnambiguous

public java.util.Vector getLanguageUnambiguous(int maxLength)

Returns all NON-EMPTY terminal strings derivable in this grammar, up to a specified maximum string length.

Parameters:

maxLength - int upper bound on string length

Returns:

Vector containing all NON-EMPTY terminal strings derivable in maxSteps or fewer steps from start; strings with multiple derivations will NOT appear multiple times

isValidVariable

public boolean isValidVariable(int i)

Tests whether a given integer is a valid variable number for this CNF.

Parameters:

i - int variable number to be tested

Returns:

true iff i >= 0 and i < number of variables in this CNF

printCNF

public void printCNF()

Reports number of variables, alphabet of terminal symbols, and rule set.

printRules

public void printRules()

Pretty-prints the rule set.

removeTypeOne

public void removeTypeOne(int n,
                          char t)

Removes rule "vn -> t" from the rule set.

Parameters:

n - integer specifying LHS variable

t - char specifying terminal symbol for RHS

Postcondition:

if rule is present, removes rule "vn -> t" from this CNF's rule set and informs user of deletion

removeTypeZero

public void removeTypeZero(int n,
                           int i,
                           int j)

Removes rule "vn -> vi vj" from the rule set.

Parameters:

n - integer specifying LHS variable

i - integer specifying first RHS variable

j - integer specifying second RHS variable

Precondition:

n, i, and j are valid variable numbers for this CNF

Postcondition:

if rule is present, removes rule "vn -> vi vj" from this CNF's rule set and informs user of deletion

testString

public StringVarTerm testString(java.lang.String s)

Tests whether a given String is a NON-EMPTY terminal string which can be generated by this CNF.

Parameters:

s - String to be tested

Returns:

the StringVarTerm object which shows how s is generated, or "null" if s is not in the language of this CNF grammar

Precondition:

s is non-empty

printLanguage

protected void printLanguage(java.util.Vector v,
                             boolean printDeriv)

Prints the strings in the given Vector, preceded by "epsilon" if epsilon is generated by this CNF.

Parameters:

v - Vector representing the non-epsilon terminal strings generated by this CNF (up to some maximum derivation length)

printDeriv - determines whether the derivation of each string is also printed

Precondition:

v is a non-null Vector of non-null StringVarTerm objects

Postcondition:

if v is empty and if epsilon is not generated, reports that "the language is empty"

constructC1

protected void constructC1()

Initializes this to be a CNF grammar equivalent to Sipser's G1 (p.100).

Postcondition:

data fields of this CNF grammar are set accordingly

constructC2

protected void constructC2()

Initializes this to be a CNF grammar equivalent to Sipser's G3 (p.103).

Postcondition:

data fields of this CNF grammar are set accordingly

constructC3

protected void constructC3()

Initializes this to be a CNF grammar equivalent to Sipser's G6 (p.108).

Postcondition:

data fields of this CNF grammar are set accordingly

constructC4

protected void constructC4()

Initializes this to be a CNF grammar which generates 0*10*, strings with exactly one '1'.

Postcondition:

data fields of this CNF grammar are set accordingly

constructC5

protected void constructC5()

Initializes this to be a CNF grammar which generates all palindromes over the alphabet {0,1}.

Postcondition:

data fields of this CNF grammar are set accordingly

main

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