Martin

John C. Martin · Fourth edition

Definition 3.1 · Regular languages

If Σ\Sigma is an alphabet, the set R\mathcal R of regular languages over Σ\Sigma is defined as follows.

  1. The language ∅\varnothing is an element of R\mathcal R, and for every a∈Σa\in\Sigma, the language {a}\{a\} is in R\mathcal R.
  2. For any two languages L1L_1 and L2L_2 in R\mathcal R, the three languages
L1∪L2,L1L2,L1∗L_1\cup L_2,\qquad L_1L_2,\qquad L_1^*

are elements of R\mathcal R.

Construction by stages

Start with the base languages:

R0={∅}∪{{a}:a∈Σ}.R_0=\{\varnothing\}\cup\bigl\{\{a\}:a\in\Sigma\bigr\}.

At each stage, keep the preceding languages and apply each operation once to members of that stage:

Rn+1=Rn∪{L∪K:L,K∈Rn}∪{LK:L,K∈Rn}∪{L∗:L∈Rn}.\begin{aligned} R_{n+1}={}&R_n\\[3pt] &{}\cup\{L\cup K:L,K\in R_n\}\\[3pt] &{}\cup\{LK:L,K\in R_n\}\\[3pt] &{}\cup\{L^*:L\in R_n\}. \end{aligned}

The complete class is the union of all stages:

R0⊆R1⊆R2⊆⋯ ,R=⋃n≥0Rn.R_0\subseteq R_1\subseteq R_2\subseteq\cdots,\qquad \mathcal R=\bigcup_{n\ge0}R_n.
Rows2

R0=R_0=

{,,}

R1=R_1=

{,,,,,,,,,,}