context free grammars and pushdown automata short notes

CFG Symbol-Count Quick Checklist

CFG Symbol-Count Quick Checklist 1. Equation First Write the net terminal count change (Δ n_{a}, Δ n_{b}) for every production rule. 2. Bottom-Up Propagation Solve for the simplest non-terminals first, then substitute into higher-level rules. 3. Branching Tax Remember that rules splitting the derivation (e.g., S \to a S b S) increase the number of required base-case terminations. 4. Absorption Check When unrolling, check if outer recursive wrappers (like a^{k} \dots b^{k}) are absorbed by inner Kleene stars. 5. Edge Case Verification Test your final invariant against the shortest valid strings (e.g., length 1 or 2) to ensure no hidden exceptions exist. 6. Beware False Equality If any rule generates a's and b's asymmetrically, n_{a} (w) = n_{b} (w) is almost certainly false.

CNF and Derivation Length Quick Revision

CNF and Derivation Length Quick Revision Core Rules of CNF: A \to B C (Two non-terminals) A \to a (One terminal) S \to ϵ (Only if S is start and never on RHS) The Golden Formula: Derivation Steps = 2 n - 1 For any string w of length n \geq 1 derived in CNF Exam Execution: Identify n (total terminal count in the target string). Compute 2 n - 1 . Ignore distractors (number of variables, number of rules).

Ambiguity Quick Revision Checklist

Ambiguity Quick Revision Checklist Core Definitions: Ambiguous Grammar: \exists at least one string with > 1 LMD, > 1 RMD, or > 1 parse tree. Unambiguous Grammar: \forall strings, exactly 1 LMD, 1 RMD, and 1 parse tree. Inherently Ambiguous Language: No unambiguous CFG exists for this language. Proof Method: Pick a candidate string w . Derive w using two different leftmost derivation sequences. Confirm the parse trees are structurally distinct. Exam Heuristic: Look for rules with repeated non-terminals on the right-hand side (e.g., S \to a S b S) or symmetric binary operations (e.g., E \to E + E). These are prime candidates for ambiguity.

1 more card in this chapter

Context-Free Grammars and Pushdown Automata Short Notes for GATE CS

Context-Free Grammars and Pushdown Automata short notes for GATE CS: 4 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

CFG Symbol-Count Quick Checklist

1. Equation First Write the net terminal count change (

Δ n_{a}, Δ n_{b}

) for every production rule.

2. Bottom-Up Propagation Solve for the simplest non-terminals first, then substitute into higher-level rules.

3. Branching Tax Remember that rules splitting the derivation (e.g.,

S \to a S b S

) increase the number of required base-case terminations.

4. Absorption Check When unrolling, check if outer recursive wrappers (like

a^{k} \dots b^{k}

) are absorbed by inner Kleene stars.

5. Edge Case Verification Test your final invariant against the shortest valid strings (e.g., length 1 or 2) to ensure no hidden exceptions exist.

6. Beware False Equality If any rule generates

a

's and

b

's asymmetrically,

n_{a} (w) = n_{b} (w)

is almost certainly false.

CNF and Derivation Length Quick Revision

Core Rules of CNF:

$A \to B C$ (Two non-terminals)
$A \to a$ (One terminal)
$S \to ϵ$ (Only if $S$ is start and never on RHS)

The Golden Formula:

Derivation Steps = 2 n - 1

For any string $w$ of length $n \geq 1$ derived in CNF

Exam Execution:

Identify $n$ (total terminal count in the target string).
Compute $2 n - 1$ .
Ignore distractors (number of variables, number of rules).

Ambiguity Quick Revision Checklist

Core Definitions:

Ambiguous Grammar: $\exists$ at least one string with $> 1$ LMD, $> 1$ RMD, or $> 1$ parse tree.
Unambiguous Grammar: $\forall$ strings, exactly $1$ LMD, $1$ RMD, and $1$ parse tree.
Inherently Ambiguous Language: No unambiguous CFG exists for this language.

Proof Method:

Pick a candidate string $w$ .
Derive $w$ using two different leftmost derivation sequences.
Confirm the parse trees are structurally distinct.

Exam Heuristic:

Look for rules with repeated non-terminals on the right-hand side (e.g., $S \to a S b S$ ) or symmetric binary operations (e.g., $E \to E + E$ ). These are prime candidates for ambiguity.

High-Yield Revision: PDA Core Rules

Transition Meaning: $δ (q, a, X) ∋ (p, γ)$ means: in state $q$ , reading $a$ , with $X$ on top $\to$ move to $p$ , pop $X$ , push $γ$ .
DPDA Golden Rule: If $δ (q, a, X)$ is defined for $a \in Σ$ , then $δ (q, ϵ, X)$ must be empty.
Acceptance Equivalence: NPDA by Final State $\equiv$ NPDA by Empty Stack (CFL).
DPDA Limitation: DPDA by Empty Stack is strictly weaker (requires prefix property).
Stack Power Limit: Can verify $a^{n} b^{n}$ (DCFL) or $w w^{R}$ (CFL), but cannot verify $a^{n} b^{n} c^{n}$ or $w w$ (Not CFL).