Grammar
Time Limit: 10 Seconds 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.
Sample Input
a SAB Sa Ab ab SAB Sa Ab ab SAB Sa Ab Ba
Sample Output
1 0 0Submit