|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object finiteAutomata.CNF
public class CNF
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).
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 |
---|
protected Alphabet alpha
protected int numVars
protected boolean startToEpsilon
protected java.util.Vector[][] rule
Constructor Detail |
---|
public CNF()
public CNF(java.lang.String a, int n, boolean b, java.util.Vector[][] r)
a
- String representation of the desired alphabet with
characters listed in the desired lexicographic ordern
- int number of desired variablesb
- true iff "v0 -> epsilon" is to be a ruler
- 2-dimensional array of Vectors of CNFRule objectsMethod Detail |
---|
public void addTypeOne(int n, char t)
n
- integer specifying LHS variablet
- char specifying terminal symbol for RHSpublic void addTypeZero(int n, int i, int j)
n
- integer specifying LHS variablei
- integer specifying first RHS variablej
- integer specifying second RHS variablepublic java.util.Vector getLanguage(int maxLength)
maxLength
- int upper bound on string length
public java.util.Vector getLanguageUnambiguous(int maxLength)
maxLength
- int upper bound on string length
public boolean isValidVariable(int i)
i
- int variable number to be tested
public void printCNF()
public void printRules()
public void removeTypeOne(int n, char t)
n
- integer specifying LHS variablet
- char specifying terminal symbol for RHSpublic void removeTypeZero(int n, int i, int j)
n
- integer specifying LHS variablei
- integer specifying first RHS variablej
- integer specifying second RHS variablepublic StringVarTerm testString(java.lang.String s)
s
- String to be tested
protected boolean queryPredefined()
protected void predefinedDialog()
protected java.lang.String queryAlphabet()
protected int queryNumVars()
protected boolean queryAmbiguous()
protected int constructorMenu()
protected void menuHandler(int choice)
choice
- integer code for user's desired actionprotected void ruleChangeDialog()
protected void addTypeZeroDialog()
protected void addTypeOneDialog()
protected void removeTypeZeroDialog()
protected void removeTypeOneDialog()
protected void printLanguageDialog()
protected void testStringDialog()
protected void printLanguage(java.util.Vector v, boolean printDeriv)
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 printedprotected void constructC1()
protected void constructC2()
protected void constructC3()
protected void constructC4()
protected void constructC5()
public static void main(java.lang.String[] args)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |