Derivation & Recursion: 8 Solved MCQs + 2 CFG Problems

Derivation and recursion errors come from expanding the wrong nonterminal, missing an indirect cycle, or changing the language. Attempt each option or next step before checking its explanation; revise through GATE CS Exam Preparation. Questions 1, 2 and 4 have individual solved pages; for the other seven, use the Derivation & Recursion PYQ Questions practice hub.

Derivation and recursion rules to know before the questions

A sentential form is any string of terminals and nonterminals obtained from the start symbol. A leftmost derivation (LMD) always expands the leftmost nonterminal; a rightmost derivation (RMD) always expands the rightmost one. Direct left recursion has an immediate production such as A → Aα. Indirect left recursion returns through other nonterminals. Precisely, A is left recursive when A ⇒+ Aα for some α. Merely finding A somewhere on a right-hand side does not prove it.

For S → AB, A → aA | a, B → bB | b, derive aabb by LMD:

S ⇒ AB ⇒ aAB ⇒ aaB ⇒ aabB ⇒ aabb

The RMD is:

S ⇒ AB ⇒ AbB ⇒ Abb ⇒ aAbb ⇒ aabb

The expansion order changes, while both chains reach the same terminal string. To remove immediate left recursion, rewrite A → Aα | β as A → βA′ and A′ → αA′ | ε. Retain every nonrecursive β alternative. For an indirect cycle, substitute the intervening productions first, then apply the rewrite.

Derivation and recursion MCQs 1-2: detecting and removing left recursion

Question 1

GATE 2017

Consider the following expression grammar G:

E -> E - T | T

T -> T + F | F

F -> (E) | id

Which of the following grammars are not left recursive, but equivalent to G ?

A.

E -> E - T | T

T -> T + F | F

F -> (E) | id

B.

E -> TE'

E' -> -TE' | ε

T -> T + F | F

F -> (E) | id

C.

E -> TX

X -> -TX | ε

T -> FY

Y -> +FY | ε

F -> (E) | id

D.

E -> TX | (TX)

X -> -TX | +TX | ε

T -> id

Answer: C. Both E → E - T and T → T + F are immediate cycles. B repairs only E. C uses X and Y to repeat the two suffixes without a leftmost self-call, preserving the expression strings and the E/T precedence separation. D changes the factor structure and therefore the language. See the complete solved Question 1.

Question 2

GATE 2016

Which one of the following grammars is free from left recursion?

A.

S → AB
A → Aa | b
B → c

B.

S → Ab | Bb | c
A → Bd | ε
B → e

C.

S → Aa | B
A → Bb | Sc | ε
B → d

D.

S → Aa | Bb | c
A → Bd | ε
B → Ae | ε

Answer: B. A contains A → Aa. C has the indirect cycle S ⇒ Aa ⇒ Sca, while D has A ⇒ Bd ⇒ Aed. In B, B becomes e, A becomes Bd or ε, and no S alternative returns S, A or B to the left edge of its own derivation. B is the only recursion-free choice. Check the complete solved Question 2.

Derivation and recursion MCQs 3-4: transformation integrity and precedence

Question 3

Consider the following grammar:

S → AB | eC

A → aD|ε

B → D|bAC

C → cE|ε

D → B|d|De|D

Which of the following is a correct left-recursion-free equivalent grammar?

A.

S → AB|eC  
A → aD|ε  
B → dB'| bAC  
B' → eB'|ε  
C → cE|ε  
D → dD'|B  
D' → eD'|ε

B.

S → AB|C  
A → aD|ε  
B → D|b A C  
C → cE|ε  
D → dD'|BD'  
D' → eD'|ε

C.

S → AB|C  
A → aD|ε  
B → dB'|bAC  
B' → eB' |ε  
C → c E|ε  
D → d|B D'
D' → eD'|ε

D.

S → AB |C  
A → aD |ε  
B → D |bAC   
C → cE|ε  
D → dD'|bACD'
D' → eD'|ε

The given answer is D, but no option is equivalent. B, C and D change S → eC to S → C. Since C → ε, original derives e, while the altered rule derives ε. A has no left recursion, but it is not equivalent: its B loses e-suffixed strings from the bAC branch. For example, the original derives be via B ⇒ D ⇒ De ⇒ Be ⇒ bACe ⇒ be, whereas A cannot. Resolve D → De and that unit cycle as R → eR | ε, B → dR | bACR, D → dR | bACR, keeping S → AB | eC. This clean equivalent has no left recursion. The question has an error in its answer options.

Question 4

ISRO 2015

Given the following expression grammar:

E → E ∗ F ∣ F + E ∣ F

F → F − F ∣ id

Which of the following is true? ISRO 2015

• A. ∗ has higher precedence than +

• B. - has higher precedence than ∗

• C. + and - have same precedence

• D. + has higher precedence than ∗

Answer: B. F is completed before it participates in an E production, so − inside F binds more tightly than ∗ and + at E. However, F → F − F permits multiple groupings, so do not infer clean associativity. Review the complete solved Question 4.

Derivation and recursion MCQs 5-6: CFG limits and recursion vocabulary

Question 5

Which of the following features cannot be captured by a CFG.

• A. Syntax of a recursive procedures

• B. Syntax of if-then-else statements

• C. Whether a variable is declared before its use

• D. Matching nested parentheses

Answer: C. A CFG generates recursive procedures, nested conditionals and balanced parentheses. Declaration-before-use requires storing an identifier and scope, then checking a later use. That belongs to semantic analysis and the symbol table.

Question 6

Which grammar will have the left recursive production reference within the given string?

• A. Left Recursive Grammar

• B. Right Recursive Grammar

• C. Straight Recursive Grammar

• D. None of the above

Answer: A. A → Aα is immediately left recursive because A is leftmost on the right-hand side. A → αA is right recursive. Its position selects A.

Derivation and recursion MCQs 7-8: reading the generated language

Question 7

Consider the following grammars over Σ = {a, b, c}:

G₁:

S → a | c | aS | cS | bA

A → b | c | bA | cA

G₂:

S → b | c | bS | cS | aA

A → b | bS

Which option correctly describes the properties satisfied by the strings in these languages?

• A. G₁: No b appears before any a. G₂: Every a is followed by at least one b.

• B. G₁: No b appears before any a. G₂: No a appears before any b.

• C. G₁: No b appears after any a. G₂: Every a is followed by at least one b.

• D. G₁: No b appears after any a. G₂: Every b is followed by at least one a.

Answer: A. In G₁, S emits a or c until S → bA; A then emits only b or c. No a follows the first b. In G₂, only S → aA emits a, and A → b | bS begins with b. Every a has a following b.

Question 8

If G is a grammar with start symbol S and productions

S → S1S | 0S1 | 1S0 | SS | ε

then which one of the following strings is not generated by G?

• A. 1010

• B. 0110110

• C. 10010

• D. 010111010

Answer: C. The invariant is number of 1s ≥ number of 0s. ε starts equal; SS combines valid pairs; S1S adds one 1; the other rules add one of each. 10010 has two 1s and three 0s, so it is impossible. Option A is generated by S ⇒ 1S0 ⇒ 10S10 ⇒ 1010. Options B and D are generated as 0110110 = (01)1(01·10) and 010111010 = 01·((01)1(1010)); each 01 or 10 comes from a paired rule with the inner S ⇒ ε.

Worked problems 9-10: derivations and compiler-friendly grammar

Questions 9 and 10 are subjective problems, not MCQs. Write the derivations before comparing them with the worked answers.

Question 9

Explain the concept of derivation in Context-Free Grammar (CFG). Differentiate between Leftmost Derivation (LMD) and Rightmost Derivation (RMD) with an example. Also, define recursive grammars and discuss different types of recursion. Why is left recursion problematic in compilers, and how can it be eliminated?

One step is ⇒; zero or more steps are ⇒*; an intermediate string is a sentential form. For E → E + E | id, LMD of id + id is E ⇒ E + E ⇒ id + E ⇒ id + id; RMD is E ⇒ E + E ⇒ E + id ⇒ id + id.

Recursion may be direct or indirect, left or right. A naive top-down parser loops without consuming input. Replace A → Aα | β with A → βA′, A′ → αA′ | ε; substitute indirect cycles first.

Question 10

Given the grammar:

E → E − T | T

T → T + F | F

F → (E) | id

Eliminate the left recursion and construct an equivalent grammar suitable for top-down parsing. Justify each step clearly.

E and T each have immediate left recursion. Transform them separately:

E → TE′
E′ → −TE′ | ε
T → FT′
T′ → +FT′ | ε
F → (E) | id

E and T now begin through lower-level nonterminals, letting a top-down parser consume input before repetition. Strings and E/T precedence layering remain. Implement left associativity through a semantic action or left fold.

How derivation and recursion questions are tested

Exam questions test four moves: find recursion cycles, read precedence from nonterminal levels, separate syntax from semantic checks, and prove languages with a derivation or invariant.

Study First and Follow in Compiler Design: Solved Examples, then try Context-Free Grammar MCQs: 11 Solved CFG, CFL, PDA. Redo Questions 1, 2, 7 and 8 unseen. Record the deciding step, then repeat after two days. Question 3 reminds you to preserve the language.

GATE Guidance by Sanchit Sir includes the full Compiler Design and Grammar & CFG sequence. For focused practice, solve the 10 questions from the opening hub.