package finiteAutomata;
import java.util.Vector;
/**
* Chomsky Normal Form grammar. Every context-free grammar can be represented
* by an equivalent CNF grammar.
*
* <BR><BR>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.
*
* <BR><BR>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.
*
* <BR><BR>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]".
*
* <BR><BR>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).
*
* @author Barbara Wahl
* @version Fall 2007
*/
public class CNF {
// ** DATA FIELDS **
/**
* terminal symbols
*/
protected Alphabet alpha;
/**
* number of variables
*/
protected int numVars;
/**
* true if "v0 -> epsilon" is a rule
*/
protected boolean startToEpsilon;
/**
* array of Vectors of CNFRule objects; rule[i][j] contains
* all the type j rules which transform vi
*/
protected Vector[][] rule;
// ** CONSTRUCTORS **
/**
* 0-parameter constructor, prompts the user for CNF information.
* @post constructs a CNF grammar with all data fields set according
* to user input
*/
public CNF()
{
int choice;
// predefined = true if user wants to use a predefined CNF object
boolean predefined = queryPredefined();
if(predefined)
predefinedDialog();
else
{ // "alpha" & "numVars" for user-defined CNF
numVars = queryNumVars();
alpha = new Alphabet(queryAlphabet());
startToEpsilon = false;
// allocate 2-dim'l array to hold references to Vectors
rule = new Vector[numVars][2];
for(int i=0; i<numVars; i++)
for(int j=0; j<2; j++)
// create the empty rule Vectors
rule[i][j] = new Vector();
}
// show current state of this CNF grammar
System.out.println("Current Grammar:");
this.printCNF();
// repeatedly display menu, allowing user to add rules, etc.
while(true)
{
choice = constructorMenu(); // get user action choice
if(choice == 6)
break; // user is done -- exit while loop
else menuHandler(choice);
}
System.out.println("Bye-bye!");
}
/**
* 4-parameter constructor.
* @param a String representation of the desired alphabet with
* characters listed in the desired lexicographic order
* @param n int number of desired variables
* @param b true iff "v0 -> epsilon" is to be a rule
* @param r 2-dimensional array of Vectors of CNFRule objects
* @pre a is a non-empty string with no repeated characters
* @pre n > 0
* @pre 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)
* @post 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)
*/
public CNF(String a, int n, boolean b, Vector[][] r)
{
Assert.pre(n > 0, "n is positive");
alpha = new Alphabet(a);
numVars = n;
startToEpsilon = b;
rule = new Vector[n][2];
for(int i=0; i<n; i++)
{
rule[i][0] = r[i][0];
rule[i][1] = r[i][1];
}
}
// ** PUBLIC METHODS **
/**
* Adds rule "vn -> t" to the rule set.
* @param n integer specifying LHS variable
* @param t char specifying terminal symbol for RHS
* @pre n is a valid variable number for this CNF
* @pre t is a valid terminal symbol for this CNF
* @post 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
*/
public void addTypeOne(int n, char t)
{
if(!this.isValidVariable(n) || !alpha.contains(t))
{
System.out.println("Invalid rule not added; can't have ");
System.out.print(new CNFRule(n,t));
return;
}
// check if this rule already exists
CNFRule newRule = new CNFRule(n,t);
if(rule[n][1].contains(newRule))
System.out.println("Rule " + newRule +
" was not added (it already exists).");
// proceed to add this rule
else
{
rule[n][1].add(newRule);
System.out.println("The rule " + newRule + " +" +
"has been added.");
}
}
/**
* Adds rule "vn -> vi vj" to the rule set.
* @param n integer specifying LHS variable
* @param i integer specifying first RHS variable
* @param j integer specifying second RHS variable
* @pre n, i, and j are valid variable numbers for this CNF
* @post 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
*/
public void addTypeZero(int n, int i, int j)
{
if(!this.isValidVariable(n) || !this.isValidVariable(i) ||
!this.isValidVariable(j) || i == 0 || j == 0)
{
System.out.println("Invalid rule not added; " +
"can't have ");
System.out.print(new CNFRule(n,i,j));
return;
}
// check if this rule already exists
CNFRule newRule = new CNFRule(n,i,j);
if(rule[n][0].contains(newRule))
System.out.println("Rule " + newRule +
" was not added (it already exists).");
// proceed to add this rule
else
{
rule[n][0].add(newRule);
System.out.println("The rule " + newRule + " +" +
"has been added.");
}
}
/**
* Returns all non-empty terminal strings derivable in a given number
* of steps.
* @param maxSteps int upper bound on derivation length
* @return Vector containing all NON-EMPTY terminal strings derivable
* in maxSteps or fewer steps from start; strings with multiple
* derivations WILL appear multiple times
*/
public Vector getLanguage(int maxSteps)
{
Vector q = new Vector(); // working space (use as queue)
q.add(new StringVarTerm(alpha)); // enqueue the start string, "v0"
Vector result = new Vector(); // store strings for return
StringVarTerm current = (StringVarTerm) q.elementAt(0);
StringVarTerm newString;
CNFRule r;
int leftMostIndex; // position of left-most variable in current
int lmv; // left-most variable in current
int head = 0; // index for top-of-queue (for lazy deletion)
// PLAN: current = q.dequeue; while current.numSteps isn't too
// large, either store current (if it has no vars) or use current
// to generate more strings (enqueue the new strings at tail of
// q & repeat)
while(current.numSteps() <= maxSteps)
{
head++; // effectively, q.dequeue
if(current.vars() == 0) // current is all terminals -- store it!
result.add(current);
// Otherwise, apply each applicable rule to "current" &
// enequeue results (FIRST check current.numSteps < maxSteps)
else if(current.numSteps() < maxSteps)
{
leftMostIndex = current.leftMostVarIndex();
lmv = current.decodeVar(leftMostIndex);
// code to prevent useless application of type 0 rules
int jStart = 0;
if(current.numSteps() + current.vars() >= maxSteps)
jStart = 1;
// for each rule which applies to left-most-variable "lmv"...
for(int j = jStart; j<2; j++) // j = rule type
for(int i=0; i<this.rule[lmv][j].size(); i++)
{
// r is the ith applicable rule of its type
r = (CNFRule)(this.rule[lmv][j]).elementAt(i);
newString = current.applyRule(r);
q.add(newString); // enqueue result
}
}
// stop if queue is empty
if(head >= q.size()) break;
// dequeue to current and repeat until maxSteps exceeded
current = (StringVarTerm)q.elementAt(head);
}
return result;
}
/**
* Returns all non-empty terminal strings derivable in a given number
* of steps, without repetitions.
* @param maxSteps int upper bound on derivation length
* @return Vector containing all NON-EMPTY terminal strings derivable
* in maxSteps or fewer steps from start; strings with multiple
* derivations will NOT appear multiple times
*/
public Vector getLanguageUnambiguous(int maxSteps)
{
Vector q = new Vector(); // working space (use as queue)
q.add(new StringVarTerm(alpha)); // enqueue the start string, "v0"
Vector result = new Vector(); // store terminal strings for return
StringVarTerm current = (StringVarTerm) q.elementAt(0);
StringVarTerm newString;
CNFRule r;
int leftMostIndex; // position of left-most variable in current
int lmv; // left-most variable in current
int head = 0; // index for top-of-queue (for lazy deletion)
Hashtable used = new Hashtable(9973); // creates a hashtable with
// tableSize = 9973 (lg prime)
String key; // will use String objects as keys
// PLAN: current = q.dequeue; while current.numSteps is not too
// large, either store current (if it has no vars) or use current
// to generate more strings (enqueue the new strings at tail of
// q & repeat). We avoid repetitions as follows.
// First, each time an element is added to "q", it is also put into
// the hashtable "used". Second, if an element "newString"
// representsthe same string of variables and terminals (maybe with
// a different derivation) as any element already in hashtable
// "used", then "newString" will not be added to "q".
while(current.numSteps() <= maxSteps)
{
head++; // effectively, q.dequeue
if(current.vars() == 0) // current is all terminals; store
result.add(current);
// Otherwise, apply each applicable rule to "current" &
// enqueue results (check current.numSteps < maxSteps)
else if(current.numSteps() < maxSteps)
{
leftMostIndex = current.leftMostVarIndex();
lmv = current.decodeVar(leftMostIndex);
// prevent useless application of type 0 rules
int jStart = 0;
if(current.numSteps() + current.vars() >= maxSteps)
jStart = 1;
// for each rule applicable to "lmv"...
for(int j = jStart; j<2; j++) // j = rule type
for(int i=0; i<this.rule[lmv][j].size(); i++)
{
// r is the ith applicable rule of type j
r = (CNFRule)(this.rule[lmv][j]).elementAt(i);
newString = current.applyRule(r);
key = newString.toPrettyString();
if(!used.contains(key))
{
q.add(newString); // enqueue
used.insert(key,null); // add to hashtable
}
}
}
if(head >= q.size())
break; // stop if q is (virtually) empty
// or, dequeue to current and repeat
current = (StringVarTerm)q.elementAt(head);
}
System.out.println("Hashtable max load factor = " +
used.loadFactor());
return result;
}
/**
* Tests whether a given integer is a valid variable number.
* number for this CNF
* @param i int variable number to be tested
* @return true iff i >= 0 and i < number of variables in this CNF
*/
public boolean isValidVariable(int i)
{
return (i >= 0 && i < numVars);
}
/**
* Reports number of variables, alphabet of terminal symbols, and
* rule set.
*/
public void printCNF()
{
System.out.println("numVars = " + numVars);
System.out.println("alphabet of terminals = " +
alpha.toPrettyString());
System.out.println("grammar rules:");
printRules();
}
/**
* Pretty-prints the rule set.
*/
public void printRules()
{
CNFRule theRule;
if(startToEpsilon)
System.out.println("v0 -> epsilon");
for(int n = 0; n < numVars; n++) // for each LHS variable n
for(int t = 0; t < 2; t++) // for both rule types t
// iterate thru rule[n][t]
for(int i = 0; i < rule[n][t].size(); i++)
{
theRule = (CNFRule)rule[n][t].elementAt(i);
System.out.println(theRule);
}
}
/**
* Removes rule "vn -> t" from the rule set.
* @param n integer specifying LHS variable
* @param t char specifying terminal symbol for RHS
* @post if rule is present, removes rule "vn -> t" from
* this CNF's rule set and informs user of deletion
*/
public void removeTypeOne(int n, char t)
{
if(this.isValidVariable(n) && alpha.contains(t))
rule[n][1].remove(new CNFRule(n,t));
System.out.println("The rule " + new CNFRule(n,t) +
" has been removed.");
}
/**
* Removes rule "vn -> vi vj" from the rule set.
* @param n integer specifying LHS variable
* @param i integer specifying first RHS variable
* @param j integer specifying second RHS variable
* @pre n, i, and j are valid variable numbers for this CNF
* @post if rule is present, removes rule "vn -> vi vj" from
* this CNF's rule set and informs user of deletion
*/
public void removeTypeZero(int n, int i, int j)
{
if(this.isValidVariable(n) && this.isValidVariable(i) &&
this.isValidVariable(j) && i > 0 && j > 0)
rule[n][0].remove(new CNFRule(n,i,j));
System.out.println("The rule " + new CNFRule(n,i,j) +
" has been removed.");
}
/**
* Tests whether a given String is a terminal string which can be
* generated by this CNF.
* @param s String to be tested
* @return the StringVarTerm object which shows how s is generated,
* or "null" if s is not in the language of this CNF grammar
*/
public StringVarTerm testString(String s)
{
int n = s.length();
if(n==0 || !alpha.indexArray(s,new int[n]))
return null; // give up if s not valid argument
// generate all strings up through length n using this CNF grammar
// Theorem: if s is a string of length n>0 in the language of
// of a CNF grammar, then every derivation of s has length 2*n-1.
Vector language = this.getLanguageUnambiguous(2*n-1);
// look for s among the StringVarTerm objects in lang
StringVarTerm current;
for(int i=0; i<language.size(); i++)
{
current = (StringVarTerm)language.elementAt(i);
// if "current" and "s" represent the terminal string
if(current.equalTermString(s))
return current; // success!
}
return null; // s not found in language
}
// ** MENU AND QUERY METHODS **
/**
* Asks user if they want to use a pre-defined CNF.
* @return true iff user's response begins with 'Y' or 'y'
*/
protected boolean queryPredefined()
{
System.out.print("Do you want to use a pre-defined CNF? " +
"Enter Y or N: ");
return Util.answerIsYes();
}
/**
* Queries user regarding which pre-defined CNF they will use.
* @post initializes this CNF to have the same data fields as the
* pre-defined grammar chosen by the user
*/
protected void predefinedDialog()
{
int num;
while(true)
{
System.out.println("Choose a pre-defined CNF grammar: ");
System.out.println(" 1 = equiv to Sipser G1, p.100");
System.out.println(" 2 = equiv to Sipser G3, p.103");
System.out.println(" 3 = equiv to Sipser G6, p.108");
System.out.println(" 4 = CNF grammar for 0*10*");
System.out.println(" 5 = CNF grammar for palindromes on" +
" {0,1}");
num = Util.readNum();
if(0 < num && num < 6)
break;
}
switch(num){
case 1:
constructC1();
break;
case 2:
constructC2();
break;
case 3:
constructC3();
break;
case 4:
constructC4();
break;
case 5:
constructC5();
break;
}
}
/**
* Queries user for alphabet of terminal symbols.
* @return String of terminal symbols as specified by user
*/
protected String queryAlphabet()
{
System.out.print(">> Enter a string with no spaces or " +
"repeated characters (terminal symbols): ");
return Util.readString();
}
/**
* Prints constructor menu header and queries user regarding number
* of variables.
* @return positive integer number of variables as specified by user
*/
protected int queryNumVars()
{
int num = 0; // temp storage for integer input
System.out.println("****** CNF CONSTRUCTOR MENU ******");
// ask user how many variables; only accept num > 0
while(num < 1)
{
System.out.print(">> Enter a positive integer " +
"(number of variables): ");
num = Util.readNum();
}
return num;
}
/**
* Asks user if they want to have strings with ambiguous derivations
* be repeated.
* @return true iff user response begins with 'Y' or 'y'
*/
protected boolean queryAmbiguous()
{
System.out.print("Repeat strings with ambiguous derivations? " +
"Enter Y or N: ");
return Util.answerIsYes();
}
/**
* Repeatedly displays constructor menu options until user makes
* a valid choice.
* @return int choice number from 1 to 6
*/
protected int constructorMenu()
{
int choice = -1;
while(choice < 1 || choice > 6)
{
System.out.println("\nChoose an action: ");
System.out.println(" 1 = add/remove a rule");
System.out.println(" 2 = print this CNF grammar");
System.out.println(" 3 = print the language of this" +
" CNF grammar");
System.out.println(" 4 = test a non-empty string");
System.out.println(" 5 = test the epsilon string");
System.out.println(" 6 = DONE with this CNF grammar");
choice = Util.readNum();
}
return choice;
}
/**
* Takes the appropriate action based on constructorMenu options.
* @param choice integer code for user's desired action
* @pre 1 <= choice <= 5
*/
protected void menuHandler(int choice)
{
Assert.pre(1 <= choice && choice <= 5,
"1 <= choice <= 5");
switch (choice)
{
case 5: // test epsilon string
if(this.startToEpsilon)
System.out.println("epsilon is accepted");
else System.out.println("epsilon is rejected");
break;
case 4: // test a non-epsilon string
testStringDialog();
break;
case 3: // print language
printLanguageDialog();
break;
case 2: // print CNF
printCNF();
break;
case 1: // add/remove a rule
ruleChangeDialog();
}
}
/**
* Asks user which type of rule change they want to make
* and carries out that request.
* @post rule array is altered to reflect addition/deletion
* of a rule, or value of startToEpsilon is possibly changed
*/
protected void ruleChangeDialog()
{
int n = -1;
while(n<0 || n>5)
{
System.out.println("Choose an option: ");
System.out.println(" 0 = add a rule, form 0, " +
"vn -> vi vj");
System.out.println(" 1 = add a rule, form 1, " +
"vn -> terminal");
System.out.println(" 2 = add a rule, form 2, " +
"start -> epsilon");
System.out.println(" 3 = remove a rule, form 0, " +
"vn -> vi vj");
System.out.println(" 4 = remove a rule, form 1, " +
"vn -> terminal");
System.out.println(" 5 = remove a rule, form 2, " +
"start -> epsilon");
n = Util.readNum();
}
switch(n)
{
case 5: // remove rule type 2, start -> epsilon
startToEpsilon = false;
System.out.println("The rule v0 -> epsilon " +
"has been removed.");
break;
case 4: // remove rule type 1, vn -> terminal
removeTypeOneDialog();
break;
case 3: // remove rule type 0, vn -> vi vj
removeTypeZeroDialog();
break;
case 2: // add rule type 2, start -> epsilon
startToEpsilon = true;
System.out.println("The rule v0 -> epsilon " +
"has been added.");
break;
case 1: // add rule type 1, vn -> terminal
addTypeOneDialog();
break;
case 0: // add rule type 0, vn -> vi vj
addTypeZeroDialog();
}
}
/**
* Queries user for n, i, and j in the rule "vn -> vi vj" and adds
* the correpsonding rule.
* @post rule array is updated
*/
protected void addTypeZeroDialog()
{
int n=-1, i=-1, j=-1;
System.out.println("Adding rule of type 0, form vn -> vi vj.");
while(n<0 || n>=numVars)
{
System.out.print("Enter value for n, the LHS variable:" +
" n = ");
n = Util.readNum();
}
while(i<1 || i>=numVars)
{
System.out.print("Enter value for i, the first " +
"RHS variable: i = ");
i = Util.readNum();
}
while(j<1 || j>=numVars)
{
System.out.print("Enter value for j, the second " +
"RHS variable: j = ");
j = Util.readNum();
}
this.addTypeZero(n,i,j);
}
/**
* Queries user for n and t in the rule "vn -> t" and adds
* the correpsonding rule.
* @post rule array is updated
*/
protected void addTypeOneDialog()
{
int n = -1;
char t = ' ';
System.out.println("Adding rule of type 1, form vn -> t.");
while(n<0 || n>=numVars)
{
System.out.print("Enter value for n, the LHS variable: " +
"n = ");
n = Util.readNum();
}
while(!alpha.contains(t))
{
System.out.print("Enter a terminal symbol for RHS: t = ");
// assume terminal = first char from the input string
t = Util.readString().charAt(0);
}
this.addTypeOne(n,t);
}
/**
* Queries user for n, i, and j, and removes rule "vn -> vi vj".
* @post rule array is updated
*/
protected void removeTypeZeroDialog()
{
int n=-1, i=-1, j=-1;
System.out.println("Removing rule of type 0, form vn -> vi vj.");
while(n<0 || n>=numVars)
{
System.out.print("Enter value for n, the LHS " +
"variable: n = ");
n = Util.readNum();
}
while(i<1 || i>=numVars)
{
System.out.print("Enter value for i, the first RHS " +
"variable: i = ");
i = Util.readNum();
}
while(j<1 || j>=numVars)
{
System.out.print("Enter value for j, the second RHS " +
"variable: j = ");
j = Util.readNum();
}
this.removeTypeZero(n,i,j);
}
/**
* Queries user for n and t, and removes rule "vn -> t".
* @post rule array is updated
*/
protected void removeTypeOneDialog()
{
int n = -1;
char t = ' ';
System.out.println("Removing rule of type 1, form vn -> t.");
while(n<0 || n>=numVars)
{
System.out.print("Enter value for n, the LHS variable: " +
"n = ");
n = Util.readNum();
}
while(!alpha.contains(t))
{
System.out.print("Enter a terminal symbol for RHS: t = ");
// assume terminal = first char from the input string
t = Util.readString().charAt(0);
}
this.removeTypeOne(n,t);
}
/**
* Queries user for max string length and prints this CNF's language.
* @post 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
*/
protected void printLanguageDialog()
{
int n = -1;
while(n<=0)
{
System.out.print("Enter a positive value for n " +
"(max derivation length): ");
n = Util.readNum();
}
boolean printDeriv = false;
System.out.print("Enter YES if you want to also print " +
"the derivations: ");
String inString = Util.readString();
if(inString.charAt(0) == 'y' || inString.charAt(0) == 'Y')
printDeriv = true;
Vector lang;
// ask whether to repeat strings with ambiguous derivations
boolean ambiguous = queryAmbiguous();
if(ambiguous)
lang = getLanguage(n);
else lang = getLanguageUnambiguous(n);
this.printLanguage(lang, printDeriv);
}
/**
* Determines whether a user-specified String is generated by this grammar.
* @post reports the result of the test and, if accepted, a derivation
* of the string
*/
protected void testStringDialog()
{
String inString;
System.out.print("Enter a string to test: ");
inString = Util.readString();
StringVarTerm result = testString(inString);
if(result!=null)
{
System.out.print(inString + " is accepted!");
System.out.print("\nDerivation: ");
result.printDerivation();
}
else System.out.println(inString + " is rejected");
}
// ** OTHER METHODS **
/**
* Prints the strings in the given Vector, preceded by "epsilon" if
* epsilon is generated by this CNF.
* @param v Vector representing the non-epsilon terminal strings
* generated by this CNF (up to some maximum derivation length)
* @param printDeriv determines whether the derivation of each
* string is also printed
* @pre v is a non-null Vector of non-null StringVarTerm objects
* @post if v is empty and if epsilon is not generated, reports that
* "the language is empty"
*/
protected void printLanguage(Vector v, boolean printDeriv)
{
StringVarTerm s;
if(v.isEmpty() && !startToEpsilon) // empty language
{
System.out.println("Language is empty!");
return;
}
System.out.println("\nLanguage strings:");
if(this.startToEpsilon)
{
System.out.print("epsilon");
if(printDeriv)
System.out.print(": v0 -> epsilon");
System.out.println();
}
// iterate thru v, printing each string
for(int i=0; i<v.size(); i++)
{
s = ((StringVarTerm)v.elementAt(i));
System.out.print(s.toPrettyString());
if(printDeriv)
{
System.out.print(": ");
s.printDerivation();
}
else System.out.println();
}
}
// ** METHODS TO CREATE PRE-DEFINED GRAMMARS **
/**
* Initializes this to be a CNF grammar equivalent to Sipser's G1 (p.100).
* @post data fields of this CNF grammar are set accordingly
*/
protected void constructC1()
{
alpha = new Alphabet("01#"); // alphabet symbols
numVars = 5;
startToEpsilon = false; // start -> epsilon not a rule
rule = new Vector[numVars][2]; // array of Vectors for rules
// Create the rule Vectors
for(int i=0; i<numVars; i++)
for(int j=0; j<2; j++)
rule[i][j] = new Vector();
// create & store the rules for this grammar
rule[0][0].add(new CNFRule(0,3,4)); // v0 -> v3 v4
rule[0][1].add(new CNFRule(0,'#')); // v0 -> #
rule[1][0].add(new CNFRule(1,3,4)); // v1 -> v3 v4
rule[1][1].add(new CNFRule(1,'#')); // v1 -> #
rule[2][1].add(new CNFRule(2,'1')); // v2 -> 1
rule[3][1].add(new CNFRule(3,'0')); // v3 -> 0
rule[4][0].add(new CNFRule(4,1,2)); // v4 -> v1 v2
}
/**
* Initializes this to be a CNF grammar equivalent to Sipser's G3 (p.103).
* @post data fields of this CNF grammar are set accordingly
*/
protected void constructC2()
{
alpha = new Alphabet("ab"); // alphabet symbols
numVars = 5; // numVars
startToEpsilon = true; // start -> epsilon is a rule
rule = new Vector[numVars][2]; // array of Vectors for rules
// Create the rule Vectors
for(int i=0; i<numVars; i++)
for(int j=0; j<2; j++)
rule[i][j] = new Vector();
// create & store the rules for this grammar
rule[0][0].add(new CNFRule(0,3,2)); // v0 -> v3 v2
rule[0][0].add(new CNFRule(0,1,1)); // v0 -> v1 v1
rule[0][0].add(new CNFRule(0,3,4)); // v0 -> v3 v4
rule[1][0].add(new CNFRule(1,3,2)); // v1 -> v3 v2
rule[1][0].add(new CNFRule(1,1,1)); // v1 -> v1 v1
rule[1][0].add(new CNFRule(1,3,4)); // v1 -> v3 v4
rule[2][0].add(new CNFRule(2,1,4)); // v2 -> v1 v4
rule[3][1].add(new CNFRule(3,'a')); // v3 -> a
rule[4][1].add(new CNFRule(4,'b')); // v4 -> b
}
/**
* Initializes this to be a CNF grammar equivalent to Sipser's G6 (p.108).
* @post data fields of this CNF grammar are set accordingly
*/
protected void constructC3()
{
alpha = new Alphabet("ab"); // alphabet symbols
numVars = 6; // numVars
startToEpsilon = false; // start -> epsilon not a rule
rule = new Vector[numVars][2]; // array of Vectors for rules
// Create the rule Vectors
for(int i=0; i<numVars; i++)
for(int j=0; j<2; j++)
rule[i][j] = new Vector();
// create & store the rules for this grammar
rule[0][1].add(new CNFRule(0,'a')); // v0 -> a
rule[0][0].add(new CNFRule(0,1,2)); // v0 -> v1 v2
rule[0][0].add(new CNFRule(0,4,5)); // v0 -> v4 v5
rule[0][0].add(new CNFRule(0,2,1)); // v0 -> v2 v1
rule[0][0].add(new CNFRule(0,2,3)); // v0 -> v2 v3
rule[1][1].add(new CNFRule(1,'a')); // v1 -> a
rule[1][0].add(new CNFRule(1,1,2)); // v1 -> v1 v2
rule[1][0].add(new CNFRule(1,4,5)); // v1 -> v4 v5
rule[1][0].add(new CNFRule(1,2,1)); // v1 -> v2 v1
rule[1][0].add(new CNFRule(1,2,3)); // v1 -> v2 v3
rule[2][1].add(new CNFRule(2,'a')); // v2 -> a
rule[2][1].add(new CNFRule(2,'b')); // v2 -> b
rule[2][0].add(new CNFRule(2,1,2)); // v2 -> v1 v2
rule[2][0].add(new CNFRule(2,4,5)); // v2 -> v4 v5
rule[2][0].add(new CNFRule(2,2,1)); // v2 -> v2 v1
rule[2][0].add(new CNFRule(2,2,3)); // v2 -> v2 v3
rule[3][0].add(new CNFRule(3,1,2)); // v3 -> v1 v2
rule[4][1].add(new CNFRule(4,'a')); // v4 -> a
rule[5][1].add(new CNFRule(5,'b')); // v5 -> b
}
/**
* Initializes this to be a CNF grammar which generates 0*10*,
* strings with exactly one '1'.
* @post data fields of this CNF grammar are set accordingly
*/
protected void constructC4()
{
alpha = new Alphabet("01"); // alphabet symbols
numVars = 4; // numVars
startToEpsilon = false; // start -> epsilon not a rule
rule = new Vector[numVars][2]; // array of Vectors for rules
// Create the rule Vectors
for(int i=0; i<numVars; i++)
for(int j=0; j<2; j++)
rule[i][j] = new Vector();
// create & store the rules for this grammar
rule[0][1].add(new CNFRule(0,'1')); // v0 -> 1
rule[0][0].add(new CNFRule(0,1,2)); // v0 -> v1 v2
rule[0][0].add(new CNFRule(0,1,3)); // v0 -> v1 v3
rule[0][0].add(new CNFRule(0,2,1)); // v0 -> v2 v1
rule[1][0].add(new CNFRule(1,1,1)); // v1 -> v1 v1
rule[1][1].add(new CNFRule(1,'0')); // v1 -> 0
rule[2][1].add(new CNFRule(2,'1')); // v2 -> 1
rule[3][0].add(new CNFRule(3,2,1)); // v3 -> v2 v1
}
/**
* Initializes this to be a CNF grammar which generates all palindromes
* over the alphabet {0,1}.
* @post data fields of this CNF grammar are set accordingly
*/
protected void constructC5()
{
alpha = new Alphabet("01"); // alphabet symbols
numVars = 6; // numVars
startToEpsilon = true; // start -> epsilon IS a rule
rule = new Vector[numVars][2]; // array of Vectors for rules
// Create the rule Vectors
for(int i=0; i<numVars; i++)
for(int j=0; j<2; j++)
rule[i][j] = new Vector();
// create & store the rules for this grammar
rule[0][1].add(new CNFRule(0,'0')); // v0 -> 0
rule[0][1].add(new CNFRule(0,'1')); // v0 -> 1
rule[0][0].add(new CNFRule(0,1,1)); // v0 -> v1 v1
rule[0][0].add(new CNFRule(0,2,2)); // v0 -> v2 v2
rule[0][0].add(new CNFRule(0,1,3)); // v0 -> v1 v3
rule[0][0].add(new CNFRule(0,2,4)); // v0 -> v2 v4
rule[1][1].add(new CNFRule(1,'0')); // v1 -> 0
rule[2][1].add(new CNFRule(2,'1')); // v2 -> 1
rule[3][0].add(new CNFRule(3,5,1)); // v3 -> v5 v1
rule[4][0].add(new CNFRule(4,5,2)); // v4 -> v5 v2
rule[5][1].add(new CNFRule(5,'0')); // v5 -> 0
rule[5][1].add(new CNFRule(5,'1')); // v5 -> 1
rule[5][0].add(new CNFRule(5,1,1)); // v5 -> v1 v1
rule[5][0].add(new CNFRule(5,2,2)); // v5 -> v2 v2
rule[5][0].add(new CNFRule(5,1,3)); // v5 -> v1 v3
rule[5][0].add(new CNFRule(5,2,4)); // v5 -> v2 v4
}
// ** TEST METHOD **
public static void main(String[] args)
{
new CNF();
}
}