Regular Grammar and Finite Automata MCQs: 12 Solved Questions with Explanations

Regular grammars turn recursive productions into transition rules, while Myhill-Nerode classes expose the memory a finite automaton must retain. Start each question by naming the state meaning or length residue, then test one accepted and one rejected string. For broader practice, continue with Finite Automata MCQs: 10 Solved DFA and NFA (GATE) or GATE CS Exam Preparation.

Translate a right-linear grammar into states before solving the MCQs

In a right-linear grammar, treat each non-terminal as a state: A -> xB is an x transition from A to B, and A -> epsilon makes A accepting.

For G0: S -> 0S | 1A and A -> 0A | epsilon, derive:

S => 0S => 00S => 001A => 0010A => 00100A => 00100.

Here q0, q1 and qd mean zero, one and at least two 1s. Input 0 loops; input 1 moves q0 -> q1 -> qd; qd loops. Thus 00100 accepts at q1, while 0101 ends at qd. Review Finite Automata: DFA vs NFA Explained.

Construct regular grammars for parity restrictions

Question 1 (UGC NET 2016)

Which regular grammar generates L = {a^n b^m | n + m is even}?

• A.

  S → S1 | S2
  S1 → a S1 | A1
  A1 → b A1 | λ
  S2 → aaS2 | A2
  A2 → b A2 | λ

• B.

  S → S1 | S2
  S1 → a S1 | a A1
  S2 → aa S2 | A2
  A1 → bA1 | λ
  A2 → bA2 | λ

• C.

  S → S1 | S2
  S1 → aaa S1 | aA1
  S2 → aaS2 | A2
  A1 → bA1 | λ
  A2 → bA2 | λ

• D.

  S → S1 | S2
  S1 → aa S1 | A1
  S2 → aaS2 | aA2
  A1 → bbA1 | λ
  A2 → bbA2 | b

Answer: D. An even sum requires even-even or odd-odd counts. S1/A1 gives pairs: S => S1 => aaS1 => aaA1 => aabbA1 => aabb. S2/A2 gives odd-odd: S => S2 => aaS2 => aaaA2 => aaab. Open the exact solved page.

Question 2 (UGC NET 2013)

Which regular grammar generates L = {a^n b^m | n is even and m is even}?

L = { aⁿ bᵐ | n is even and m is even } is given by

• A.

  S → aSb | S₁
  S₁ → bS₁a | λ

• B.

  S → aaS | S₁
  S₁ → bSb | λ

• C.

  S → aSb | S₁
  S₁ → S₁ab | λ

• D.

  S → aaS | S₁
  S₁ → bbS₁ | λ

Answer: D. S adds aa; after the switch, S1 adds bb. Hence both counts are even: S => aaS => aaaaS => aaaaS1 => aaaabbS1 => aaaabbbbS1 => aaaabbbb. Open the exact solved page.

Attach a meaning to every state or production

Question 3 (UGC NET 2014)

Which regular grammar generates L = {w | n_a(w) and n_b(w) are both even, w in {a, b}*}? Assume p, q, r and s are states.

• A. p → aq | br | λ, q → bs | ap

r → as | bp, s → ar | bq, p and s are initial and final states.

• B. p → aq | br, q → bs | ap

r → as | bp, s → ar | bq, p and s are initial and final states.

• C. p → aq | br | λ, q → bs | ap

r → as | bp, s → ar | bq p is both initial and final states.

• D. p → aq | br, q → bs | ap

r → as | bp, s → ar | bq p is both initial and final states.

Answer: C. Let p,q,r,s mean even-even, odd-even, even-odd and odd-odd. Only p accepts and has lambda. The trace abba is p -> q -> s -> q -> p; option A also accepts s. Open the exact solved page.

Question 4

Consider the grammar S → aaaS | a | aa. What is L(G)?

S → aaaS | a | aa

L(G) =?

• A.  L(G) = {w: |w| mod 3 = 0}

• B. L(G) = {w: |w| mod 3 = 1 or 2}

• C.  L(G)= L(a*)

• D. L(G) = L(a*)- (λ)

Answer: B. Recursion adds three as; termination adds one or two. Thus lengths are 3k+1 or 3k+2, k >= 0. For example, a and aa belong; epsilon and aaa do not.

Convert a grammar to the minimum-state view

Question 5 (GATE 2005)

Consider the regular grammar S → Xa | Ya, X → Za, Z → Sa | ε, Y → Wa and W → Sa. S is the start symbol, {a} is the terminal set, and {S, W, X, Y, Z} is the non-terminal set. What is the minimum number of states in an equivalent DFA?

• A. 2

• B. 3

• C. 4

• D. 5

Answer: B. 3. S => Xa => Zaa => aa gives length two. Recursion adds three, so L={a^(3k+2) | k>=0}. Residues 0, 1 and 2 need suffixes aa, a and epsilon to accept, proving they are distinct. Open the exact solved page.

Question 6 (GATE 2006)

Consider the regular grammar S → bS | aA | ε and A → aS | bA. What are the Myhill-Nerode equivalence classes for the generated language?

S → bS | aA | ϵ

A → aS | bA

The Myhill-Nerode equivalence classes for the language generated by the grammar are

• A. {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #a(w) is odd}

• B. {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #b(w) is odd}

• C. {w ∊ (a + b)* | #a(w) = #b(w) and {w ∊ (a + b)* | #a(w) ≠ #b(w)}

• D. {ϵ}, {wa | w ∊ (a + b)* and {wb | w ∊ (a + b)*}

Answer: A. Input b preserves the state; a toggles S <-> A. Only S has epsilon, so the classes have even and odd a counts. Thus baab ends at S, while babb ends at A. See DFA Minimization for GATE. Open the exact solved page.

Count Myhill-Nerode classes without drawing every arrow

Question 7 (UGC NET 2016)

Let L be the language generated by the regular expression 0*10* and accepted by the deterministic finite automaton M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has _____ equivalence classes.

• A. 3

• B. 4

• C. 5

• D. 6

Answer: A. 3. 0*10* has exactly one 1. Its residual cases are zero, one, or at least two 1s, represented by epsilon, 1 and 11. The last is dead; suffix 1 separates the first two. Open the exact solved page.

Question 8

Consider a language L defined over the alphabet Σ = {0, 1} which contains all the strings whose length is at most n. Find the number of equivalence classes of language L.

• A. n

• B. n+1

• C. n+2

• D. 2n

Answer: C. n+2. Lengths 0,1,...,n leave different allowances, giving n+1 classes. Length n+1 or more is one dead class. Thus (n+1)+1=n+2; for n=2, the classes are 0, 1, 2 and >=3.

Read the exact string shape generated by a grammar

Question 9 (ISRO 2011)

Which sentence can be generated by S → aS | bA and A → d | cA?

S -> aS | bA

A -> d | cA

• A. bccdd

• B. abbcca

• C. abcabc

• D. abcd

Answer: D. abcd. The form is a^i b c^j d, i,j>=0, and S => aS => abA => abcA => abcd. The other options break this form. Open the exact solved page.

Question 10 (UGC NET 2025)

A machine over Σ = {a, b} accepts every string that contains abb as a substring, with any binary prefix and suffix. Which grammar generates this language?

For the above specified passage, which of the following represent the grammar for the language accepted the machine?

• A. S → AabbB, A → aA | ε, B → bB | ε

• B. S → abbA, A → aA | ε | bA

• C. S → AabbA, A → aA | bA | ε

• D. S → Aabb, A → aA | bA | ε

Answer: C. The language is Sigma* abb Sigma*. The two As generate any binary prefix and suffix. For baabbab, choose ba, fixed abb, then ab. Other options restrict one side. Open the exact solved page.

Separate the grammar's form from the language class

Question 11

Consider the grammar S → a | b | aTa | bTb and T → aT | bT | ε. Select the wrong option.

S→ a | b | aTa | bTb

T→ aT | bT | ϵ

Select the wrong option.

• A. The language generated by the grammar is regular.

• B. The language generated by the grammar is a(a+b)*a + b(a+b)*b.

• C. The language generated by the grammar can be accepted by NFA.

• D. The given grammar is CFG.

Answer: B. The language contains a, b, and longer strings with matching endpoints. B omits the singletons. The full expression is a + b + a(a+b)*a + b(a+b)*b, which is regular; the grammar is also context-free.

Question 12 (GATE 2000)

Let L denote the language generated by the grammar S -> 0S0 | 00. Which of the following is true?

• A. L = 0+

• B. L is regular but not 0+

• C. L is context free but not regular

• D. L is not context free

Answer: B. The base is 00; recursion adds two zeros. Thus L={0^(2k) | k>=1}=(00)+: 00, 0000, and no odd length. It is regular but differs from 0+. Open the exact solved page.

The short version

Track parity as a state pair, convert recursive length changes into residues, and count residual languages rather than productions. Test one accepted and one rejected string before choosing. For a structured Theory of Computation path, continue with GATE Guidance by Sanchit Sir.