|
|||||||||
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. |
private 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. |
private void |
addTypeZeroDialog()
Queries user for n, i, and j in the rule "vn -> vi vj" and adds the correpsonding rule. |
private void |
constructC1()
Initializes this to be a CNF grammar equivalent to Sipser's G1 (p.100). |
private void |
constructC2()
Initializes this to be a CNF grammar equivalent to Sipser's G3 (p.103). |
private void |
constructC3()
Initializes this to be a CNF grammar equivalent to Sipser's G6 (p.108). |
private void |
constructC4()
Initializes this to be a CNF grammar which generates 0*10*, strings with exactly one '1'. |
private void |
constructC5()
Initializes this to be a CNF grammar which generates all palindromes over the alphabet {0,1}. |
private int |
constructorMenu()
Repeatedly displays constructor menu options until user makes a valid choice. |
java.util.Vector |
getLanguage(int maxSteps)
Returns all non-empty terminal strings derivable in a given number of steps. |
java.util.Vector |
getLanguageUnambiguous(int maxSteps)
Returns all non-empty terminal strings derivable in a given number of steps, without repetitions. |
boolean |
isValidVariable(int i)
Tests whether a given integer is a valid variable number. |
static void |
main(java.lang.String[] args)
|
private void |
menuHandler(int choice)
Takes the appropriate action based on constructorMenu options. |
private 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. |
private 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. |
private void |
printLanguageDialog()
Queries user for max string length and prints this CNF's language. |
void |
printRules()
Pretty-prints the rule set. |
private java.lang.String |
queryAlphabet()
Queries user for alphabet of terminal symbols. |
private boolean |
queryAmbiguous()
Asks user if they want to have strings with ambiguous derivations be repeated. |
private int |
queryNumVars()
Prints constructor menu header and queries user regarding number of variables. |
private 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. |
private 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. |
private void |
removeTypeZeroDialog()
Queries user for n, i, and j, and removes rule "vn -> vi vj". |
private 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 terminal string which can be generated by this CNF. |
private 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 maxSteps)
maxSteps
- int upper bound on derivation length
public java.util.Vector getLanguageUnambiguous(int maxSteps)
maxSteps
- int upper bound on derivation 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
private boolean queryPredefined()
private void predefinedDialog()
private java.lang.String queryAlphabet()
private int queryNumVars()
private boolean queryAmbiguous()
private int constructorMenu()
private void menuHandler(int choice)
choice
- integer code for user's desired actionprivate void ruleChangeDialog()
private void addTypeZeroDialog()
private void addTypeOneDialog()
private void removeTypeZeroDialog()
private void removeTypeOneDialog()
private void printLanguageDialog()
private void testStringDialog()
private 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 printedprivate void constructC1()
private void constructC2()
private void constructC3()
private void constructC4()
private 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 |