quote this
COT-5310 Theory of Computation I Assignment 3 Florida International University School of Computing and Information Sciences 1. (20 points) Let G be a context-free grammar on alphabet Σ = {a, (,+, ∗, )} and the following production rules: S → S + T |T T → T ∗ U |U U → (S)|a (a) (10 points) Specify the parse tree and left-most derivation each of the strings “((a))” and “(a + a ∗ a) ∗ (a ∗ a + a)”. (b) (10 points) Formally prove that G is unambiguous. 2. (10 points) Convert the following CFG into an equivalent CFG in CNF. Show the intermediate steps. S → ASA|A|ε A→ aa|ε 3. (15 points) Let PDA P is represented by the following graph. q0start q1 q2 q3 q4 ε, ε→ $ ε, $→ ε 0,− → ε 1,+→ ε 0, $→ $ 0,+→ + ε, ε→ + 1, $→ $ 1,− → − ε, ε→ − 1 (a) (5 points) Write-down the 6-tuple representation of P . (b) (10 points) Convert P to its equivalent CFG describing L(P ) (Hint: You need to first convert the given PDA to the following PDA and then, use the conversion process specified in the proof of Lemma 2.27 and in class. Please note that by following the general conversion process, you will have many useless/unreachable variables that can be eliminated from your final response. The key useful variables are Aq0q6 , Aq6q4 , Aq0q7 , Aq7q4 , and Aq0q4 which is the start variable of the grammar). q0start q1 q2 q5q8 q7 q3 q6 q4 ε, ε→ $ ε, $→ ε 0,− → ε 1,+→ ε ε, ε→ + ε, ε→ − 1,− → ε ε, ε→ − 1, $→ ε ε, ε→ $ 0, $→ ε ε, ε→ $ 0,+→ ε ε, ε→ + 4. (25 points) Assuming that A = {anbmck|n,m, k ∈ Z≥0, n = 2m} and B = {anbmck|n,m, k ∈ Z≥0,m = 2k}, answer the following questions (a) (10 points) By Drawing appropriate PDAs, show that languages A and B are context-free. (b) (10 points) Use A and B to prove that the family of context-free languages are not closed under intersection (Hint: show that A∩B is not a CFL using pumping lemma for context-free languages). (c) (5 points) Use the proven claim in part b to show that the family of context-free languages are not closed under complement. 5. (15 points) Show that the following languages are context-free. (a) (7 points) {anbmck|n,m, k ∈ Z≥0,m < n + k} (b) (8 points) {anbmcbm+n2 c|n,m ∈ z≥0} 6. (15 points + 15 extra bonus points) let g be a cfg on σ = {a, b} with the following product rules. s → ss|asb|bsa|ε (a) (5 points) specify the simplest description of the language generated by g. 2 (b) (10 points) convert g to its equivalent pda recognizing l(g). (c) (15 bonus points) formally prove your claim in part a. 3 n="" +="" k}="" (b)="" (8="" points)="" {anbmcbm+n2="" c|n,m="" ∈="" z≥0}="" 6.="" (15="" points="" +="" 15="" extra="" bonus="" points)="" let="" g="" be="" a="" cfg="" on="" σ="{a," b}="" with="" the="" following="" product="" rules.="" s="" →="" ss|asb|bsa|ε="" (a)="" (5="" points)="" specify="" the="" simplest="" description="" of="" the="" language="" generated="" by="" g.="" 2="" (b)="" (10="" points)="" convert="" g="" to="" its="" equivalent="" pda="" recognizing="" l(g).="" (c)="" (15="" bonus="" points)="" formally="" prove="" your="" claim="" in="" part="" a.="">