Context-Free Grammars & Pushdown Automata

A context-free grammar is a 4-tuple G = (V, Σ, R, S) where:

• V is a finite set of variables (also called nonterminals), written in uppercase: A, B, S, EXPR.
• Σ is a finite set of terminals (actual symbols of the language: digits, letters, punctuation), disjoint from V.
• R is a finite set of production rules, each of the form A → α where A ∈ V and α ∈ (V ∪ Σ)*.
• S ∈ V is the start variable.

The word "context-free" is key. In a context-sensitive grammar, a rule A → α fires only when A appears in a specific context (left or right neighbor). Here, A can be replaced by α no matter where it appears. This restriction is both a limitation (some languages are not context-free) and a tremendous advantage: it enables efficient parsing algorithms.

Example — simple arithmetic expressions:

E → E + T | T
T → T * F | F
F → ( E ) | id

This grammar generates expressions like id + id * id and (id + id) * id. The nonterminals carry semantic roles: E for expression, T for term, F for factor — encoding the standard operator precedence directly into the grammar structure.

Why finite rules generate an infinite language: Any rule that is recursive (directly or indirectly) can fire arbitrarily many times. E → E + T lets us extend an expression leftward as many times as we like. The grammar is a finite description of an infinite set.

# Python: represent a grammar as a dict of lists-of-tuples
grammar = {
    'E': [('E', '+', 'T'), ('T',)],
    'T': [('T', '*', 'F'), ('F',)],
    'F': [('(', 'E', ')'), ('id',)],
}
start = 'E'

# A symbol is a terminal if it is not a key in the grammar
def is_terminal(sym):
    return sym not in grammar

A grammar generates strings through a process called derivation. Starting from S, we repeatedly replace a variable with one of its right-hand sides until no variables remain. Each replacement step is written with an arrow: ⇒. A sequence of steps is a derivation, written ⇒* (zero or more steps).

Formally, if α A β is a sentential form (a string of terminals and variables) and A → γ is a rule, then α A β ⇒ α γ β. The language of G, written L(G), is the set of all strings of terminals derivable from S:

L(G) = { w ∈ Σ* | S ⇒* w }

Leftmost vs. rightmost derivation: At each step we can choose which variable to expand. A leftmost derivation always expands the leftmost variable; a rightmost derivation always expands the rightmost. For an unambiguous grammar (defined shortly), every string has a unique leftmost derivation and a unique rightmost derivation, and they correspond to opposite traversals of the same parse tree.

Example derivation of id + id * id in the arithmetic grammar:

E ⇒ E + T          (rule E→E+T)
  ⇒ T + T          (rule E→T, leftmost E)
  ⇒ F + T          (rule T→F)
  ⇒ id + T         (rule F→id)
  ⇒ id + T * F     (rule T→T*F)
  ⇒ id + F * F     (rule T→F)
  ⇒ id + id * F    (rule F→id)
  ⇒ id + id * id   (rule F→id)

This is a leftmost derivation of 8 steps for a 5-token string. The length of derivations can grow without bound as strings grow, but each step is a local, context-free substitution.

# Enumerate all strings derivable in at most max_steps steps (BFS)
from collections import deque

def derive_bfs(grammar, start, terminals, max_steps=6):
    """Returns set of terminal strings derivable from start."""
    results = set()
    # Each state is a tuple representing a sentential form
    queue = deque([(start,)])
    seen = {(start,)}
    while queue:
        form = queue.popleft()
        # Check if all terminals
        if all(s in terminals for s in form):
            results.add(form)
            continue
        if sum(1 for s in form if s not in terminals) == 0:
            continue  # no variables to expand
        steps = sum(1 for s in form if s not in terminals)
        if steps > max_steps:
            continue
        # Expand leftmost variable
        for i, sym in enumerate(form):
            if sym not in terminals:
                for rhs in grammar[sym]:
                    new_form = form[:i] + rhs + form[i+1:]
                    if new_form not in seen:
                        seen.add(new_form)
                        queue.append(new_form)
                break
    return results

A parse tree (also called a derivation tree or concrete syntax tree) is a tree representation of a derivation that suppresses the order in which rules were applied, retaining only the structure. Each internal node is labeled with a variable; its children are labeled with the symbols of the rule's right-hand side, left-to-right. Leaves are terminals (or ε). Reading the leaves left-to-right gives the derived string.

Parse trees are the right mental model because they represent meaning. The tree for id + id * id under the arithmetic grammar correctly shows + at a higher level than *, reflecting that multiplication binds tighter.

Ambiguity is one of the most practically important concepts in the module. A grammar G is ambiguous if some string w ∈ L(G) has two or more distinct parse trees (equivalently, two distinct leftmost derivations).

Classic ambiguous grammar:

E → E + E | E * E | ( E ) | id

The string id + id * id has two parse trees here:

1. + at root, with id and id * id as subtrees (correct, multiplication first).
2. * at root, with id + id and id as subtrees (wrong, addition first).

Ambiguity is a property of the grammar, not the language. The arithmetic language above is inherently unambiguous: the grammar with E→E+T | T, T→T*F | F, F→id|(E) is unambiguous and generates the same language. However, some languages are inherently ambiguous: no unambiguous grammar exists for them. The classic example is

{ a^i b^j c^k | i=j or j=k }

which is context-free but inherently ambiguous.

Why ambiguity matters in practice: A YACC/Bison parser for an ambiguous grammar will report shift-reduce or reduce-reduce conflicts. The parser has no way to choose between two valid trees, and you must resolve the conflict by either rewriting the grammar (usually) or using explicit precedence declarations (a common shortcut in practice).

# Visualise a parse tree with a simple recursive descent pretty-printer
# (Assume tree is represented as nested tuples: (label, child1, child2, ...))

def pp_tree(node, indent=0):
    if isinstance(node, str):
        print('  ' * indent + node)
    else:
        label, *children = node
        print('  ' * indent + label)
        for child in children:
            pp_tree(child, indent + 1)

# Tree for id + id * id (correct, multiplication binds tighter)
tree = ('E',
          ('E', ('T', ('F', 'id'))),
          '+',
          ('T',
            ('T', ('F', 'id')),
            '*',
            ('F', 'id')))

pp_tree(tree)

A pushdown automaton (PDA) is the computational model corresponding to CFGs. It is a nondeterministic finite automaton augmented with an unbounded stack. The stack is what separates PDAs from DFAs/NFAs: it provides memory that can grow proportional to the input depth, enabling the machine to count and match nested structures.

Formally, a PDA is a 6-tuple P = (Q, Σ, Γ, δ, q₀, F) where:

• Q: finite set of states.
• Σ: input alphabet.
• Γ: stack alphabet (can include a special bottom-of-stack marker, often $ or Z₀).
• δ: Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → 2^(Q × (Γ ∪ {ε})*) — the transition function. Each transition reads (or skips, if ε) one input symbol, pops (or skips) the top of stack, and pushes a string of stack symbols.
• q₀ ∈ Q: start state.
• F ⊆ Q: accept states.

A PDA accepts by final state if there is a computation that reads all input and ends in a state in F. (Alternatively, accepting by empty stack yields an equivalent class of languages.)

Notation for a transition: δ(q, a, A) ∋ (r, B₁B₂...Bₖ) means: in state q, reading input a, with A on top of stack, push B₁B₂...Bₖ (B₁ on top) and go to state r. If k=0, the stack symbol is popped without replacement.

Canonical example — recognizing {0ⁿ1ⁿ | n ≥ 0}: This language is not regular (proved by the pumping lemma for regular languages), but a PDA handles it easily:

1. Push a marker $ onto the stack.
2. In state q₁: for each '0' read, push '0' onto the stack.
3. On seeing the first '1', transition to state q₂.
4. In state q₂: for each '1' read, pop one '0'.
5. If the stack contains only $ when input ends, accept.

Nondeterminism is essential. Unlike for finite automata (where NFA = DFA), deterministic PDAs (DPDAs) recognize a strict subset of context-free languages. The language { ww^R | w ∈ {0,1}* } is context-free but not deterministic context-free — a DPDA cannot know when the string transitions from the first half to the second without peeking at the future. This nondeterminism is why PDAs are converted to CFGs (and vice versa) rather than being implemented directly; parsers use algorithmic techniques (LL/LR) to resolve nondeterminism for practical grammars.

# Simulate a nondeterministic PDA for { 0^n 1^n | n >= 1 }
# Represent configuration as (state, remaining_input, stack)
# stack: list, top = last element

def accepts_0n1n(s):
    """True iff s == '0'*n + '1'*n for some n >= 1."""
    # BFS over nondeterministic configurations
    from collections import deque
    # States: 'start', 'push', 'pop', 'accept'
    init = ('push', s, ['$'])
    queue = deque([init])
    visited = set()
    while queue:
        state, inp, stack = queue.popleft()
        key = (state, inp, tuple(stack))
        if key in visited:
            continue
        visited.add(key)
        if state == 'accept' and inp == '' and stack == ['$']:
            return True
        if not inp:
            # Try epsilon transitions to accept
            if state == 'pop' and stack == ['$']:
                queue.append(('accept', '', ['$']))
            continue
        c = inp[0]; rest = inp[1:]
        if state == 'push':
            if c == '0':
                # Push 0 onto stack
                queue.append(('push', rest, stack + ['0']))
            if c == '1' and stack[-1] == '0':
                # Nondeterministically switch to pop mode
                queue.append(('pop', rest, stack[:-1]))
        elif state == 'pop':
            if c == '1' and stack[-1] == '0':
                queue.append(('pop', rest, stack[:-1]))
    return False

print(accepts_0n1n('0011'))   # True
print(accepts_0n1n('001'))    # False
print(accepts_0n1n('000111')) # True

The central theorem of this module: A language is context-free if and only if some PDA recognizes it. This equivalence has two directions, each constructive.

CFG → PDA (every CFL has a PDA): Given a CFG G, construct a PDA P that simulates a leftmost derivation nondeterministically. P has three states: start (q_start), loop (q_loop), accept (q_accept).

1. Initialization: Push $ and then S (start variable) onto the stack. Go to q_loop.
2. Variable on top of stack: For each rule A → α, nondeterministically pop A and push the reverse of α (so the first symbol of α is on top). This is an ε-transition (no input consumed).
3. Terminal on top of stack: If the top of stack matches the current input symbol, pop it and advance the input. This is a match step.
4. Acceptance: If only $ remains and input is exhausted, accept.

The PDA is nondeterministic because step 2 can choose any rule for A. A successful computation corresponds exactly to a leftmost derivation of the input string.

PDA → CFG (every PDA language has a CFG): Given a PDA P, construct a CFG whose variables are triples (p, A, q), written [pAq], with the intuition: "[pAq] derives exactly the strings that take the PDA from state p with A on top of the stack to state q having completely consumed A." The production rules encode this semantics:

• For each transition δ(q, a, A) ∋ (r, B₁...Bₖ), add rules: [qAq_k] → a [rB₁q₁][q₁B₂q₂]...[q_{k-1}Bₖqₖ] for all states q₁, ..., qₖ ∈ Q.
• Also add S → [q₀Z₀q_f] for each accepting state q_f.

This construction has O(|Q|³ · |Γ|) variables in the worst case, so it generates large grammars — but it is correct, and that is the point.

Corollary: The class of context-free languages is closed under union, concatenation, and Kleene star (by combining grammars). It is not closed under intersection or complement (though the intersection of a CFL and a regular language is always a CFL — a useful practical fact for parser specification).

# The CFG->PDA construction in pseudocode (not runnable; illustrates the algorithm)

# Given: grammar G with start S, variables V, terminals T, rules R
# Build PDA with states {q_start, q_loop, q_accept}
# Stack alphabet: V ∪ T ∪ {$}

# Initial transition:
# delta(q_start, eps, eps) -> (q_loop, S $)   # push start symbol, then $

# For each rule A -> alpha in R:
# delta(q_loop, eps, A) -> (q_loop, reverse(alpha))
#   i.e., pop A, push alpha reversed so alpha[0] is on top

# For each terminal a in T:
# delta(q_loop, a, a) -> (q_loop, eps)   # match and pop

# Accept transition:
# delta(q_loop, eps, $) -> (q_accept, eps)   # empty stack -> accept

For theoretical proofs (especially the pumping lemma), it is convenient to work with grammars in a normalized form.

Chomsky Normal Form (CNF): Every rule is either:

• A → BC (two variables), or
• A → a (one terminal), or
• S → ε (only for the start variable, if ε ∈ L(G)).

Theorem: Every CFL has a CNF grammar.

Conversion algorithm (four-step simplification):

1. Add new start S₀ → S to ensure the start variable does not appear on any right-hand side.
2. Remove ε-rules: For each rule with ε on the right (A → ε, A ≠ S₀), add versions of every rule that uses A with and without A, then delete A → ε.
3. Remove unit rules (A → B where B is a single variable): replace with all non-unit rules reachable from B, then delete unit rules.
4. Binarize: Replace long right-hand sides (A → B₁B₂...Bₖ, k≥3) with new variables: A → B₁A₁, A₁ → B₂A₂, ..., and replace terminals in mixed rules (A → aB) with A → UₐB, Uₐ → a.

Greibach Normal Form (GNF): Every rule is A → aα where a ∈ Σ is a terminal and α ∈ V*. In GNF, every derivation step consumes exactly one terminal, so a string of length n has derivations of exactly n steps. GNF is used in proving that PDAs can always be modeled with a single state.

Why CNF matters in practice: The CYK (Cocke–Younger–Kasami) parsing algorithm requires CNF and runs in O(n³ · |G|) time on any CFG in CNF. It is the canonical dynamic-programming parser for arbitrary CFGs.

# CYK membership test — given a grammar in CNF and a string w
# Returns True if w in L(G)

def cyk(grammar_binary, grammar_unit, start, w):
    """
    grammar_binary: dict  A -> list of (B, C) pairs
    grammar_unit:   dict  A -> list of terminal strings
    start: start variable
    w: input string (list of terminals)
    """
    n = len(w)
    if n == 0:
        return False  # assume epsilon handled separately
    # table[i][j] = set of variables that derive w[i..j]
    table = [[set() for _ in range(n)] for _ in range(n)]

    # Base case: single characters
    for i, c in enumerate(w):
        for A, terminals in grammar_unit.items():
            if c in terminals:
                table[i][i].add(A)

    # Fill table for substrings of increasing length
    for length in range(2, n + 1):       # length of substring
        for i in range(n - length + 1):  # start index
            j = i + length - 1           # end index
            for k in range(i, j):        # split point
                for A, pairs in grammar_binary.items():
                    for (B, C) in pairs:
                        if B in table[i][k] and C in table[k+1][j]:
                            table[i][j].add(A)

    return start in table[0][n - 1]

The pumping lemma for context-free languages is the principal tool for proving that a given language is not context-free. It is a statement about all context-free languages that, when violated by a specific language, certifies non-membership in the CFL class.

Theorem (Pumping Lemma for CFLs): Let L be a context-free language. Then there exists a pumping length p such that every string w ∈ L with |w| ≥ p can be written as w = uvxyz satisfying:

1. For all i ≥ 0, uv^i xy^i z ∈ L.
2. |vy| ≥ 1 (at least one of v, y is non-empty).
3. |vxy| ≤ p.

Proof sketch (via CNF and parse trees): Convert L's grammar to CNF. For a long enough string, any parse tree must have a path from root to leaf of length ≥ |V| + 1, so some variable A appears twice on that path. The subtree rooted at the lower A generates the string x; the subtree rooted at the upper A generates vxy. By replacing the upper A-subtree with the lower (pump down, i=0) or replacing the lower A-subtree with the upper (pump up, i≥2), we get new strings still in L. This is the key picture: two occurrences of A on a root-to-leaf path give a "handle" that can be iterated.

How to use it (proof by contradiction):

1. Assume L is context-free.
2. Let p be the pumping length.
3. You choose a specific string w ∈ L with |w| ≥ p (choose wisely to make the argument work).
4. The adversary chooses the split w = uvxyz satisfying conditions 2 and 3.
5. You choose a value of i ≥ 0 such that uv^i xy^i z ∉ L.
6. This contradicts condition 1, so L cannot be context-free.

Classic example — {a^n b^n c^n}:

Let w = a^p b^p c^p. Any split uvxyz with |vxy| ≤ p cannot span all three character types simultaneously. Either vxy lies entirely in the a-region, entirely in the b-region, entirely in the c-region, or spans two adjacent regions (a's and b's, or b's and c's). In every case, pumping (i=2) increases the count of at most two of the three character types, making the counts unequal — so the pumped string is not in L.

Warning: The pumping lemma gives a necessary but not sufficient condition for being context-free. Passing the pumping lemma does not prove a language is context-free. To prove a language IS context-free, you must exhibit a CFG or PDA for it.

# Illustrate the pumping lemma argument for { a^n b^n c^n }
# (This is a proof-checker, not a formal prover)

def check_split_fails(v, y, p):
    """
    Given a split with parts v and y (strings over {a,b,c}),
    and pumping length p, check that pumping once (i=2)
    produces a string NOT in {a^n b^n c^n}.
    """
    # The pumped string has v+y added once more
    def count(s, c): return s.count(c)
    # Original contribution: v and y already appear once
    # Pumped (i=2): add one more v and y
    total_a = p + count(v, 'a') + count(y, 'a')
    total_b = p + count(v, 'b') + count(y, 'b')
    total_c = p + count(v, 'c') + count(y, 'c')
    return not (total_a == total_b == total_c)

# vxy must be of length <= p and lie in a contiguous region
# All possible short splits of a^p b^p c^p with |vxy|<=p
# Example: p=3, vxy = 'aaa' (v='a', x='a', y='a')
print(check_split_fails('a', 'a', 3))   # True: counts become 5,3,3
print(check_split_fails('ab', 'bc', 3)) # True: spans two regions, messes up counts

Context-free languages form a class with well-defined closure properties that differ importantly from regular languages.

Closed under:

• Union: L₁ ∪ L₂ — add new start S → S₁ | S₂.
• Concatenation: L₁L₂ — add new start S → S₁S₂.
• Kleene star: L* — add new start S → SS₁ | ε.
• Homomorphism (symbol-by-symbol string substitution).
• Reverse: L^R — reverse all right-hand sides.
• Intersection with regular languages: If L is a CFL and R is regular, then L ∩ R is a CFL. (Construct the product of the PDA for L and the DFA for R — the key insight is the DFA requires no stack, so the product machine is still a PDA.) This is enormously useful: you can use a regular expression to filter the input before a context-free parser handles the structure.

NOT closed under:

• Intersection: {a^n b^n c^n} = {a^n b^n | n≥0} ∩ {a* b^n c^n | n≥0}... wait, more carefully: {a^n b^n | n≥1} ∩ {b^n c^n | n≥1} projected appropriately. The canonical argument: {a^n b^n} and {b^n c^n} are both CFLs, but their "aligned" intersection over a three-symbol alphabet gives {a^n b^n c^n}, which is not a CFL.
• Complement: By De Morgan, since the class is closed under union but not intersection, it cannot be closed under complement either (closure under union + complement ⟹ closure under intersection).

Decision properties:

• Membership: O(n³) via CYK.
• Emptiness: decidable (check if start variable generates any terminal string).
• Finiteness: decidable.
• Equality of two CFLs: undecidable.
• Ambiguity of a grammar: undecidable (though semi-decidable).

# Closure under intersection with a regular language:
# Product construction: PDA cross DFA -> PDA
# Pseudocode for constructing the product machine

# Let P = (Q_P, Sigma, Gamma, delta_P, q0_P, F_P) be a PDA
# Let D = (Q_D, Sigma, delta_D, q0_D, F_D) be a DFA

# Product PDA has:
#   States: Q_P x Q_D
#   Start:  (q0_P, q0_D)
#   Accept: F_P x F_D
#   Transitions:
#     If delta_P(p, a, A) contains (r, gamma) and delta_D(d, a) = e:
#       then delta_product((p,d), a, A) contains ((r,e), gamma)
#     Epsilon moves of P carry over:
#       If delta_P(p, eps, A) contains (r, gamma):
#         then delta_product((p,d), eps, A) contains ((r,d), gamma)

# This product is still a PDA (one stack, finite control Q_P x Q_D)
# It recognizes L(P) ∩ L(D)

Not all context-free languages are recognized by deterministic PDAs. The class of deterministic context-free languages (DCFLs) is a strict subset of CFLs. It includes all the programming languages you know: C, Java, Python, Haskell. The key insight is that real compilers must be deterministic and efficient.

Deterministic PDA (DPDA): A PDA where for each state, input symbol, and stack top, at most one transition is applicable, and if any transition reads a real input symbol, no ε-transition is applicable from that configuration. DPDAs accept by empty stack or final state (these two acceptance conditions are NOT equivalent for DPDAs, unlike for NDPDAs).

LL(k) grammars: A grammar is LL(k) if a top-down, left-to-right parser can always decide which rule to apply by looking at the next k input symbols. LL(1) grammars are the most important: one lookahead token suffices. The parser maintains a parse stack; at each step it matches the top of stack against the next input token (for terminals) or uses a parse table to select a rule (for variables). Hand-written recursive descent parsers implement LL(1) parsing naturally — each nonterminal becomes a function.

LR(k) grammars: More powerful. LR(1) includes all the LL(1) grammars and much more. An LR parser is a bottom-up parser: it reads input left-to-right and builds the parse tree from leaves to root. It uses a shift-reduce strategy: either shift the next token onto the parse stack, or reduce the top of the stack by applying a grammar rule in reverse. YACC/Bison generate LALR(1) parsers (LR with merged lookahead states), which handle all common programming language constructs.

The hierarchy:

Regular ⊂ DCFL ⊂ CFL ⊂ Context-sensitive ⊂ Recursive ⊂ R.E.

LL(1) ⊂ LL(k) ⊂ LALR(1) ⊂ LR(1) ⊂ LR(k) ⊂ DCFL-by-grammar

The Earley algorithm recognizes any CFL in O(n³) (O(n²) for unambiguous, O(n) for LL(k)/LR(k) grammars), making it the most general practical parser.

# A minimal recursive-descent (LL(1)) parser for: E -> T ('+' T)*
# Tokenizer produces list of tokens; parser returns an AST.

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return None

    def consume(self, expected=None):
        tok = self.tokens[self.pos]
        if expected and tok != expected:
            raise SyntaxError(f'Expected {expected}, got {tok}')
        self.pos += 1
        return tok

    def parse_E(self):
        # E -> T ('+' T)*
        left = self.parse_T()
        while self.peek() == '+':
            self.consume('+')
            right = self.parse_T()
            left = ('+', left, right)
        return left

    def parse_T(self):
        # T -> '(' E ')' | NUM
        if self.peek() == '(':
            self.consume('(')
            node = self.parse_E()
            self.consume(')')
            return node
        else:
            return ('num', self.consume())

tokens = ['(', '1', '+', '2', ')', '+', '3']
p = Parser(tokens)
print(p.parse_E())  # ('+', ('+', ('num','1'), ('num','2')), ('num','3'))

When you read a programming language specification — the C standard, the Python grammar, the ECMAScript spec — you encounter BNF (Backus–Naur Form) or its extended variant EBNF. These are simply notational conventions for writing CFGs.

BNF notation:

• Nonterminals are written <like-this> or in uppercase.
• Rules are written <lhs> ::= rhs1 | rhs2 | ...
• Terminals are quoted or written literally.

EBNF extensions (vary by author/tool, but common ones):

• {α} means α repeated zero or more times (= α* in formal notation).
• [α] means α optional (= α | ε).
• (α | β) groups alternatives.

The Python grammar (excerpt):

if_stmt: 'if' named_expr ':' block ('elif' named_expr ':' block)* ['else' ':' block]
block:   NEWLINE INDENT statement+ DEDENT | simple_stmts

This is EBNF — the Python project uses it directly to generate a PEG parser (CPython's parser since 3.9). PEG (Parsing Expression Grammar) parsers are closely related to CFG parsers but use ordered choice (the first matching alternative wins), which makes them deterministic and fast while sacrificing some CFG generality.

Left recursion and left factoring: LL(1) parsers cannot handle left-recursive rules like E → E + T. You must eliminate left recursion by rewriting:

E  → T E'
E' → + T E' | ε

This is called left-recursion elimination. Similarly, left factoring rewrites rules with a common prefix into a form that allows a single lookahead to pick the right rule. These transformations are mechanical and are a standard part of compiler courses.

Grammar engineering — writing a grammar that is correct, unambiguous, efficient to parse, and expressive — is a genuine craft. The tension between expressiveness (allowing more language constructs) and parsability (keeping the grammar LL(1) or LALR(1)) has shaped every major programming language's syntax.

# Left recursion elimination (mechanical transformation)
# Before: E -> E '+' T | T    (left-recursive)
# After:  E  -> T E'
#         E' -> '+' T E' | eps

# Verify by tracing the derivation of 'a + b + c':
# E => T E' => a E' => a + T E' => a + b E' => a + b + T E' => a + b + c E' => a + b + c
# (E' -> eps at end)

# General left-recursion elimination for A -> A alpha_1 | ... | A alpha_k | beta_1 | ... | beta_m
# becomes:
#   A  -> beta_1 A' | ... | beta_m A'
#   A' -> alpha_1 A' | ... | alpha_k A' | eps

def eliminate_left_recursion(rules_for_A, A):
    """
    rules_for_A: list of right-hand sides (each a tuple of symbols) for nonterminal A.
    Returns (new_rules_A, new_rules_Aprime) after eliminating direct left recursion.
    """
    A_prime = A + "'"
    alpha = [r[1:] for r in rules_for_A if r[0] == A]   # recursive tails
    beta  = [r    for r in rules_for_A if r[0] != A]    # non-recursive alternatives
    if not alpha:
        return rules_for_A, []  # no left recursion
    new_A      = [b + (A_prime,) for b in beta]
    new_Aprime = [a + (A_prime,) for a in alpha] + [('eps',)]
    return new_A, new_Aprime

rules_E = [('E', '+', 'T'), ('T',)]
new_E, new_Eprime = eliminate_left_recursion(rules_E, 'E')
print('E  ->', new_E)       # [('T', "E'")]
print("E' ->", new_Eprime) # [('+', 'T', "E'"), ('eps',)]