Simplification of CFG MCQs: 12 Solved Questions with Explanations

CFG simplification questions test more than one definition. You must identify nullable, unit, generating, and reachable variables, preserve the language, and count the final useful productions. The questions test nullable, unit, generating, and reachable variables, preserve the language, and count final useful productions. Attempt them here, then continue with the Simplification of CFG practice set.

Simplification rules to keep beside the quiz

Use this four-part checklist:

• An epsilon production has the form A → ε.

• A unit production has one variable alone on the right, such as A → B.

• A non-generating variable cannot derive any string made entirely of terminals.

• An unreachable variable cannot be reached from the start variable S.

Use this order: epsilon productions, unit productions, then useless symbols and productions. An earlier removal can create a later cleanup opportunity. Attempt each item before reading its answer. If the terms feel mixed up, revise these Context-Free Grammar MCQs first.

Useless symbols and unit productions

Question 1

Stem: Which is equivalent CFG without useless symbols for the given grammar:

S → PQ | p , P → p

Options:

• A. S → PQ

• B. S → p

• C. S → P , P → p

• D. S → P | p , P → p

Answer: B. Test generation first. Q has no production, so delete the non-generating rule S → PQ. Now P is unreachable from S, so delete P → p. Only S → p remains.

Question 2

Stem: Consider the following productions:

P₁: A → B

P₂: A → a

Here, A and B are non-terminals, and a is a terminal. Select the correct option.

Options:

• A. Both P₁ and P₂ are unit productions

• B. P₁ is a unit production, but P₂ is not a unit production

• C. P₁ is not a unit production, but P₂ is a unit production

• D. Neither P₁ nor P₂ is a unit production

Answer: B. A → B has exactly one non-terminal on its right, so it is unit. A → a produces a terminal and is not unit. One symbol is insufficient; that symbol must be a variable.

Question 3

Stem: Consider the CFG G = (V, T, P, S) with the following productions:

S → AB | a

A → a

Let G′ be an equivalent CFG with no useless symbols. What is the minimum number of productions in G′?

Options:

• A. 1

• B. 2

• C. 3

• D. 5

Answer: A. As in Question 1, test generating before reachable. B has no production, so delete S → AB. This makes A unreachable, so delete A → a. Only S → a remains, giving one production.

Epsilon removal and the safest elimination order

Question 4

Stem: Consider the following grammar G:

S → aAb | ab

A → aAb | ε

Select the correct option.

Options:

• A. The grammar is unambiguous

• B. There exists an equivalent grammar for G without any ε-production

• C. The grammar G contains a unit production

• D. None of the above

Answer: B. Since A is nullable, add A → ab. The epsilon-free grammar is S → aAb | ab and A → aAb | ab. A is false because S ⇒ ab and S ⇒ aAb ⇒ ab are two derivations of ab. C is false because no right side is one non-terminal.

Question 5

Stem: What is the safest order while simplifying Context Free Grammar?

Options:

• A. Elimination of 𝜀-productions, Unit productions and then Useless symbols & productions.

• B. Elimination of useless symbols & productions, 𝜀-productions and then Unit productions.

• C. Elimination of Unit productions, 𝜀-productions and then Useless symbols and productions.

• D. Elimination of 𝜀-productions, Useless symbols and productions and then Unit productions.

Answer: A. In this UGC NET 2022, December item, epsilon removal can create unit productions. Unit removal can then leave rules non-generating or unreachable. Removing useless symbols last catches both effects.

Question 6

Stem: The equivalent grammar corresponding to the grammar

S → aA

A → BB

B → aBb | ε

Options:

• A.

S → aA

A → BB

B → aBb

• B.

S → a | aA

A → BB

B → aBb | ab

• C.

S → a | aA

A → BB | B

B → aBb

• D.

S → a | aA

A → BB | B

B → aBb | ab

Answer: D. In this UGC NET 2012, June item, B is nullable, making A nullable through A → BB. Add S → a, A → B, and B → ab by omitting the nullable occurrence in each affected rule. Then delete B → ε. All three additions are needed to preserve the original language.

Normal forms and derivation-length counting

Question 7

Stem: If G is a context-free grammar and W is a string of length l in L(G), how long is a derivation of W in G, if G is in Chomsky normal form?

Options:

• A. 2l

• B. 2l + 1

• C. 2l − 1

• D. l

Answer: C. CNF needs l - 1 binary productions to create l leaves, then l terminal productions. Thus (l - 1) + l = 2l - 1. For l = 4, three binary steps plus four terminal steps make seven, and 2(4) - 1 = 7.

Question 8

Stem: A CFG is said to be in Griebach Normal Form (GNF), if all the productions are   of the form A → aX where X is a sequence of any number of variables. Let G be a CFG in GNF. To derive a string of terminals of length x, the number of productions to be used is

Options:

• A. 2x – 1

• B. x

• C.  2x + 1

• D. 2^x

Answer: B. In the standard Greibach Normal Form, each production introduces exactly one terminal. A length-x string therefore needs x production uses. For x = 5, five steps introduce five terminals.

Language recognition and ambiguity checks

Question 9

Stem: Consider the following grammar and select the language generated by the grammar from the option.

S→ aSc | A

A→bAc | ϵ

Options:

• A.  L={aⁱ b^j c^k | i+j=k & i,j,k >0 }

• B.  L={aⁱ b^j c^k | i=k or j=k & i,j,k >0 }

• C.  L={aⁱ b^j c^k | i+j=k & i,j,k >=0 }

• D. L={aⁱ b^j c^k | i=k or j=k & i,j,k >=0 }

Answer: C. Use S → aSc i times and A → bAc j times, then A → ϵ. The result is a^i b^j c^(i+j), so k = i + j. Either recursion may be used zero times. With i = 2 and j = 3, this gives a²b³c⁵, and 5 = 2 + 3.

Question 10

Stem: The grammar whose productions are

 <stmt> → if id then <stmt>

 <stmt> → if id then  <stmt> else <stmt>

 <stmt> → id := id

is ambiguous because

Options:

• A. the sentence  if a then if b then c:= d  has two parse trees

• B. the left most and right most derivations of the sentence  if a then if b then c:= d  give rise to different parse trees

• C. the sentence  if a then if b then c:= d else c:= f  has more than two parse trees

• D. the sentence  if a then if b then c:= d else c:= f  has two parse trees

Answer: D. This GATE 1996 item has the dangling-else ambiguity. One parse attaches else c:= f to the inner if b; the other attaches it to the outer if a. Leftmost and rightmost derivations prove ambiguity only when they produce distinct parse trees.

Question 11

Stem:  Consider the following grammar.

S → ABC | Abc

BA → AB

Bb → bb

Ab → ab

Aa → aa

The languages generated by the above grammar is the set of all strings, made up of a, b, c such that:

(1) The no. of a's, b's, and c's will be equal.

(2) The no. of a's, b's, and c's are same, and the a's precede b's, which precede c's.

Options:

• A. Only (1)

• B. Only (2)

• C.  (1) & (2)

• D. None

Answer: B. The rules do not merely preserve equal counts. Reordering and terminalisation constrain the result to ordered blocks: every a precedes every b, and every b precedes every c. Statement (2) includes both equal counts and this order, so the correct answer is Only (2).

Full mixed simplification: count the final productions

Question 12

Stem: Consider the grammar consisting of 7 productions

S → aA | aBB

A → aaA | λ

B → bB | bbC

C → B

After elimination of Unit, useless and λ – productions, how many production remain in the resulting grammar?

Options:

• A. 2

• B. 3

• C. 4

• D. 5

Answer: C. Use the safe order even though the stem names the classes differently.

1. Remove A → λ, then add S → a and A → aa for the omitted nullable A.

2. Replace unit rule C → B with C → bB | bbC.

3. Neither B nor C has a terminating base rule, so delete both and S → aBB.

The final grammar is S → aA | a and A → aaA | aa. Counting the alternatives separately gives 2 + 2 = 4 productions, so the answer is C.

Score the set and choose the next practice step

Use this as study guidance, not an official benchmark:

• 10 to 12 correct: revise edge cases only.

• 7 to 9 correct: redo epsilon and unit removal.

• 0 to 6 correct: revisit generating and reachable variables.

The short version: mark nullable variables. Remove epsilon rules. Remove unit rules. Delete non-generating and unreachable symbols. After each stage, confirm that the language is preserved.

Continue structured Compiler Design learning with GATE Guidance by Sanchit Sir, and use the GATE Test Series for timed practice. The GATE category collects preparation material. Now re-solve all 12 without notes, writing the grammar after every elimination step.