Write a context-free grammar for L = anbm, where n = m+2

Write a context-free grammar for L = anbm, where n = m+2 (i.e., string has 2 more a’s than b’s).

2. Show a derivation tree for w = aabbbb  using the grammar given:

S -> AB | λ

A -> aB

B -> Sb

Upload your solution, which should be a PDF or JPEG image that clearly identifies the question number and gives the appropriate solution in the form of a hand-drawn or software-created derivation tree. Do NOT use ASCII drawn trees or text descriptions

3. Is the following grammar an S-grammar? Explain why or why not.

S -> aR

R -> aAB

A -> aAb | b

B -> b

4. Eliminate the variable B from the grammar given:

S -> abAB | ba

A -> aaa

B -> aA | bb

Your solution should be a complete grammar, equivalent to this one, without the variable B.

5. Eliminate all useless productions from the grammar given:

S -> abS | abA | abC

A -> cd

B -> ac

C -> dC

Your solution should be a complete grammar, equivalent to this one, with useless productions removed.

6. Eliminate all λ-productions from the grammar given:

S -> ABCd

A -> BC

B -> bB | λ

C -> cC | λ

Your solution should be a complete grammar, equivalent to this one, with lambda productions removed.

7. Convert the grammar given into Chomsky Normal Form (CNF)

S -> aSb | Sab | ab

Your solution should be a complete grammar, equivalent to this one, in Chomsky Normal Form.

View keyboard shortcuts

EditViewInsertFormatToolsTable

12pt

Paragraph

8. Convert the grammar given into Greibach Normal Form (GNF)

S -> ab | aS | aaS | aSS

Your solution should be a complete grammar, equivalent to this one, in Greibach Normal Form

9. Construct a PDA that accepts the language L = {bnabn: n≥1}. Give your solution in the form of a transition graph.

Upload your solution, which should be a PDF or JPEG image that clearly identifies the question number and gives the appropriate solution in the form of a hand-drawn or software-created transition graph. Do NOT use ASCII drawn transition graphs or text descriptions

10. Show the sequence of instantaneous descriptions for the string aabaa as processed by the PDA given here. Conclude by stating whether the string will be accepted or rejected.