JAVA or C++ 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

Sample test program for CFG class

// Test Context-Free Grammar Class

import java.io.*;

public class TestCFG

{

public static void main(String[] args)

{

// Language: strings that contain 0+ b's, followed by 2+ a's,

// followed by 1 b, and ending with 2+ a's.

String[] C = {"S=>bS",

"S=>aaT",

"T=>aT",

"T=>bU",

"U=>Ua",

"U=>aa"};

String inString, startWkString;

boolean accept1;

CFG CFG1 = new CFG(C);

if(args.length >= 1)

{

// Input string is command line parameter

inString = args[0];

char[] startNonTerm = new char[1];

startNonTerm[0] = CFG1.getStartNT();

startWkString = new String(startNonTerm);

accept1 = CFG1.processData(inString, startWkString);

System.out.println(" Accept String? " + accept1);

}

} // end main

} // end class