Context-Free Languages and BNF

Regular languages (handled by FSMs and regex) are limited — they cannot describe nested or recursive structures like balanced parentheses or the syntax of programming languages. Context-free languages (CFLs) are a more powerful class that can handle these patterns. They are defined by context-free grammars (CFGs), often written in Backus-Naur Form (BNF).

---

The Chomsky Hierarchy

Languages are classified by their complexity in the Chomsky hierarchy:

Level	Language Type	Recognised By	Example
3	Regular	Finite State Machine	ab
2	Context-Free	Pushdown Automaton	aⁿbⁿ
1	Context-Sensitive	Linear-Bounded Automaton	aⁿbⁿcⁿ
0	Recursively Enumerable	Turing Machine	Any computable language

Each level is strictly more powerful than the one below it. Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable.

---

Context-Free Grammars (CFGs)

A context-free grammar consists of:

Component	Symbol	Description
Terminals	lowercase letters, symbols	The actual characters in the language (e.g., a, b, +, (, ))
Non-terminals	UPPERCASE or	Variables that can be replaced by other symbols
Production rules	→ or ::=	Rules for replacing non-terminals with sequences of terminals and non-terminals
Start symbol	S or	The non-terminal from which derivation begins

Example: aⁿbⁿ

S → aSb | ε

Derivations:

• S → ε (empty string)
• S → aSb → aεb = ab
• S → aSb → aaSbb → aaεbb = aabb
• S → aSb → aaSbb → aaaSbbb → aaaεbbb = aaabbb

This grammar generates exactly the language {ε, ab, aabb, aaabbb, ...} = {aⁿbⁿ : n ≥ 0}.

An FSM cannot recognise this language — it would need to count the a's and match them with the b's, requiring unbounded memory.

---

Backus-Naur Form (BNF)

BNF is a notation for writing context-free grammars, widely used to define the syntax of programming languages.

BNF Syntax

Symbol	Meaning
::=	"is defined as" (replaces →)
|	"or" (alternative production)
< >	Enclose non-terminal names

Example: Simple Arithmetic Expressions

<expression> ::= <term> | <expression> + <term> | <expression> - <term>
<term>       ::= <factor> | <term> * <factor> | <term> / <factor>
<factor>     ::= <number> | ( <expression> )
<number>     ::= <digit> | <number> <digit>
<digit>      ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

This grammar defines expressions like: 3 + 4 * (2 - 1)