Trusted by +2 million users,

1000+ happy students everyday

1000+ happy students everyday

Showing pages 1 to 1 of 3 pages

Compiler ConstructionFall 2017Second AssignmentContext-Free Grammars and Top-Down ParsingDue Wednesday Oct 11, 2017 at 9 AMQuestion 1 [25 points](a) For each of the following grammars, precisely describe the language generated by the grammar. Theset of terminals T is {a, b} unless another set is specified. (16 points)(1)S → A | BA → aaaA | єB → Bbb | bAns. S = {є, aaa, aaaaaa, aaaaaaaaa, .... , ,b,bbb,bbbbb, bbbbbbb, .... }Thus S contains all strings made froma and b such that strings made from a contain a’s in thisorder: 3,6,9,... and strings made form b contain b in this order: 1, 3,5,7,9,....2S → RbRR → aRb | bRa | RR | bR | єAns. R = { є, b, ab, ba, bb, abb, bba, bab, bbb, abbb, ... }(2)S → aSbSaS | aSaSbS | bSaSaS | єS = { aba, aab, baa, aababa, aabaab, babaaa, aaabba, aaabab, .... }S contains all the strings having 2 more a’s than b’s(4)S → a S b | C Set of terminals here is T = {a, b, c}C → cc C | єAns.C = {cc, cccc, cccccc, ... }S = { ab, accb, accccb, aaccbb, ... }C contains all the strings having even number of c’sS contains all strings beginning with a and ending b, in the middle it contains strings of set C or of set S(b) Using the grammar in Part 2 above, give a derivation for the stringabbabb. Give your derivation inthree different forms: a derivation tree, a left-most derivation and a right-most derivation. (9 points)Ans.S→ RbR → aRbbR → abbR → abbRbR → abbaRbbR → abbabbR → abbabbQuestion 2 [20 points]Give a grammar that generates each of the following languages. The set of terminals T is given for eachgrammar.(1)L = {a3nb2m| m ≥ 0, n ≥ 0}. T = {a, b}Ans L→aaaL | Lbbb | є(2)L = {a2ncmbm| m ≥ 0, n ≥ 0}. T = {a, b, c}.Ans R→ cRb |є

**You’re reading a preview**

To View Complete Document

Click the button to download

Subscribe to our plans