Skip to main content

Regular expressions and regular languages

Short answer

Regular expressions are built from ∅, ε, symbols, and operations +, concatenation, *. A regular language is one described by a regular expression, equivalent to acceptance by a DFA/NFA or generation by a regular grammar. Examples: a*b, (a+b)*aa(a+b)*. They are closed under union, intersection, complement, but cannot count unboundedly (e.g., {a^n b^n} is not regular).

Discuss regular expressions and regular languages in detail with suitable examples.

Regular expressions

Over an alphabet Σ, regular expressions are defined recursively:

  1. ∅ (empty set), ε (empty string) and each symbol a ∈ Σ are regular expressions.
  2. If R and S are regular expressions, so are (R + S) (union), (RS) (concatenation) and R* (Kleene closure).
  3. Nothing else is a regular expression.

Meaning: L(∅) = ∅, L(ε) = {ε}, L(a) = {a}, L(R+S) = L(R) ∪ L(S), L(RS) = L(R)L(S), L(R*) = (L(R)), where R means zero or more repetitions (R⁺ = RR* means one or more).

Regular languages

A language is regular if it can be described by a regular expression. By Kleene's theorem, this is equivalent to being accepted by a DFA, an NFA, or generated by a regular (Type 3) grammar.

Examples

Regular expressionLanguage over {a, b}
a*bany number of a's followed by one b
(a+b)*all strings, including ε
(a+b)aa(a+b)strings containing aa
(a+b)*abbstrings ending in abb
(ab)*ε, ab, abab, ...
a(a+b)*bstrings starting with a and ending with b

Properties

  • Regular languages are closed under union, concatenation, Kleene star, complement, intersection and reversal.
  • Useful identities: R + ∅ = R, Rε = R, R∅ = ∅, (R*)* = R*, (R+S)* = (RS), ε + RR = R*.
  • Languages such as { aⁿbⁿ : n ≥ 0 } are not regular (a finite automaton cannot count without bound); this is shown with the pumping lemma.

Use

Token definition in compilers, pattern search in text, validating input, and designing finite automata.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 2 questions →