Part B:

Note: Needs to be done in Java Programming

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

2. 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

3. A CFG for alphabet {a,b} that recognizes the language consisting of all strings that contain exactly one b, have 2N a's (N >= 0, N is an integer) before the b, and 2N+1 a's after the b. Test your program with the following input strings:

ba, aaabaaaa, aabaaa, abaa, aaaabaaa

4. A CFG for alphabet {x,y,z} that recognizes the language consisting of all strings that start with z, followed by N x's (N >= 0), followed by twice as many y's, and ending with z. Test your program with the following input strings:

zz, zxxyyz, zxxyyyy, zxyyz, zxxyyyyz

For each context-free grammar in Part B, turn in your definition of the grammar, the source code for the test program, and the output for the test input strings.