3220：Context-Free Languages

Context-free grammars (CFG) are a powerful method of describing languages. The syntax of most programming languages including C, C++, Java and Pascal, compilers for which are provided in this online judge system, is specified using CFGs.

In this problem, we work with CFGs in a generative manner. A CFG consists of a set of production rules for transforming strings. Every rule is of the form

V → w

where V is a symbol and w is a string of symbols. Symbols are classified into terminals and variables. In the rule above, V is restricted to be a variable, while w can contain terminals and/or variables. The term “context-free” expresses the fact that V can always be replaced by w, regardless of the context in which it occurs. Among variables, exactly one of them is designated as the start variable. To generate a string using the CFG, one begins with a string consisting of only a single start variable, and then applies the rules successively and arbitrarily to rewrite the string until only terminals are left.

For example, the alphabet of terminals consists of z, the start variable is S and we we have the following rules:

1. S → CB
2. S → ZZ
3. A → CB
4. A → ZZ
5. B → ZZ
6. C → BA
7. Z → z

then we start with S, and we can choose a rule to apply to it. If we choose rule 1, we replace S with CB and obtain the string CB. If we then choose rule 6, we replace C with BA and obtain the string BAB. If we now choose rule 4, we replace A with ZZ and obtain the string BZZB. We can write this series of choice more briefly, using symbols: S ⇒ CB ⇒ BAB ⇒ BZZB ⇒ ZZZZB ⇒ ZZZZZZ ⇒ zZZZZZ ⇒ zzZZZZ ⇒ zzzZZZ ⇒ zzzzZZ ⇒ zzzzzZ ⇒ zzzzzz. The language of the grammar is the set of all strings consisting of twice an odd number of z’s.

Given a CFG and some strings, determine whether each string belongs to the language of the grammar.

To make everything brief, we group together all rules with the same variable to the left of “→”  in the CFG. For example, we group the following three rules

S → u
S → v
S → w

into

S → u | v | w

And the CFG is given in a special form called Chomsky normal form (CNF). A CFG in CNF only contains rules of the form

A → BC
A → a

where a is any terminal and A, B, and C are any variables except that B and C may not be the start variable. CNF also permits the rule S → ε, where S is the start variable and ε represents the empty string, so that the CFG can generate the empty string. We ignore this case just for this problem.

The input contains exactly one CFG in CNF and no more than 50 strings. We use single lowercase letters as terminals and single uppercase letters as variables. S will always be the start variable. The CFG is given in several lines. A line contains all production rules for one variable grouped together as described above. “→” will be replaced by “->”. Not all possible variables are involved in the CFG, but every involved one will has at least one production rule. The CFG ends with a line containing only a single “#”. Following the CFG come the strings, one on a separate line. The input ends where no more strings can be found. Spaces and blank lines will not show up in the input.

For each string, output exactly one line. If the string belongs to the language of the given CFG, the line should read “YES” (without quotes); otherwise it should read “NO” (without quotes).