Correct Answer: Eliminating Immediate Left Recursion \A \rightarrow A\alpha / \beta\ | AI Research

Correct Answer: Eliminating Immediate Left Recursion (A \rightarrow A\alpha / \beta)

Verified Sources

Sep 12, 2026

To remove immediate left recursion of the form
$A \rightarrow A\alpha \mid \beta$
(where (\beta) does not start with (A)), the standard transformation introduces a new nonterminal (A') and rewrites the grammar as:
$A \rightarrow \beta A'$
$A' \rightarrow \alpha A' \mid \epsilon$

This directly matches option (i).

Therefore, the correct choice is (i) (A \rightarrow \beta A').

Key learning terms: immediate left recursion , elimination transformation , new nonterminal , epsilon.

Knowledge Check

Question 1 of 3

Q1Single choice

After removing immediate left recursion from grammar $A \rightarrow A\alpha \mid \beta$ , which production is created for $A$ ?

(i) $A \rightarrow \beta A'$

(ii) $A \rightarrow \alpha A'$

(iii) $A \rightarrow \alpha \beta A''$

(iv) $A \rightarrow \beta \alpha A'$

Explore Related Topics

Which Automaton Accepts Regular Languages? The Correct Answer Is DFA

The deterministic finite automaton (DFA) is the canonical model that exactly accepts regular languages, whereas PDA, LBA, and Turing machines recognize strictly larger language families.

A language is regular iff some DFA $M=(Q,\Sigma,\delta,q_0,F)$ accepts it: $L(M)=\{w\in\Sigma^* \mid \delta^*(q_0,w)\in F\}$ .
DFA ↔ regular languages; PDA ↔ context‑free; LBA ↔ context‑sensitive; Turing machine ↔ recursively enumerable.
Regular languages form the base of the hierarchy: $\text{Regular} \subset \text{Context-Free} \subset \text{Context-Sensitive} \subset \text{Recursively Enumerable}$ .
DFA’s finite memory limits it to patterns like “ends with 01” or “even number of 1’s”, but it cannot handle unbounded counting such as $\{a^n b^n\mid n\ge0\}$ .

Ambiguity in Context-Free Grammars, Disambiguation Techniques, and Analysis of the Grammar $S \rightarrow aS/Sa/a$

Regular Expression Equivalence: Which Pairs Generate the Same Language?

Browse all research articles