Let M = (K, Σ, δ, s, F) be a finite state automaton, where K = {A, B}, Σ = {a,…
GATE · 2004 · ITModified — slightly modified from the official paper; see the solution
Let M = (K, Σ, δ, s, F) be a finite state automaton, where
K = {A, B}, Σ = {a, b}, s = A, F = {B}
δ(A,a) = A, δ(A,b) = B, δ(B,a) = B and δ(B,b) = A.
A grammar to generate the language accepts by M can be specified as G = (V, Σ, R, S), where V = K ∪ Σ and S = A. Which one of the following set of rules will make L(G) = L(M)?
- A.
{A → aB, A → bA, B → bA, B → aA, B → ε}
- B.
{A → aA, A → bB, B → aB, B → bA, B → ε}
- C.
{A → bB, A → aB, B → aA, B → bA, A → ε}
- D.
{A → aA, A → bA, B → bB, B → aA, A → ε}
Attempted by 6 students.
Sign up free to check your answer
Sign up freeLoading lesson…