your program in either C or Java. The Problem Given a grammar in Chomsky Normal Form and several strings, determine whether or not each of the strings given is part of the grammar described. To simplify matters, the alphabet for each problem will be the lowercase letters, and the set of variables will be all capital letters. The start symbol will always be S. Epsilon, the empty string, will be represented by the character ‘@’. Input File Format (chomsky.in) The first line of the input file will contain a single positive integer, n (n < 100), representing
Write your program in either C or Java.
The Problem
Given a grammar in Chomsky Normal Form and several strings, determine whether or not each of the strings given is part of the grammar described.
To simplify matters, the alphabet for each problem will be the lowercase letters, and the set of variables will be all capital letters. The start symbol will always be S. Epsilon, the empty string, will be represented by the character ‘@’.
Input File Format (chomsky.in)
The first line of the input file will contain a single positive integer, n (n < 100), representing the number of grammars that are going to be described in the file.
For each grammar, the first line will have a single positive integer, v (v < 27), representing the number of variables. The next v lines will contain the rules for each variable.
For each of these lines, the first token on the line will be a positive integer r (r < 10), representing the number rules for the variable described on that line. The second token on the line will be the variable for the line, a single capital letter. For convenience, it is guaranteed that for each grammar, on the first of these lines will be the letter ‘S’, the start symbol. After the variable, there will be r tokens that follow. Each token will either be two capital letters (variables), or a single lower case letter (terminal). For the line with ‘S’, the character ‘@’ may be present to represent epsilon.
On the next line there will be a single positive integer, s, representing the number of strings to test. The next s lines will contain one string of lowercase letters or ‘@’ each. Each string will be of length 100 or less.
Output Format
For each test case, output a header as follows:
Grammar #k:
where k represents the grammar number, starting at 1.
For each of the following s lines, write the string in question, followed by a colon, followed by a space, followed by either “YES” or “NO”. For example, if the string in question were “babba” and it was NOT in the grammar, then you would output:
babba: NO
Output these lines in the order in which the strings were given in the input file.
Separate the output for each case with a blank line.
Sample Input
2
3
2 S AB BB
3 A BB a b
2 B b c
2
bcb
c
2
2 S AA @
3 A AA x y
3
@
asd
yyyy
Sample Output
Grammar #1:
bcb: YES
c: NO
Grammar #2:
@: YES
asd: NO
yyyy: YES
Step by step
Solved in 2 steps
