CMSC330: Discussion Material (10/1)October 1, 20081) What langage does the following grammar generate:S → aSbS | bSaS | Answer: The set of all strings with an equal number of a’s and b’s.2)a) Give the grammar that generates the language of the regular expression: 0*1(0 | 1)*Answer:S → A1BA → 0A | B → 0B | 1B | b) Give the leftmost and rightmost derivations of the following strings using the grammar from part a):i) 1001Answer:Leftmost: S → A1B → 1B → 10B → 100B → 1001B → 1001Rightmost: S → A1B → A10B → A100B → A1001B → A1001 → 1001ii) 00011Answer:Leftmost: S → A1B → 0A1B → 00A1B → 000A1B → 0001B → 00011B → 00011Rightmost: S → A1B → A11B → A11 → A011 → A0011 → A00011 → 00011c) Give the parse trees for the strings in part b).i) Answer:1ii) Answer:3) Design a context free grammar for the following language: {aibjck| i 6= j or j 6= k}Answer:S → RC | ATR → aRb | XX → aA | bBT → bT c | YY → bB | cCA → aA | B → bB | C → cC | Note: The important productions rules here are for the symbols R and T. R enforces the constraint i 6= jand T enforces the constraint j 6= k. The start symbol just ensures that one or the other must be true forthe string to be in the language of this grammar.4) Given the following grammar:S → aS | aSb | a) Is this grammar ambiguous? Why?Answer: Yes. The string aab has two parse tree s, leftmost derivations, and rightmost derivations.b) Redesign the grammar to be unambiguous.Answer:S → aSb | AA → Aa | Note: This is the grammar for the language ambn| m ≥ n5) Construct a NFA for the following grammar:S → aA | BA → aaBB → bB | a2Answer:Note: The grammar must be right or left-linear to perform this conversion. This grammar is
View Full Document
Unlocking...