finiteAutomata
Class CNF

java.lang.Object
  extended by 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.
protected  void addTypeOneDialog()
          Queries user for n and t in the rule "vn -> t" and adds the correpsonding rule.
 void addTypeZero(int n, int i, int j)
          Adds rule "vn -> vi vj" to the rule set.
protected  void addTypeZeroDialog()
          Queries user for n, i, and j in the rule "vn -> vi vj" and adds the correpsonding rule.
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}.
protected  int constructorMenu()
          Repeatedly displays constructor menu options until user makes a valid choice.
 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)
           
protected  void menuHandler(int choice)
          Takes the appropriate action based on constructorMenu options.
protected  void predefinedDialog()
          Queries user regarding which pre-defined CNF they will use.
 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.
protected  void printLanguageDialog()
          Queries user for max string length and prints this CNF's language.
 void printRules()
          Pretty-prints the rule set.
protected  java.lang.String queryAlphabet()
          Queries user for alphabet of terminal symbols.
protected  boolean queryAmbiguous()
          Asks user if they want to have strings with ambiguous derivations be repeated.
protected  int queryNumVars()
          Prints constructor menu header and queries user regarding number of variables.
protected  boolean queryPredefined()
          Asks user if they want to use a pre-defined CNF.
 void removeTypeOne(int n, char t)
          Removes rule "vn -> t" from the rule set.
protected  void removeTypeOneDialog()
          Queries user for n and t, and removes rule "vn -> t".
 void removeTypeZero(int n, int i, int j)
          Removes rule "vn -> vi vj" from the rule set.
protected  void removeTypeZeroDialog()
          Queries user for n, i, and j, and removes rule "vn -> vi vj".
protected  void ruleChangeDialog()
          Asks user which type of rule change they want to make and carries out that request.
 StringVarTerm testString(java.lang.String s)
          Tests whether a given String is a NON-EMPTY terminal string which can be generated by this CNF.
protected  void testStringDialog()
          Determines whether a user-specified String is generated by this grammar.
 
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

queryPredefined

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

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

predefinedDialog

protected void predefinedDialog()
Queries user regarding which pre-defined CNF they will use.

Postcondition:
initializes this CNF to have the same data fields as the pre-defined grammar chosen by the user

queryAlphabet

protected java.lang.String queryAlphabet()
Queries user for alphabet of terminal symbols.

Returns:
String of terminal symbols as specified by user

queryNumVars

protected int queryNumVars()
Prints constructor menu header and queries user regarding number of variables.

Returns:
positive integer number of variables as specified by user

queryAmbiguous

protected boolean queryAmbiguous()
Asks user if they want to have strings with ambiguous derivations be repeated.

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

constructorMenu

protected int constructorMenu()
Repeatedly displays constructor menu options until user makes a valid choice.

Returns:
int choice number from 1 to 6

menuHandler

protected void menuHandler(int choice)
Takes the appropriate action based on constructorMenu options.

Parameters:
choice - integer code for user's desired action
Precondition:
1 <= choice <= 5

ruleChangeDialog

protected void ruleChangeDialog()
Asks user which type of rule change they want to make and carries out that request.

Postcondition:
rule array is altered to reflect addition/deletion of a rule, or value of startToEpsilon is possibly changed

addTypeZeroDialog

protected void addTypeZeroDialog()
Queries user for n, i, and j in the rule "vn -> vi vj" and adds the correpsonding rule.

Postcondition:
rule array is updated

addTypeOneDialog

protected void addTypeOneDialog()
Queries user for n and t in the rule "vn -> t" and adds the correpsonding rule.

Postcondition:
rule array is updated

removeTypeZeroDialog

protected void removeTypeZeroDialog()
Queries user for n, i, and j, and removes rule "vn -> vi vj".

Postcondition:
rule array is updated

removeTypeOneDialog

protected void removeTypeOneDialog()
Queries user for n and t, and removes rule "vn -> t".

Postcondition:
rule array is updated

printLanguageDialog

protected void printLanguageDialog()
Queries user for max string length and prints this CNF's language.

Postcondition:
all terminal strings generated by this CNF, up to the user-specified max length, are printed; according to user input, derivations may also be printed and strings with ambiguous derivations may appear multiple times

testStringDialog

protected void testStringDialog()
Determines whether a user-specified String is generated by this grammar.

Postcondition:
reports the result of the test and, if accepted, a derivation of the string

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)