Homework 11 Context-Free Grammars 1 CS 341 Homework 11 Context-Free Grammars 1. Consider the grammar G = (V, Σ, R, S), where V = {a, b, S, A}, Σ = {a, b}, R = { S → AA, A → AAA, A → a, A → bA, A → Ab }. (a) Which strings of L(G) can be produced by derivations of four or fewer steps? (b) Give at least four distinct derivations for the string babbab. (c) For any m, n, p > 0, describe a derivation in G of the string bmabnabp. 2. Construct context-free grammars that generate each of these languages: (a) {wcwR : w ∈ {a, b}*} (b) {wwR : w ∈ {a, b}*} (c) {w ∈ {a, b}* : w = wR} 3. Consider the alphabet Σ = {a, b, (, ), ∪, *, ∅}. Construct a context-free grammar that generates all strings in Σ* that are regular expressions over {a, b}. 4. Let G be a context-free grammar and let k > 0. We let Lk(G) ⊆ L(G) be the set of all strings that have a derivation in G with k or fewer steps. (a) What is L5(G), where G = ({S, (, )}, {(, )}, {S → ε, S → SS, S → (S) })? (b) Show that, for all context-free grammars G and all k > 0, Lk(G) is finite. 5. Let G = (V, Σ, R, S), where V = {a, b, S}, Σ = {a, b}, R = { S → aSb, S → aSa, S → bSa, S → bSb, S → ε }. Show that L(G) is regular. 6. A program in a procedural programming language, such as C or Java, consists of a list of statements, where each statement is one of several types, such as: (1) assignment statement, of the form id := E, where E is any arithmetic expression (generated by the grammar using T and F that we presented in class). (2) conditional statement, e.g., "if E < E then statement", or while statement , e.g. "while E < E do statement". (3) goto statement; furthermore each statement could be preceded by a label. (4) compound statement, i.e., many statements preceded by a begin, followed by an end, and separated by ";". Give a context-free grammar that generates all possible statements in the simplified programming language described above. 7. Show that the following languages are context free by exhibiting context-free grammars generating each: (a) {ambn : m ≥ n}Homework 11 Context-Free Grammars 2 (b) {ambncpdq : m + n = p + q} (c) {w ∈ {a, b}* : w has twice as many b's as a's} (d) {uawb : u, w ∈ {a, b}*, |u| = |w|} 8. Let Σ = {a, b, c}. Let L be the language of prefix arithmetic defined as follows: (i) any member of Σ is a well-formed expression (wff). (ii) if α and β are any wff's, then so are Aαβ, Sαβ, Mαβ, and Dαβ. (iii) nothing else is a wff. (One might think of A, S, M, and D as corresponding to the operators +, -, ×, /, respectively. Thus in L we could write Aab instead of the usual (a + b), and MSabDbc, instead of ((a - b) × (b/c)). Note that parentheses are unnecessary to resolve ambiguities in L.) (a) Write a context-free grammar that generates exactly the wff's of L. (b) Show that L is not regular. 9. Consider the language L = {amb2nc3ndp : p > m, and m, n ≥ 1}. (a) What is the shortest string in L? (b) Write a context-free grammar to generate L. Solutions 1. (a) We can do an exhaustive search of all derivations of length no more than 4: S Þ AA Þ aA Þ aa S Þ AA Þ aA Þ abA Þ aba S Þ AA Þ aA Þ aAb Þ aab S Þ AA Þ bAA Þ baA Þ baa S Þ AA Þ bAA Þ bAa Þ baa S Þ AA Þ AbA Þ abA Þ aba S Þ AA Þ AbA Þ Aba Þ aba S Þ AA Þ Aa Þ aa S Þ AA Þ Aa Þ bAa Þ baa S Þ AA Þ Aa Þ Aba Þ aba S Þ AA Þ AbA Þ abA Þ aba S Þ AA Þ AbA Þ Aba Þ aba S Þ AA Þ AAb Þ aAb Þ aab S Þ AA Þ AAb Þ Aab Þ aab Many of these correspond to the same parse trees, just applying the rules in different orders. In any case, the strings that can be generated are: aa, aab, aba, baa. (b) Notice that A Þ bA Þ bAb Þ bab, and also that A Þ Ab Þ bAb Þ bab. This suggests 8 distinct derivations: S Þ AA Þ AbA Þ AbAb Þ Abab Þ* babbab S Þ AA Þ AAb Þ AbAb Þ Abab Þ* babbab S Þ AA Þ bAA Þ bAbA Þ babA Þ* babbab S Þ AA Þ AbA Þ bAbA Þ babA Þ* babbab Where each of these four has 2 ways to reach babbab in the last steps. And, of course, one could interleave the productions rather than doing all of the first A, then all of the second A, or vice versa. (c) This is a matter of formally describing a sequence of applications of the rules in terms of m, n, p that will produce the string bmabnabp. S Þ /* by rule S → AA */Homework 11 Context-Free Grammars 3 AA Þ* /* by m applications of rule A → bA */ bmAA Þ /* by rule A → a */ bmaA Þ* /* by n applications of rule A → bA */ bmabnA Þ* by p applications of rule A → Ab */ bmabnAbp Þ /* by rule A → a */ bmabnabp Clearly this derivation (and some variations on it) produce bmabnabp for each m, n, p. 2. (a) G = (V, Σ, R, S) with V = {S, a, b, c}, Σ = {a, b, c}, R = { S → aSa S → bSb S → c }. (b) Same as (a) except remove c from V and Σ and replace the last rule, S → c, by S → ε. (c) This language very similar to the language of (b). (b) was all even length palindromes; this is all palindromes. We can use the same grammar as (b) except that we must add two rules: S → a S → b 3. This is easy. Recall the inductive definition of regular expressions that was given in class : 1. ∅ and each member of Σ is a regular expression. 2. If α , β are regular expressions, then so is αβ 3. If α , β are regular expressions, then so is α∪β. 4. If α is a regular expression, then so is α*. 5. If α is a regular expression, then so is (α). 6. Nothing else is a regular expression. This definition provides the basis for a grammar for regular expressions: G = (V, Σ, R, S) with V = {S, a, b, (, ), ∪, …
View Full Document
Unlocking...