1. Let G1 be the following context-free grammar:
| S | ⟶ | Sb | aHb | (1) (2) |
| H | ⟶ | aHbb | Kb | (3) (4) |
| K | ⟶ | cK | c | (5) (6) |
(a) Offer a precise description of L(G1), the language generated by G1.
(b) Provide some evidence for the claim that G1 is unambiguous. To do so, choose a "generic" member of L(G1), describe its derivation from S, and argue that there is no other way to derive it from S.
(c) Present an alternative CFG G'1 that generates the same language as G1 but whose only nonterminal symbols are S and K, with K having the same two productions as are in G1. (In other words, modify the grammar so that S "does the work" of both S and H in the original grammar.) Demonstrate that your grammar is ambiguous.
2. Let G2 be the following context-free grammar:
| S | ⟶ | SH | λ | (1) (2) |
| H | ⟶ | aHa | bHb | c | (3) (4) (5) |
Give a precise description of L(G2), the language generated by G2.
3. Present a context-free grammar G3 that generates the language { aj bk ck+1 b2j | j≥0, k≥1 }
4. Consider the following Chomsky Normal Form grammar G4:
| S | ⟶ | HS | a | c | (1) (2) |
| H | ⟶ | KH | b | (3) (4) |
| K | ⟶ | KS | a | (5) (6) |
Use the CYK algorithm to determine whether the string acbbc is a member of L(G4).
Specifically, fill in the cells of the matrix pictured below so that the cell in row i and column j contains Vi,j = { X ∈ {S,H,K} : X ⟹+ wi,j }, where wi,j is the substring of w (i.e., the string of interest) beginning with its i-th symbol and ending with its j-th symbol (inclusive). (Your answers are expected to include not only the answer to the question "Is w ∈ L(G)?" but also the correctly completed table.)
Recall that, for i satisfying 1≤i≤|w|, X ∈ Vi,i iff X → wi,i is a production in the grammar. Meanwhile, for i and j satisfying 1≤i<j≤|w|, X ∈ Vi,j iff there exists k, where i≤k<j, and nonterminals Y and Z such that Y ∈ Vi,k, Z ∈ Vk+1,j, and X → YZ is a production in the grammar.
1 2 3 4 5
+------+------+------+------+------+
| | | | | |
| | | | | | 1
| | | | | |
+------+------+------+------+------+
| | | | |
| | | | | 2
| | | | |
+------+------+------+------+
| | | |
| | | | 3
| | | |
+------+------+------+
| | |
| | | 4
| | |
+------+------+
| |
| | 5
| |
+------+
|
If you prefer it, you can turn the matrix upside down so that the row numbers decrease as you go down the page.
Note that some descriptions of the CYK algorithm are based upon Vi,j being defined to be the set containing those nonterminals that generate the substring of w of length i beginning at position j. A table based upon this definition would be such that each of its rows corresponds to one of the diagonals in the table as described above (and as covered in lecture and the relevant web page). If you find this variation to be easier to understand, feel free to use it, but make sure to state it explicitly in your answer.
5. Let G be this q-grammar:
| S ⟶ | bDb | cE | (1) (2) |
| D ⟶ | cS | aEc | (3) (4) |
| E ⟶ | aSb | λ | (5) (6) |
(a) Show the grammar's parse table.
(b) Show the "stack movie" illustrating the steps taken during a parse —guided by the parse table from (a)— of the string cabacbb.
(c) Let Gc be the grammar resulting from augmenting G by adding production (7): S ⟶ λ. Show that Gc is not a q-grammar. Do so by showing a pair of "successful" stack movies, in one of which production (1) is applied and in the other of which production (7) is applied in the "same circumstance" (i.e., with S at the top of the stack and b being the next input symbol).
(d) Let Gd be the grammar resulting from augmenting G by adding production (7): D → λ. Is Gd a q-grammar? If it is, explain how the parse table from (a) would be updated to account for this new production. If it is not, explain why not.
(e) (more difficult) Let Ge be the grammar resulting from replacing production (1) in G by the production (1') S → bDa. Show that Ge is not a q-grammar.