1
Assessment details
Computing Theory COSC 1107/1105 Sample Exercise
1. Consider the grammar derivations below.
S ⇒ aSbb ⇒ aaSbbbb ⇒ aa#bbbb
S ⇒ ccBd ⇒ ccccBdd ⇒ cccc#dd
S ⇒ ccBd ⇒ ccAd ⇒ cc1A1d ⇒ cc1#1d S ⇒A⇒2A2⇒2C2⇒2cCc2⇒2c#c2
(a) From the above derivations, construct rules that must exist in any context-free grammar G for which these derivations are correct.
(b) Assuming that these are all the rules in G, give L(G) in set notation.
(c) Is the grammar G regular? Explain your answer.
(d) Is there a deterministic finite state automaton for L(G)? Explain your answer.
(e) Construct a context-free grammar for the language L2 below.
L2 ={w1 a2i cj al dk bi w2 |w1,w2 ∈{1,2}∗,|w1|=|w2|,i≥1,j,k,l≥0,j