Problem D
Context-Free Grammar Parsing

Given as input a context-free grammar (CFG) and a list of strings, indicate whether each string could be generated by the grammar. For this problem, the grammar is in a restricted version of Chomsky normal form (CNF).

The grammar use production rules of the following form:

\[ V \rightarrow \{ ~ \Sigma ~ |~ VV~ \} \]

where $V$ is a set of variables and $\Sigma $ is a set of symbols. In other words, each rule indicates that one variable can produce either one symbol or two more variables.

Chomsky normal form further requires that the start variable appears nowhere in any rule production (the right hand side of a rule). In this problem, no rule may produce $\varepsilon $ (the empty string), which is why this is a restricted version of CNF.

In case you need a refresher, a CFG produces a string of (only) symbols by the following algorithm:

  • Start with only the starting variable.

  • Replace any variable with its production.

  • Repeat from step 2 until only symbols remain.

We say that the language of the grammar is all the strings that can be produced in this way by the grammar.


Input starts with a description of a grammar in restricted CNF. The first line contains an integer $1 \le n \le 200$, indicating the number of rules that follow. The following $n$ lines each contain one rule. Each rule begins with a variable, then a single space, then either a single symbol or a pair of variables. For this problem, a variable is an upper-case letter (A–Z), and a symbol is a lowercase letter (a-z). The start variable of the grammar is the first variable in the first rule of the grammar.

After the grammar is a line containing an integer $1 \le s \le 100$. Each of the following $s$ lines contains a string with $1$ to $30$ lowercase letters (a–z).


For each of the $s$ strings, output ‘yes’ if it is in the language of the grammar, or ‘no’ otherwise.

Sample Input 1 Sample Output 1
A a
B b
CPU Time limit 9 seconds
Memory limit 1024 MB
Statistics Show
Greg Hamerly
Source Baylor University Introduction to Computation Theory
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in