Concepts of Languages and Grammars

Learn what a formal language is, how a grammar defines it, and how the Chomsky Hierarchy organises all languages into four nested levels.

What is a Formal Language?

In everyday life, a language is a system of words and rules we use to communicate. In computer science, a formal language is a mathematically precise version of that idea.

A formal language is built from three building blocks:

1. Alphabet (Σ) A finite, non-empty set of symbols. These are the only characters that may appear in strings.

Alphabet	Symbols
Σ = {0, 1}	binary digits
Σ = {a, b}	two letters
Σ = {a, b, c}	three letters

2. String (Word) A finite sequence of symbols taken from the alphabet. The empty string ε contains zero symbols.

Example

Σ = {a, b}

Some strings over Σ:

ε (empty string, length 0)

a (length 1)

ab (length 2)

aab (length 3)

bba (length 3)

3. Language (L) A (possibly infinite) set of strings over Σ.

Example

L₁ = {ab, aabb, aaabbb, ...} ← strings with equal a's then b's

L₂ = {ε, a, aa, aaa, ...} ← any number of a's (including none)

L₃ = {0, 1, 00, 01, 10, 11} ← all binary strings of length 1 or 2

Two special languages:

∅ — the empty language (contains no strings at all)
{ε} — a language containing only the empty string (one member, but it has zero symbols)

What is a Grammar?

A grammar is a finite set of rules that tells you how to generate (or recognise) all strings in a language. Instead of listing every string (which is impossible when the language is infinite), you write a small rulebook.

Formally, a grammar is a 4-tuple:

Example

G = ( V, T, P, S )

Symbol	Name	Meaning
V	Variables / Non-terminals	Placeholder symbols — get replaced by rules
T	Terminals	Actual output symbols from the alphabet Σ
P	Production Rules	The replacement rules themselves
S	Start Symbol	The one non-terminal you begin with (S ∈ V)

Rule of thumb: Terminals are what end up in the final string. Non-terminals are scaffolding that help you build it.

A Concrete Example

Let us define a grammar for the language L = {aⁿbⁿ | n ≥ 1} = {ab, aabb, aaabbb, …}

Example

G = ( V, T, P, S )

V = { S }

T = { a, b }

S = S

P = { S → aSb, S → ab }

Reading the rules:

S → ab means "S can be replaced by the string ab"
S → aSb means "S can be replaced by aSb, wrapping itself with one a on the left and one b on the right"

Deriving "aaabbb":

Example

→ aSb (apply S → aSb)

→ aaSbb (apply S → aSb again)

→ aaabbb (apply S → ab)

Each arrow (→) is one derivation step where we apply exactly one production rule.

Production Rules Up Close

A production rule has the form:

Example

left-hand side → right-hand side

α → β

α contains at least one non-terminal (it is what gets replaced)
β can be any combination of terminals and non-terminals, or ε

The process of applying rules repeatedly is called derivation. Using ⟹* to mean "derives in zero or more steps":

Example

If S ⟹* w and w contains only terminals,

then w is a sentence (valid string) of the language.

Sentential Form vs Sentence

Term	Definition	Example (from above grammar)
Sentential form	Any string reachable from S, may still have non-terminals	S, aSb, aaSbb
Sentence	A sentential form with NO non-terminals left	ab, aabb, aaabbb

The Language Generated by G

Example

L(G) = { w ∈ T* | S ⟹* w }

This reads: "The language of G is the set of all terminal strings w that can be derived from the start symbol S."

The Chomsky Hierarchy

Noam Chomsky classified all grammars (and therefore all formal languages) into four types based on how restrictive their production rules are. Each type is a subset of the one above it.

Example

Type 0 ⊇ Type 1 ⊇ Type 2 ⊇ Type 3

Type 0 — Unrestricted

No restrictions on rules. Most powerful.

Type 1 — Context-Sensitive

Rules can depend on surrounding context.

Type 2 — Context-Free

Rules replace one non-terminal at a time.

Type 3 — Regular

Rules are linear (left or right). Least powerful.

Type	Grammar	Language Class	Recogniser	Example Language
0	Unrestricted	Recursively Enumerable	Turing Machine	Any computable language
1	Context-Sensitive (CSG)	Context-Sensitive	Linear-Bounded Automaton	{aⁿbⁿcⁿ \| n ≥ 1}
2	Context-Free (CFG)	Context-Free	Pushdown Automaton	{aⁿbⁿ \| n ≥ 1}
3	Regular (RG)	Regular	Finite Automaton (DFA/NFA)	{aⁿ \| n ≥ 0}

Key insight: As you move down the hierarchy, the rules become more restricted, the languages become simpler, and the machines needed to recognise them become less powerful.

Programming languages are mostly context-free (Type 2). Regular expressions match regular languages (Type 3). Most compilers use a CFG for parsing.

Why Grammars Matter in Compilers

Every programming language you write code in is defined by a grammar. That grammar is what allows a compiler to:

Check syntax — "Is this a valid statement?"
Build a parse tree — break the code into a structured tree
Generate code — walk the tree to produce output

Example

Source code: int x = a + b;

Grammar rule: Declaration → Type Identifier = Expr ;

Grammar rule: Expr → Expr + Term | Term

Grammar rule: Term → Identifier | Number

Parse tree:

Declaration

/ | | | \

Type ID = Expr ;

(int) (x) / \

Expr Term

(a) (b)

\ /

(+)

Without a grammar, there is no systematic way to understand the structure of source code. The grammar is the backbone of every compiler's front end.

What is a Formal Language?

In everyday life, a language is a system of words and rules we use to communicate. In computer science, a formal language is a mathematically precise version of that idea.

A formal language is built from three building blocks:

1. Alphabet (Σ) A finite, non-empty set of symbols. These are the only characters that may appear in strings.

Alphabet	Symbols
Σ = {0, 1}	binary digits
Σ = {a, b}	two letters
Σ = {a, b, c}	three letters

2. String (Word) A finite sequence of symbols taken from the alphabet. The empty string ε contains zero symbols.

Example

Σ = {a, b}

Some strings over Σ:

ε (empty string, length 0)

a (length 1)

ab (length 2)

aab (length 3)

bba (length 3)

3. Language (L) A (possibly infinite) set of strings over Σ.

Example

L₁ = {ab, aabb, aaabbb, ...} ← strings with equal a's then b's

L₂ = {ε, a, aa, aaa, ...} ← any number of a's (including none)

L₃ = {0, 1, 00, 01, 10, 11} ← all binary strings of length 1 or 2

Two special languages:

∅ — the empty language (contains no strings at all)
{ε} — a language containing only the empty string (one member, but it has zero symbols)

What is a Grammar?

Formally, a grammar is a 4-tuple:

Example

G = ( V, T, P, S )

Symbol	Name	Meaning
V	Variables / Non-terminals	Placeholder symbols — get replaced by rules
T	Terminals	Actual output symbols from the alphabet Σ
P	Production Rules	The replacement rules themselves
S	Start Symbol	The one non-terminal you begin with (S ∈ V)

Rule of thumb: Terminals are what end up in the final string. Non-terminals are scaffolding that help you build it.

A Concrete Example

Let us define a grammar for the language L = {aⁿbⁿ | n ≥ 1} = {ab, aabb, aaabbb, …}

Example

G = ( V, T, P, S )

V = { S }

T = { a, b }

S = S

P = { S → aSb, S → ab }

Reading the rules:

S → ab means "S can be replaced by the string ab"
S → aSb means "S can be replaced by aSb, wrapping itself with one a on the left and one b on the right"

Deriving "aaabbb":

Example

→ aSb (apply S → aSb)

→ aaSbb (apply S → aSb again)

→ aaabbb (apply S → ab)

Each arrow (→) is one derivation step where we apply exactly one production rule.

Production Rules Up Close

A production rule has the form:

Example

left-hand side → right-hand side

α → β

α contains at least one non-terminal (it is what gets replaced)
β can be any combination of terminals and non-terminals, or ε

The process of applying rules repeatedly is called derivation. Using ⟹* to mean "derives in zero or more steps":

Example

If S ⟹* w and w contains only terminals,

then w is a sentence (valid string) of the language.

Sentential Form vs Sentence

Term	Definition	Example (from above grammar)
Sentential form	Any string reachable from S, may still have non-terminals	S, aSb, aaSbb
Sentence	A sentential form with NO non-terminals left	ab, aabb, aaabbb

The Language Generated by G

Example

L(G) = { w ∈ T* | S ⟹* w }

This reads: "The language of G is the set of all terminal strings w that can be derived from the start symbol S."

The Chomsky Hierarchy

Noam Chomsky classified all grammars (and therefore all formal languages) into four types based on how restrictive their production rules are. Each type is a subset of the one above it.

Example

Type 0 ⊇ Type 1 ⊇ Type 2 ⊇ Type 3

Type 0 — Unrestricted

No restrictions on rules. Most powerful.

Type 1 — Context-Sensitive

Rules can depend on surrounding context.

Type 2 — Context-Free

Rules replace one non-terminal at a time.

Type 3 — Regular

Rules are linear (left or right). Least powerful.

Type	Grammar	Language Class	Recogniser	Example Language
0	Unrestricted	Recursively Enumerable	Turing Machine	Any computable language
1	Context-Sensitive (CSG)	Context-Sensitive	Linear-Bounded Automaton	{aⁿbⁿcⁿ \| n ≥ 1}
2	Context-Free (CFG)	Context-Free	Pushdown Automaton	{aⁿbⁿ \| n ≥ 1}
3	Regular (RG)	Regular	Finite Automaton (DFA/NFA)	{aⁿ \| n ≥ 0}

Key insight: As you move down the hierarchy, the rules become more restricted, the languages become simpler, and the machines needed to recognise them become less powerful.

Programming languages are mostly context-free (Type 2). Regular expressions match regular languages (Type 3). Most compilers use a CFG for parsing.

Why Grammars Matter in Compilers

Every programming language you write code in is defined by a grammar. That grammar is what allows a compiler to:

Check syntax — "Is this a valid statement?"
Build a parse tree — break the code into a structured tree
Generate code — walk the tree to produce output

Example

Source code: int x = a + b;

Grammar rule: Declaration → Type Identifier = Expr ;

Grammar rule: Expr → Expr + Term | Term

Grammar rule: Term → Identifier | Number

Parse tree:

Declaration

/ | | | \

Type ID = Expr ;

(int) (x) / \

Expr Term

(a) (b)

\ /

(+)

Without a grammar, there is no systematic way to understand the structure of source code. The grammar is the backbone of every compiler's front end.