1) (15 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 (5 points) Specify the parse tree and left-most derivation each of the strings “((a))” and “(a + a ∗ a) ∗ (a ∗ a + a)”

1) (15 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

1. 1. (5 points) Specify the parse tree and left-most derivation each of the strings “((a))” and “(a + a ∗ a) ∗ (a ∗ a + a)”.
   2. (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.

 

start

q

0

ε, ε → $

0, − → ε 1, + → ε

q

1

ε, $ → ε

q

4

ε, ε → +

0, + → + 0, $ → $

1, $ → $ 1, − → − ε, ε → −

q2

q3

 

 

1. 1. (5 points) Write-down the 6-tuple representation of P .
   2. (5 points) Describe the language accepted by this PDA.
   3. (10 points) Prove that the following context-free grammar generates the language described in part b.

S → SS|0S1|1S0|ε

4. (50 points) Show that the following languages are context-free either by writing a grammar that generates them or by drawing a PDA that accepts them.
   1. (5 points) {wuw^R|u, w ∈ {0, 1}∗} (write a grammar)
   2. (5 points) {w|w = w^R ∧ |w| is odd} (write a grammar)
   3. (10 points) {aⁿb^mc^k|n, m, k ∈ Z_≥0, m = k ∨ n = 3k ∨ 2n = 3m} (write a grammar)
   4. (10 points) {aⁿb^mc^k|n, m, k ∈ Z_≥0, m =/  n + k} (write a grammar)
   5. (5 points) {aⁿb^mc^k|n, m, k ∈ Z_≥0, n = 2m} (draw a PDA) (f)  (5 points) {aⁿb^mc^k|n, m, k ∈ Z_≥0, m = 2k} (draw a PDA)

(g)  (10 points) {aⁿb^mc^l   2     J|n, m ∈ Z_≥0} (draw a PDA)

5. (10 points) Convert the PDA of question 3 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 A_q0q6 , A_q6q4 , A_q0q7 , A_q7q4 , and A_q0q4 which is the start variable of the grammar).