Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 59 · Regular Expressions and Languages

Regular Expressions, Regular Grammars and Regular Languages

Learn the formal definition of regular expressions, the languages they describe, algebraic identities, regular grammars and star height, with Python examples.

You have written regular expressions in editors and programming languages. In the theory of computation, a regular expression is a precise algebraic notation for a language, built from just three operations, and it describes exactly the class of languages that finite automata recognize. This lesson gives the formal definition, the core identities, the link to regular grammars, and a way to measure how "nested" an expression is.

The formal definition

Regular expressions over an alphabet Σ are defined by induction. Base cases:

  • ∅ is a regular expression denoting the empty language.
  • ε is a regular expression denoting the language {ε}.
  • Each symbol a in Σ is a regular expression denoting {a}.

Inductive cases: if R and S are regular expressions, so are

  • Union R + S (often written R | S), denoting L(R) ∪ L(S).
  • Concatenation RS, denoting L(R)L(S).
  • Kleene star R*, denoting L(R)*: zero or more strings of L(R) joined together.

Parentheses group, and by convention star binds tightest, then concatenation, then union. So ab*+c means (a(b*)) + c. A language is regular if some regular expression denotes it. Because a language is regular if and only if some DFA recognizes it (see Kleene's theorem), the two views are interchangeable.

Examples

Expression Language
(a+b)* all strings over {a, b}
a*b* any a's followed by any b's
(a+b)*abb strings ending in abb
(0+1)*00(0+1)* binary strings containing 00
(aa)* an even number of a's, only a's
(a+b)(a+b) exactly the four strings of length 2
a(a+b)*a + a strings that start and end with the same letter a

Computing the language of an expression

A regular expression is a tree, and its language can be computed bottom-up. The code below represents expressions as nested tuples, enumerates the language up to a length cutoff, and compares the result with Python's own re engine on every string up to length 6.

Python Regular expressions as trees: languages and star height

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both languages agree, and the star heights are 1 and 2. Star height is the maximum nesting depth of stars in an expression; for a language it is the minimum over all expressions that denote it. Star height 0 means a finite language. Many languages that look like they need nested stars can be rewritten with fewer: (a*b)* equals ε + (a+b)*b, with star height 1. Eggan's theorem links the star height of a language to the structure of its automata, and for some languages (like those whose automaton has complex loops) the star height can be arbitrarily large.

Algebraic identities

Regular expressions obey laws that help you simplify them. Here R, S and T are any regular expressions:

  • Union: R + S = S + R; R + R = R; R + ∅ = R; (R + S) + T = R + (S + T).
  • Concatenation: (RS)T = R(ST); εR = Rε = R; ∅R = R∅ = ∅. Concatenation is not commutative: ab differs from ba.
  • Distribution: R(S + T) = RS + RT; (S + T)R = SR + TR.
  • Star: ∅* = ε; ε* = ε; (R*)* = R*; R*R* = R*; RR* = R*R = R⁺; (R + ε)* = R*.
  • Combining: (R + S)* = (R*S*)* = (R* + S*)*.

The last identity is why (a+b)* and (a*b*)* mean the same thing, which surprises many beginners. The identities are also what makes the Arden's theorem method of extracting expressions from automata work.

Regular grammars

A regular grammar is a Type 3 grammar from the Chomsky hierarchy. The right-linear form allows only productions A → aB, A → a and A → ε, where a is a terminal and A, B are variables. (The left-linear form has A → Ba instead; mixing both in one grammar breaks the guarantee and can generate non-regular languages.)

Right-linear grammars and NFAs are the same thing in different notation: each variable is a state, and each production A → aB is a transition from A to B on a. A production A → a or A → ε sends the machine to an accepting state. Here is a grammar for (a+b)*abb:

TEXT
S -> aS | bS | aA
A -> bB
B -> bC
C -> ε
flowchart LR
    start(( )) --> S
    S(("S")) -->|"a, b"| S
    S -->|"a"| A(("A"))
    A -->|"b"| B(("B"))
    B -->|"b"| C((("C")))

Each production becomes an arrow. C accepts because it has the production C → ε.

Python Run a regular grammar as an NFA

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The grammar view and the regex view agree on every word. This shows the three descriptions of the same class: regular expressions, regular grammars and finite automata. The next lesson shows how to compile an expression into an automaton automatically.

Properties of regular expressions worth remembering

  • Every finite language is regular (just union its strings).
  • Regular expressions have no memory beyond the pattern: they cannot match a^n b^n or balanced parentheses. The pumping lemma proves this rigorously.
  • Practical regex dialects (backreferences like (a+)\1) go beyond the formal definition and can match non-regular languages, but then they no longer run in linear time.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Which regular expression describes all binary strings that end in 01?

    (0+1)* allows any prefix, and 01 forces the ending. The other expressions describe strings starting with 01, or other patterns.
  2. 2. Which identity is true for regular expressions?

    (R+S)* and (RS)* denote the same language. Concatenation is not commutative, R* contains ε but R+ may not, and ∅* = ε, not ∅.
  3. 3. What is the star height of (ab)?

    There is a star around the whole expression and another star nested inside it, so the nesting depth is 2.
  4. 4. A production like A → aB in a regular grammar corresponds to what in an NFA?

    In a right-linear grammar, each variable is a state and each production A → aB is a transition A --a--> B.
  5. 5. Why can no regular expression describe a^n b^n?

    Regular languages are those recognized by finite automata, which cannot remember an unbounded count.

Summary

  • Regular expressions are built from ∅, ε and symbols using union, concatenation and star; they denote exactly the regular languages.
  • Identities like (R+S)* = (RS)* let you simplify expressions; concatenation is not commutative.
  • Star height measures the nesting depth of stars; finite languages have star height 0.
  • Right-linear grammars are NFAs in grammar form, so regex, grammar and automaton describe the same class.

Next: From Regular Expressions to Finite Automata