Question

Automata Theory and Formal Languages

Problems 1: Consider the following two grammars.

Grammar G1- S → aSb / ∈ Grammar G2- S → aAb / ∈, A → aAb / ∈

a. is G1=G2

b. What is the grammar generated by the expression

Problem 2: Let us consider the grammar.

G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } )

Derive aaabbb

Problem 3: Suppose we have the following grammar.

G: N = {S, A, B} T = {a, b} P = {S → AB, A → aA|a, B → bB|b}

What language is generated by this grammar?

Problem − Suppose, L (G) = {am bn | m ≥ 0 and n > 0}. We have to find out the grammar G which produces L(G).

Solution

Since L(G) = {am bn | m ≥ 0 and n > 0}

the set of strings accepted can be rewritten as −

L(G) = {b, ab,bb, aab, abb, …….}. Show your solution.

Answer 1