Theory of Computation 1 Consider the grammar G S aSbS S

Theory of Computation:

1. Consider the grammar G = { S -> aSbS, S -> bSaS, S -> cS, S -> e} (10 pts)

a) Give a derivation for string “aababcbc”

b) Give a derivation for string “bbacbcaa”

2). Construct context free grammars that generate the following language (10 pts)

L = {aⁿbⁿc^kd^k | n, k = 0, 1, 2, 3, ...}

3). Using the G you have generated in 2), give the derivation for string “aabbcd” (5 pts)

4). For the derivation you have done in 3), produce the corresponding parse tree. (5 pts)

5). Consider the following grammar G (10 pts)

G = { S->A, S->B, S->AB, A->aA, B->bB, A->e, B->e}

a) Is G ambiguous? Why? (Prove it)

b) If G is ambiguous, can you make changes to G to make it unambiguous? List your changes.

For aababcbc

S -> aSbS Substituting s with S -> aSbS the string becomes

S -> aaSbSbS Substituting s with S -> e the string becomes

S -> aabSbS Substituting s with S -> aSbS the string becomes

S -> aabaSbSbS Substituting s with S ->e the string becomes

S -> aababSbS Substituting s with S ->cS the string becomes

S -> aababcSbS Substituting s with S ->e the string becomes

S -> aababcbS Substituting s with S ->cS the string becomes

S -> aababcbcS Substituting s with S ->e the string becomes

aababcbc

For bbacbcaa

S -> bSaS Substituting s with S ->bSaS the string becomes

S -> bbSaSaS Substituting s with S ->e the string becomes

S -> bbaSaS Substituting s with S ->e the string becomes

S -> bbaSaS Substituting s with S ->cS the string becomes

S -> bbacSaS Substituting s with S ->bSaS the string becomes

S -> bbacbSaSaS Substituting s with S ->cS the string becomes

S -> bbacbcSaSaS Substituting all s with S ->e the string becomes

S -> bbacbcaa