Regular Expressions and Kleene's Theorem

By [L1], every regular expression has a finite construction tree, so there is a well-founded induction on the number of constructor occurrences in that tree.

In the base cases $R=\mathrm{\varnothing }$, $R=\epsilon$, and $R=a$, the language is uniquely fixed by [L2]. If $R$ is composite, then its outermost constructor is uniquely one of $+$, concatenation, or ${}^{\ast }$ by [L1]. The induction hypothesis gives unique denotations to the immediate subexpressions, and then [L2] applies one fixed language operation to those already determined languages.

Therefore exactly one language $\mathcal{L}(R)$ satisfies the recursive clauses for the given expression $R$.

We construct $N_R$ by induction on the structure of $R$, maintaining one designated start state and one designated accepting state, with that designated state as the entire accepting set. For the base expressions, use: a two-state gadget with no transition to its accepting state for $\mathrm{\varnothing }$; a two-state gadget joined by one $\epsilon$-edge for $\epsilon$; and a two-state gadget with one $a$-edge for a letter $a\in \mathrm{\Sigma }$.

For $R+S$, add a fresh start state with $\epsilon$-edges to the starts of the machines for $R$ and $S$, and a fresh accepting state reached by $\epsilon$-edges from their old accepting states; only the fresh state is accepting. For $RS$, connect the accepting state of the machine for $R$ to the start state of the machine for $S$ by an $\epsilon$-edge, make the former nonaccepting, and retain only the accepting state of the machine for $S$. For $R^{\ast }$, add fresh start and accepting states, an $\epsilon$-edge from the new start to the new accept, an $\epsilon$-edge from the new start into the old start, and $\epsilon$-edges from the old accept both back to the old start and to the new accept; only the new accept is accepting.

The base gadgets recognize exactly $\mathrm{\varnothing }$, $\{\epsilon \}$, and $\{a\}$. By [L3], the union gadget accepts exactly when one branch accepts, the concatenation gadget accepts exactly when a word splits into a word accepted by the first machine followed by one accepted by the second, and the star gadget accepts exactly when the input is a concatenation of finitely many words accepted by the submachine. Using [L1] and the uniqueness from [L2], the induction follows for every constructor.

Hence the constructed epsilon-NFA $N_R$ recognizes precisely $\mathcal{L}(R)$.

Let $w\in P_{K\cup \{r\}}^G(p,q)$, witnessed by a path $p=s_0,s_1,\dots ,s_n=q$ whose intermediate states lie in $K\cup \{r\}$ and by a factorization $w=w_1\cdots w_n,w_j\in \mathcal{L}(\lambda (s_{j-1},s_j))\mathrm{.}$ Delete every occurrence of $r$ from the state list, keeping the surviving states in order: $p=t_0,t_1,\dots ,t_m=q\mathrm{.}$ For each consecutive pair $t_{j-1},t_j$, the deleted portion between them is either empty or consists of one entrance into $r$, zero or more $r$-to-$r$ loops, and one exit from $r$. Therefore the corresponding subword of $w$ lies in the language of the updated label ${\lambda }^{\mathrm{\prime }}(t_{j-1},t_j)$ from [L2]. Using the same surviving-state list and these compressed subwords gives a witness that $w\in P_K^{G\setminus r}(p,q)$.

Conversely, let $w\in P_K^{G\setminus r}(p,q)$, witnessed by a surviving-state path $p=t_0,t_1,\dots ,t_m=q$ with intermediate states in $K$ and by subwords in the denoted languages of the updated labels ${\lambda }^{\mathrm{\prime }}(t_{j-1},t_j)$. For each such subword, [L2] says that it is either an old direct $t_{j-1}$-to-$t_j$ word or a concatenation of an old $t_{j-1}$-to-$r$ word, finitely many old $r$-to-$r$ words, and an old $r$-to-$t_j$ word. Expanding every updated edge in this way inserts only the eliminated state $r$ between surviving states, so the resulting path in $G$ has all intermediate states in $K\cup \{r\}$. Hence $w\in P_{K\cup \{r\}}^G(p,q)$.

Steps 1.1 and 1.2 prove the two inclusions, so the two path languages are equal.

Form a GNFA $G_0$ by adjoining a new start state $s$ and a new accept state $t$ to the DFA states. Put the label $\epsilon$ on $s\to q_0$ and on each edge $f\to t$ with $f\in F$. For DFA states $p,q\in Q$, label $p\to q$ by the union of all letters $a\in \mathrm{\Sigma }$ with $\delta (p,a)=q$, and use $\mathrm{\varnothing }$ on every remaining ordered pair. By [L4], a word is accepted by $D$ exactly when it labels a path from $s$ to $t$ through the old DFA states, so $L(D)=P_Q^{G_0}(s,t)$.

Eliminate the states of $Q$ one at a time. At each step use the update from [L2]. By [L3], after each elimination the start-to-accept path language is unchanged. Therefore, when all interior states have been removed, the resulting two-state GNFA $G_f$ still satisfies $L(G_f)=L(D)$.

In $G_f$ the only possible accepting paths go directly from $s$ to $t$, so by [L1] the accepted language is exactly the denotation of the sole label on that edge. Hence some regular expression denotes $L(D)$.

Suppose first that $\mathcal{L}(R)=L$ for some regular expression $R$. By [L2], there is an epsilon-NFA recognizing $L$, and by [L3] there is then a DFA recognizing the same language. Therefore [L1] implies that $L$ is regular.

Conversely, suppose that $L$ is regular. By [L1], some DFA $D$ recognizes $L$. Then [L4] gives a regular expression $R$ with $\mathcal{L}(R)=L(D)=L$.

Steps 1.1 and 1.2 prove the forward and reverse implications.

Choose a regular expression $R$ over $\mathrm{\Sigma }$ with $\mathcal{L}(R)=L$ by [L4]. For each letter $a\in \mathrm{\Sigma }$, choose a regular expression $E_a$ over $\mathrm{\Delta }$ that denotes the single word $h(a)$: if $h(a)=\epsilon$ take $E_a=\epsilon$, and if $h(a)=b_1\cdots b_n$ with $n\ge 1$, take the concatenation $E_a:=b_1\cdots b_n$.

Define $T(R)$ by recursively replacing each occurrence of a letter $a$ in $R$ by $E_a$, while leaving $\mathrm{\varnothing }$ and $\epsilon$ fixed and commuting with $+$, concatenation, and ${}^{\ast }$. By [L3], this gives one well-defined regular expression over $\mathrm{\Delta }$.

A structural induction on $R$ using [L1] and [L2] shows that $\mathcal{L}(T(R))=\{\widehat{h}(w):w\in \mathcal{L}(R)\}$. Since $\mathcal{L}(R)=L$, this language is exactly $\widehat{h}[L]$. Therefore $\widehat{h}[L]$ is denoted by a regular expression and is regular.

Choose a DFA $D=(Q,\mathrm{\Delta },\delta ,q_0,F)$ with $L(D)=K$ by [L4]. Define a DFA $D_h$ over $\mathrm{\Sigma }$ with the same state set, start state, and accepting set by ${\delta }_h(q,a):={\delta }^{\ast }(q,h(a))$ for each $q\in Q$ and $a\in \mathrm{\Sigma }$.

We claim that for every word $w\in {\mathrm{\Sigma }}^{\ast }$ one has ${\delta }_h^{\ast }(q_0,w)={\delta }^{\ast }(q_0,\widehat{h}(w))$. The proof is by induction on $\mathrm{\mid }w\mathrm{\mid }$: for $w=\epsilon$ both sides equal $q_0$, and appending one letter $a$ updates the left-hand side by ${\delta }_h(-,a)$ and the right-hand side by the block $h(a)$, exactly as [L1] and [L2] prescribe.

By [L3] and step 2.1, the DFA $D_h$ accepts $w$ exactly when $D$ accepts $\widehat{h}(w)$, that is, exactly when $\widehat{h}(w)\in K$. Thus $L(D_h)={\widehat{h}}^{-1}(K)$, so the inverse image is regular.

For the right quotient, first build the product DFA of $D_L$ and $D_K$ from [L4]. Declare a state $q\in Q_L$ to be accepting in a new DFA $D_R$ exactly when some word $y$ drives the product machine from $(q,q_K)$ to a state of $F_L\times F_K$. The transition graph of $D_R$ is otherwise the same as that of $D_L$.

For the left quotient, let $S:=\{{\delta }_L^{\ast }(q_L,x):x\in K\}\subseteq Q_L$. Add a fresh start state $s$ with an $\epsilon$-edge from $s$ to each state of $S$, keep the letter transitions of $D_L$ on the old state set $Q_L$, and keep $F_L$ as the accepting set. This gives an epsilon-NFA $N_L$.

If $D_R$ reads $x$ and ends in the state $q={\delta }_L^{\ast }(q_L,x)$, then by construction $q$ is accepting exactly when some $y\in K$ also takes $D_L$ from $q$ to a state of $F_L$. By [L1], this is equivalent to $xy\in L$ for some $y\in K$. Hence $L(D_R)=L\mathrm{/}K$.

By [L2], a word $y$ is accepted by $N_L$ exactly when some state of $S$ reaches a state of $F_L$ after reading $y$. By the definition of $S$ and then [L1], this happens exactly when there exists $x\in K$ with $xy\in L$. Therefore $L(N_L)=K^{-1}L$.

Step 2.1 shows that the right quotient is recognized by a DFA. Step 2.2 shows that the left quotient is recognized by an NFA, so [L3] makes it regular. Thus both quotients are regular.

Membership is decidable by simulating the DFA on the finitely many letters of the input word and checking, via [L1], whether the final state is accepting.

Emptiness is decidable by a graph search from the start state through the finite transition graph: by [L1], the language is empty exactly when no accepting state is reachable.

Finiteness is decidable by restricting to states that are reachable from the start state and can themselves reach an accepting state. If that finite subgraph contains a directed cycle, then one may loop around the cycle arbitrarily many times before taking a path to acceptance, producing infinitely many accepted words. If it contains no directed cycle, then every accepting run has bounded length, so only finitely many words are accepted.

Given DFA's $D_1,D_2$, use [L3] to complement either machine and then [L2] to build DFA's for the two differences $L(D_1)\setminus L(D_2)$ and $L(D_2)\setminus L(D_1)$ and for their union. By [A1], that union is the symmetric difference, so $D_1$ and $D_2$ are equivalent exactly when the resulting DFA has empty language. Step 1.2 therefore decides equivalence.

The same constructions give a DFA for $L(D_1)\setminus L(D_2)$. By [A1], the containment $L(D_1)\subseteq L(D_2)$ holds exactly when this difference language is empty, so step 1.2 also decides containment.

Steps 1.1, 1.2, 2.1, 2.2, and 3.1 decide membership, emptiness, finiteness, equivalence, and containment respectively.

The object $a+b$ is, by [L1], a syntactic expression tree with an outer union node and two letter leaves.

The object $\mathcal{L}(a+b)$ is, by [L2], the two-element set $\{a,b\}$ of words.

A formal expression tree and a two-element set of words are not literally the same kind of object, so [A1] is false.

Eliminate $p$ first. Applying [L1] without any algebraic simplification, and then eliminating $q$, gives the final label $(\mathrm{\varnothing }+a{\mathrm{\varnothing }}^{\ast }b)+(a+a{\mathrm{\varnothing }}^{\ast }\mathrm{\varnothing })(\mathrm{\varnothing }+\mathrm{\varnothing }{\mathrm{\varnothing }}^{\ast }\mathrm{\varnothing }{)}^{\ast }(c+\mathrm{\varnothing }{\mathrm{\varnothing }}^{\ast }b)$.

Eliminating $q$ first and then $p$ instead gives $(\mathrm{\varnothing }+a{\mathrm{\varnothing }}^{\ast }c)+(a+a{\mathrm{\varnothing }}^{\ast }\mathrm{\varnothing })(\mathrm{\varnothing }+\mathrm{\varnothing }{\mathrm{\varnothing }}^{\ast }\mathrm{\varnothing }{)}^{\ast }(b+\mathrm{\varnothing }{\mathrm{\varnothing }}^{\ast }c)$.

These are different formal expression trees: already the first displayed outer summand ends in $b$ in step 1.1 and in $c$ in step 1.2. Thus [A1] is false even without imposing any simplification rules.