Problem G: Grammar
Time Limit: 10 Second Memory Limit: 131072 KB
Bob is one of the best students of the Formal Languages class. Now he is learning about context free grammars in the Chomsky Normal Form (CNF). Such a grammar consists of:
a set of nonterminal symbols N
a set of terminal symbols T
a special nonterminal symbol, called the start symbol S
a set R of rules of the form A -> BC or A -> a, where A, B, C ∈ N, a ∈ T.
If A ∈ N, we define L(A), the language generated by A, as follows:
L(A) = { wz | w ∈ L(B), ∈ L(C), where A -> BC ∈ R } ∪ { a | A -> a ∈ R }.
The language generated by the grammar with start symbol S is defined to be L(S).
Bob must solve the following problem: for a given context free grammar in CNF, on input string x,
determine whether x is in the language generated by the grammar, L(S).
Input
The program input is from a text file. It starts with the input string x (|x|<=1000). Follows the grammar rules, in the form ABC or Aa, each on a separate line. We consider that the start symbol is always S.
The input data are correct and terminate with an end of file.
Output
The program prints 1 if the string is in the language generated by the grammar, 0 otherwise.The program prints the result to the standard output from the beginning of a line.
Hint
There are three tests. The first two use the
same grammar: SAB, Sa, Ab (SAB, Sa, Ab). For the first test the input string is a, and the
result is 1, while for the second test the input string is ab and the result is 0.
The sample is for 3 different inputs. your program should provide answer for one input. 3 samples are shown for more clarification.
Sample Input
a SAB Sa Ab ab SAB Sa Ab ab SAB Sa Ab Ba
Sample Output
1 0 0Submit