Question

9. Mark the best description (smallest language class) for each of the following lang • R if it is regular • C if it is context free, but not regular . N if it is "bigger than" context free You do not have to prove your answer. L = {www: we {a,b}"} L2 = {a" : n > 2, m < 5} L3 = {a"m : n + m is even } LA = {w:na(w) + no(w) = n(w)} Ls = {a" m:n sms 4n} L = {a"b"C": n 2 0} 4 ම ම ම යි 10. Consider the following CFG, with these 5 productions: S - Sb aSSSSa SaS b (a) Show the CFG is ambiguous by giving two leftmost derivations of the string abbb Label the steps using the production numbers 1-5. (b) Show the CFG is ambiguous by giving two different derivation trees for the string babb.

Answer 1

I hope the pictures are self explanatory

I push w into stack, pop every element compare 4. - f wwRw: we {a,b3" } → N Let w for wr.now, nothing remain rem L2= { anim : n7,2 ms 5} R. 23 = { anom: nem is even} → R 14 = {w: na(w) + no (W) = nc (W)} » e pus 1.5 = {anom: namsun? → [reeds memory to check ms an] 2 push a's and b's into stack, L for every c pop ad b ] 46 = 8 anbrennt more than 2 comparison (same) is not a CFLT
  
10. a) s sblass Issalsas/b String: abb s sb assb absb abbb [rule 1] [rule 2 ] [rule 5 ] rule 5 YAVI abbb Parse tree s ass asbs abbs abbb [rule 2 ] [rule 1] rule 5 ] [rule 5 ] So ambiguous. abbb b) String: babb 0 S Sas →bas y basb → babb [rule 4 ] [rule 5 ] [rule 1] [rule 5] 0 s sb [rule 1] → Sasb [rule 4 ] basb [rule 5] → babb [rule 5 ] So ambiguous.