The language of balanced brackets, and of aⁿbⁿ, cannot be recognised by any finite automaton, because counting needs memory. Context-free grammars describe these languages and pushdown automata recognise them, using a stack as that memory. This pair is one of the most tested areas of Theory of Computation. The grammar S → aSb | ε and a two-state stack machine both capture aⁿbⁿ, and the two formalisms describe exactly the same class of languages.
Context-free grammars: the definition
A context-free grammar is a four-tuple (V, T, P, S). V is the set of variables (non-terminals), T is the set of terminals, P is the set of productions, and S is the start symbol. Each production has a single variable on its left, so its left side is context-free: it can be applied regardless of surroundings. A language is context-free if some CFG generates it.
For the language {aⁿbⁿ | n at least 0}, the grammar is compact:
S → aSb | ε
Every derivation wraps one a on the left and one b on the right, keeping the counts equal, and the ε rule ends it.
Derivations and parse trees
A derivation applies productions from the start symbol until only terminals remain. Deriving the string aabb:
S ⇒ aSb ⇒ aaSbb ⇒ aabb
The last step replaces S with ε. A parse tree shows this structure with S at the root and the terminals read left to right along the leaves. In a leftmost derivation you always expand the leftmost variable; in a rightmost derivation, the rightmost. Both can describe the same parse tree.
Ambiguity in context-free grammars
A grammar is ambiguous if some string has two or more distinct parse trees (equivalently, two distinct leftmost derivations). Ambiguity matters because it makes meaning non-unique, which is fatal for programming-language grammars. The classic ambiguous grammar is E → E + E | E × E | id, where id + id × id parses two ways:
E ⇒ E + E ⇒ id + E ⇒ id + E × E ⇒ id + id × E ⇒ id + id × id
E ⇒ E × E ⇒ E + E × E ⇒ id + E × E ⇒ id + id × E ⇒ id + id × id
The first leftmost derivation makes id × id one subtree, so multiplication binds tighter. The second makes id + id the subtree instead. Same string, two parse trees.
Some context-free languages are inherently ambiguous: no unambiguous grammar exists for them at all. Ambiguity is a property of the grammar; inherent ambiguity is a property of the language.
Normal forms: CNF and GNF
Two standard forms simplify proofs and parsing.
Chomsky Normal Form (CNF): every production is either A → BC (two variables) or A → a (one terminal). Any context-free language without ε has a CNF grammar. CNF gives clean parse trees and underpins the CYK parsing algorithm.
Greibach Normal Form (GNF): every production is A → aα, a single terminal followed by zero or more variables. GNF makes the connection to pushdown automata direct, since each step consumes exactly one input symbol.
Pushdown automata
A pushdown automaton is a finite automaton augmented with a stack. Formally it is a seven-tuple, but the working idea is: on reading an input symbol (or ε), and seeing the top stack symbol, the PDA changes state and replaces the stack top with a string of stack symbols. The stack is the unbounded memory that finite automata lack.
A PDA accepts in one of two equivalent ways: acceptance by final state (input consumed and the machine is in an accepting state) or acceptance by empty stack (input consumed and the stack is empty). The two modes recognise the same class of languages; you can convert either to the other. That equivalence is a nondeterministic-PDA result: a deterministic PDA accepting by empty stack recognises only prefix-free languages.
Determinism costs power here, unlike with finite automata. The aⁿbⁿ machine is deterministic, but even-length palindromes {w wᴿ} need a nondeterministic PDA, because the machine has to guess where the midpoint falls. Deterministic context-free languages are a strict subset of the context-free languages.
A worked PDA for {aⁿbⁿ}
Build a PDA accepting {aⁿbⁿ} by empty stack. Use a bottom marker Z on the stack, a stack symbol X for each a, and two states: q0 while you are reading a's and q1 once the b's have started.
Start in q0 with Z on the stack. In q0, on input a, push one X onto the stack. The stack height records how many a's you have read.
On the first b, if the top is X, pop it and move to q1. That state change is the part that matters: q1 has no transition on a, so any a appearing after a b kills the computation. Without it the machine would accept strings like abab.
In q1, on each further b with X on top, pop one X. Each b cancels one earlier a.
When the input ends with only Z on the stack, pop Z on ε to empty the stack and accept. (The empty string is accepted straight from q0, which is correct: n = 0 gives ε.)
Trace aabb: read a (push X, stack XZ), read a (push X, stack XXZ), read b (pop X, move to q1, stack XZ), read b (pop X, stack Z), input ends, pop Z on ε, stack empty, accept. Two rejections are worth tracing too. On aab, one X is left unpopped, so the stack never empties. On abab, the machine reaches q1 after the first b and then reads an a, for which q1 has no move, so the computation dies. That is the right outcome, because abab belongs to (ab)ⁿ, not to aⁿbⁿ. Confusing those two languages is a standard exam trap. That push-on-a, pop-on-b behaviour is exactly the counting a finite automaton cannot do.
CFG and PDA equivalence
A central theorem: a language is context-free if and only if some pushdown automaton accepts it. Every CFG can be converted to an equivalent PDA (the GNF form makes this mechanical), and every PDA can be converted to an equivalent CFG. So CFGs and PDAs are two descriptions of one class, the context-free languages.
Closure properties and the pumping lemma
Context-free languages are closed under union, concatenation, and Kleene star, and under intersection with a regular language. They are not closed under intersection or complement in general. These non-closures are frequent exam traps.
To prove a language is not context-free, use the pumping lemma for CFLs. It states that for any CFL there is a length p such that any string of length at least p can be split into five parts uvxyz, with the middle vy non-empty and vxy bounded by p, so that uvⁱxyⁱz stays in the language for every i at least 0. The language {aⁿbⁿcⁿ} fails this test, proving it is not context-free.
How CFGs and PDAs are tested in GATE, NET, and placements
GATE CS asks you to decide whether a grammar is ambiguous, convert to CNF, construct a CFG or PDA for a given language, apply the pumping lemma to show a language is not context-free, and pick which closure property holds. The equivalence of the two PDA acceptance modes is a recurring conceptual item. Practise with the solved Theory of Computation context-free grammars MCQs.
UGC NET Computer Science favours the definitions and the Chomsky-hierarchy placement: type-2 grammars, CNF versus GNF, and closure results as direct recall.
Placement and company tests touch the practical edge: balanced-parenthesis checking with a stack, and why a regular expression cannot match nested brackets, which is the CFG-versus-regular boundary in disguise.
The short version
CFGs generate context-free languages, PDAs recognise them with a stack, and the two are provably equivalent. Master derivations and parse trees, spot ambiguity, know CNF and GNF, use the pumping lemma to rule languages out, and remember which closures hold. Build the {aⁿbⁿ} grammar and its PDA by hand until the push-and-pop is automatic. The full Theory of Computation learn module and GATE Guidance by Sanchit Sir place this between finite automata and Turing machines. For a structured route, begin at the GATE CS exam category. Learn the worked pair cold, and this topic becomes reliable marks.
