JAVA Program

Define a context-free grammar for each of the languages described below. Then write a test program to implement the grammar as an instance of your CFG class. Each context-free grammar should be defined in a separate test program.

1. A CFG for alphabet {a,b} that recognizes the language consisting of all strings that start with an odd number of a's followed by the same number of b's. Test your program with the following input strings:

ab, aabb, aaabbb, aaabbbbb, aaaabbb

CFG CLASS BELOW TO USE TO TEST

CFG.java public class CFG { private String[] Code; private char startNT; /* * The constructor takes an array of production rules in string format. * Each element of C is expected to be of the form * "[non-terminal]=>[terminals and non-terminals]". */ public CFG(String[] C){ Code = C; startNT = C[0].charAt(0); } /* * The getStartNT method returns the char currently used as the * starting non-terminal */ public char getStartNT(){ return startNT; }

/* * The setStartNT method allows the starting non-terminal to be * changed */ public void setStartNT(char stNT){ startNT = stNT; }

/* * The processData method determines if inString is in the CFG. * wkString should be "[starting non-terminal]" */ public boolean processData(String inString, String wkString){ // + 1 to account for lambda productions // May not work for some words produced through strings // containing multiple NT's with lambda productions. // This is okay considering we can always remove lambda productions. if (wkString.length() > inString.length() + 1) return false; if (wkString.equals(inString)) return true; // for each production rule in the CFG for (int prodRule = 0; prodRule < Code.length; prodRule++){ String thisProdWkString = wkString; char NT = Code[prodRule].charAt(0); //RHS starts at 3: "[NT]=>[RHS]" String RHS = Code[prodRule].substring(3); int NTLoc = thisProdWkString.indexOf(NT); if (NTLoc == -1) continue; else{ thisProdWkString = thisProdWkString.replaceFirst("[" + NT + "]", RHS); if (processData(inString,thisProdWkString)) return true; else continue; } } return false; } }