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. Let us build both and match them on one concrete language.
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.
[DIAGRAM: The parse tree for aabb under S to aSb. Root S with children a, S, b; the middle S has children a, S, b; the innermost S has a single child ε. Reading the leaves left to right spells a a ε b b, that is aabb.]
Ambiguity
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. Some context-free languages are inherently ambiguous: no unambiguous grammar exists for them at all. Note that ambiguity is a property of the grammar, while 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.
A worked PDA for {aⁿbⁿ}
Build a PDA accepting {aⁿbⁿ} by empty stack. Use a bottom marker Z on the stack and a stack symbol X for each a.
Start with Z on the stack. For every input a, push one X onto the stack. The stack height records how many a's you have read.
On the first b, and every b after, if the top is X, pop it. Each b cancels one earlier a.
When input ends, if you have popped exactly as many X's as you pushed, the stack holds only Z; pop Z on ε to empty the stack and accept.
Trace aabb: read a (push X, stack XZ), read a (push X, stack XXZ), read b (pop X, stack XZ), read b (pop X, stack Z), input ends, pop Z on ε, stack empty, accept. If the string were aab, one X would remain unpopped, so the stack never empties and the string is rejected. 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.