package finiteAutomata; /** * Rules for the CNF class. * *

There are three types of rules allowed in a CNF grammar. Type 0 * rules transform a variable to a pair of variables; type 1 rules transform * a variable to a terminal symbol; and type 2 rules transform the start * variable to the empty string (epsilon). The CNFRule class is used to * represent rules of types 0 and 1. * *

Data Fields: A CNFRule has a "type" (integer code 0 or 1), three integer * variables "var1", "var2", "var3", and a char variable "term" (terminal * symbol). * *

Type 0 rules are form vn -> vi vj where i and j are non-zero. * In this case, type = 0, var1 = n, var2 = i, var3 = j, and "term" is * irrelevant. * *

Type 1 rules are form vn -> t. In this case, type = 1, * var1 = n, term = t, and "var2", "var3" are irrelevant. * * @author Barbara Wahl * @version Fall 2007 */ public class CNFRule { // ** DATA FIELDS ** /** * indicates type 0 or type 1 */ protected int type; /** * left-hand-side variable */ protected int var1; /** * first right-hand-side variable (for type 0) */ protected int var2; /** * second right-hand-side variable (for type 0) */ protected int var3; /** * right-hand-side terminal symbol (for type 1) */ protected char term; // ** CONSTRUCTORS ** /** * 3-parameter constructor for type 0 rule, "vn -> vi vj". * @param n LHS variable * @param i first RHS variable * @param j second RHS variable * @pre n >= 0, i > 0, j > 0 * @post creates the type 0 CNFRule for "vn -> vi vj" (term = '-') */ public CNFRule(int n, int i, int j) { Assert.pre(n >= 0, "n is non-negative"); Assert.pre(i > 0, "i is positive"); Assert.pre(j > 0, "j is positive"); type = 0; var1 = n; var2 = i; var3 = j; term = '-'; // irrelevant } /** * 2-parameter constructor for type 1 rule, "vn -> t". * @param n LHS variable * @param t terminal symbol * @pre n >= 0 * @post creates the type 1 CNFRule for "vn -> t" * (var2 = var3 = '-') */ public CNFRule(int n, char t) { Assert.pre(n >= 0, "n is non-negative"); type = 1; var1 = n; var2 = -1; // irrelevant var3 = -1; // irrelevant term = t; } /** * Copy constructor. * @param current CNFRule to be copied * @pre current is not null * @post constructs a new CNFRule with same attributes as current */ public CNFRule(CNFRule current) { term = current.term; type = current.type; var1 = current.var1; var2 = current.var2; var3 = current.var3; } // ** PUBLIC METHODS ** /** * Returns the type. * @return int type */ public int type() { return type; } /** * Returns var1, the LHS variable. * @return int var1 */ public int var1() { return var1; } /** * Returns var2, the first RHS variable (or '-' if type 1). * @return int var2 */ public int var2() { return var2; } /** * Returns var3, the second RHS variable (or '-' if type 1). * @return int var3 */ public int var3() { return var3; } /** * Returns term, the terminal symbol on RHS (or '-' if type 0). * @return char term */ public char term() { return term; } /** * Returns a pretty String representation of this rule. * @return String for pretty-printing the rule */ public String toString() { StringBuffer s; s = new StringBuffer("v"+var1+" -> "); if(type==0) s.append("v" + var2 + " v" + var3); else s.append(term); return s.toString(); } /** * Tests whether this CNFRule and the given CNFRule are logically equal. * @param other CNFRule to compare with this * @return true iff the two rules are logically equivalent * @pre other is a non-null CNFRule object */ public boolean equals(Object other) { CNFRule that = (CNFRule) other; if(type == 0) return(that.type == 0 && var1 == that.var1 && var2 == that.var2 && var3 == that.var3); else return(that.type == 1 && var1 == that.var1 && term == that.term); } // ** TEST METHOD ** public static void main(String[] args) { // create and print some rules CNFRule[] arr = new CNFRule[10]; arr[0] = new CNFRule(0,1,2); arr[1] = new CNFRule(0,1,2); arr[2] = new CNFRule(0,2,1); arr[3] = new CNFRule(0,1,3); arr[4] = new CNFRule(0,2,2); arr[5] = new CNFRule(3,1,2); arr[6] = new CNFRule(0,'x'); arr[7] = new CNFRule(1,'y'); arr[8] = new CNFRule(0,'x'); arr[9] = new CNFRule(0,'y'); for(int i=0; i<10; i++) System.out.println("Rule " + i + ": " + arr[i]); // look for equal rules for(int i=0; i<9; i++) for(int j=i+1; j<10; j++) if(arr[i].equals(arr[j])) System.out.println("rules " + i + " and " + j + " are equal"); // try violating a precondition (uncomment to try) // CNFRule badRule = new CNFRule(0,0,1); } }