Regular Languages

Regular Languages

1. Definition

A regular language is a set of strings accepted by a finite automaton or described by a regular expression. In compilers, almost all lexical tokens (identifiers, numbers, keywords) are regular languages — that is why the scanner uses them.

2. Building Blocks

Operation	Symbol	Example
Union	∪ or 丨	L ∪ M = strings in L or M
Concatenation	juxtaposition	LM = xy where x in L, y in M
Kleene closure	*	L* = 0 or more reps (ε included)
Positive closure	+	L+ = 1 or more reps
Optional	?	L? = ε or L

Alphabet $Σ$ = finite symbols, e.g. $Σ$ = {0,1} or letters + digits. String = finite sequence; ε = empty string; language = set of strings over $Σ$.

3. Regular Languages — Key Properties

• Closed under ∪, concatenation, *, complement, intersection.
• Recognizable with finite memory (no counting/stack needed).
• Not all languages are regular: e.g. { $aⁿbⁿ$ 丨 n ≥ 0 } needs counting → needs grammar/stack, not scanner.

4. Compiler Examples

identifiers: letter (letter 丨 digit)*
unsigned numbers: digit+ (. digit+)? (E (+丨-)? digit+)?
keywords: exact strings (if, else, while) — finite language, hence regular

5. Exam Points

• Define regular language + closure properties — 3-5 marks, frequent.
• Give regular definitions for identifier / number — 5 marks, very frequent.
• Why { $aⁿb�ⁿ$ } is not regular (needs stack) — 3 marks, frequent.