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.

A CFG for alphabet {a,b} that recognizes the language consisting of all strings of length 1 or greater that do not contain the substring aa. Test your program with the following input strings:

abba, abbabaaa, abaabab, bababbab, bbbabba

CFG CLASS BELOW TO TEST WITH

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; } }