Deterministic Finite Automata and Regular Languages

Fix $q\in Q$ and a word $w=a_0{a}_1\cdots a_{n-1}$. Define a sequence of states by $s_0=q$ and $s_{i+1}=\delta (s_i,a_i)$ for $0\le i<n$, and then define ${\delta }^{\ast }(q,w):=s_n$. This gives a function $Q\times {\mathrm{\Sigma }}^{\ast }\to Q$ because the DFA transition function supplies exactly one next state at each letter.

If $w=\epsilon$, then $n=0$ and step 1.1 gives ${\delta }^{\ast }(q,\epsilon )=s_0=q$. If $w=ua$ with $u=a_0\cdots a_{n-2}$ and $a=a_{n-1}$, then the last state in the sequence is $s_n=\delta (s_{n-1},a)=\delta ({\delta }^{\ast }(q,u),a)$. So the function from step 1.1 satisfies the two clauses of [L1].

Let $\eta :Q\times {\mathrm{\Sigma }}^{\ast }\to Q$ be any other function satisfying [L1]. We prove by induction on the length of $w$ that $\eta (q,w)={\delta }^{\ast }(q,w)$ for every $q\in Q$. For $w=\epsilon$, both values are $q$ by [L1] and step 2.1.

Assume $\eta (q,u)={\delta }^{\ast }(q,u)$ for all words $u$ of length $n$, and let $w=ua$ have length $n+1$. Then [L1] gives $\eta (q,w)=\delta (\eta (q,u),a)$, and the induction hypothesis turns this into $\delta ({\delta }^{\ast }(q,u),a)={\delta }^{\ast }(q,w)$ by step 2.1.

Steps 3.1 and 3.2 show that every function satisfying [L1] agrees with the function built in step 1.1, so the extended transition function exists and is unique.

We prove the identity by induction on the length of $v$. If $v=\epsilon$, then [L1] gives ${\delta }^{\ast }(p,u\epsilon )={\delta }^{\ast }(p,u)$ and also ${\delta }^{\ast }({\delta }^{\ast }(p,u),\epsilon )={\delta }^{\ast }(p,u)$.

Assume the identity holds for a word $v$, and let $a\in \mathrm{\Sigma }$. We compare the two sides for $va$.

By [L1], ${\delta }^{\ast }(p,uva)=\delta ({\delta }^{\ast }(p,uv),a)\mathrm{.}$ The induction hypothesis turns this into $\delta ({\delta }^{\ast }({\delta }^{\ast }(p,u),v),a)\mathrm{.}$

Applying [L1] again, the last expression is exactly ${\delta }^{\ast }({\delta }^{\ast }(p,u),va)$. Therefore ${\delta }^{\ast }(p,uva)={\delta }^{\ast }({\delta }^{\ast }(p,u),va)$.

Steps 1.1, 2.1, and 3.1 complete the induction on $v$, so ${\delta }^{\ast }(p,uv)={\delta }^{\ast }({\delta }^{\ast }(p,u),v)$ for all $u,v\in {\mathrm{\Sigma }}^{\ast }$.

Define a machine $D$ with state set $P\cup \{\mathrm{\perp }\}$, start state $\epsilon$, accepting set $F=L$, and transition rule $\delta (p,a)=\{\begin{array}{ll}pa,& \text{if }pa\in P,\\ \mathrm{\perp },& \text{if }pa\mathrm{\notin }P,\end{array}\delta (\mathrm{\perp },a)=\mathrm{\perp }\mathrm{.}$ By [F1] the state set is finite, and the transition rule is total on $(P\cup \{\mathrm{\perp }\})\times \mathrm{\Sigma }$.

We claim that, for every word $w$, the run from $\epsilon$ ends at the state $w$ when $w\in P$, and ends at $\mathrm{\perp }$ when $w\mathrm{\notin }P$. This follows by induction on the length of $w$: appending a letter keeps the machine at the longer prefix exactly when that longer word still lies in $P$, and otherwise sends the run to $\mathrm{\perp }$, where it remains.

A word $w$ is accepted by $D$ exactly when the final state lies in $F=L$. By step 1.2 this happens exactly when $w\in L$, because every word in $L$ is one of its own prefixes and therefore belongs to $P$.

Thus $L=L(D)$ for the DFA from step 1.1, so [L1] shows that $L$ is regular.

Define the product machine $D_{\times }$ to have state set $Q_1\times Q_2$, start state $(q_1,q_2)$, and transition rule ${\delta }_{\times }((p,r),a):=({\delta }_1(p,a),{\delta }_2(r,a))\mathrm{.}$ Intuitively, $D_{\times }$ runs the two machines in parallel on the same input.

We claim that for every pair of states $(p,r)$ and every word $w$, ${\delta }_{\times }^{\ast }((p,r),w)=({\delta }_1^{\ast }(p,w),{\delta }_2^{\ast }(r,w))\mathrm{.}$ The claim is proved by induction on the length of $w$: it is immediate for $\epsilon$, and appending one letter updates both coordinates exactly as the component machines do.

If the accepting set is $F_{\cap }:=F_1\times F_2$, then step 1.2 and [L1] show that a word $w$ is accepted exactly when ${\delta }_1^{\ast }(q_1,w)\in F_1$ and ${\delta }_2^{\ast }(q_2,w)\in F_2$, that is, exactly when $w\in L_1\cap L_2$. By [L2], this machine recognizes the intersection.

If the accepting set is $F_{\cup }:=(F_1\times Q_2)\cup (Q_1\times F_2)$, then step 1.2 and [L1] show that a word $w$ is accepted exactly when at least one component machine accepts $w$, that is, exactly when $w\in L_1\cup L_2$. By [L2], this machine recognizes the union.

Therefore the product construction yields DFA's for both intersection and union over the fixed alphabet $\mathrm{\Sigma }$.

The machines $D$ and $D^c$ have the same state set, the same start state, and the same transition function. Therefore, for every word $w\in {\mathrm{\Sigma }}^{\ast }$, they follow exactly the same run and end in the same state ${\delta }^{\ast }(q_0,w)$.

By [L2], the word $w$ is accepted by $D^c$ exactly when this common final state lies in $Q\setminus F$, which is equivalent to saying that it does not lie in $F$. So $w$ is accepted by $D^c$ exactly when $w$ is not accepted by $D$.

Since this equivalence holds for every $w\in {\mathrm{\Sigma }}^{\ast }$, the language of $D^c$ is precisely ${\mathrm{\Sigma }}^{\ast }\setminus L(D)$, which is $L(D{)}^c$ by [L1].

By [L1], choose DFA's recognizing $L$ and $K$. Then [L2] gives DFA's recognizing $L\cup K$ and $L\cap K$, and [L3] gives a DFA recognizing ${\mathrm{\Sigma }}^{\ast }\setminus L$.

The remaining Boolean operations are obtained from union, intersection, and complement by ordinary set identities inside the fixed ambient set ${\mathrm{\Sigma }}^{\ast }$. For instance, $L\setminus K=L\cap ({\mathrm{\Sigma }}^{\ast }\setminus K)$ and the symmetric difference is $(L\setminus K)\cup (K\setminus L)$.

Therefore every Boolean combination of $L$ and $K$ over the fixed alphabet $\mathrm{\Sigma }$ is regular.

Use the same product machine as in [L2], with state set $Q_1\times Q_2$, start state $(q_1,q_2)$, and product transition function. This machine reaches the pair of component states reached by $D_1$ and $D_2$ on the same input word.

Declare a pair $(p,r)$ accepting exactly when $p\in F_1$ and $r\mathrm{\notin }{F}_2$, that is, take accepting set $F:=F_1\times (Q_2\setminus F_2)$.

By step 1.1 and [L3], a word $w$ is accepted by this product machine exactly when $D_1$ accepts $w$ and $D_2$ does not accept $w$.

By [L1], that condition is exactly $w\in L_1\setminus L_2$. So the constructed machine recognizes the language difference.

Let $w=a_0{a}_1\cdots a_{n-1}$ be any input word, and consider the run of $D$ from $q_0$ on $w$. After reading the prefix $a_0\cdots a_{i-1}$, the machine is in the state ${\delta }^{\ast }(q_0,a_0\cdots a_{i-1})$, so [L1] says every state visited during the run is reachable.

Therefore the entire run of $D$ on $w$ stays inside $Q_r$, and the restricted machine $D_r$ has exactly the same transitions on those states. So $D_r$ ends in the same final state as $D$ on the word $w$.

By [L2], the word $w$ is accepted by $D_r$ if and only if that common final state lies in $F\cap Q_r$, which is equivalent to the same final state lying in $F$. Hence $w$ is accepted by $D_r$ exactly when it is accepted by $D$.

Since this holds for every word $w\in {\mathrm{\Sigma }}^{\ast }$, the two machines recognize the same language.

Define $D_B$ to have state set $S_B\cup \{\mathrm{\perp }\}$, start state $\epsilon$, accepting set $S_B$, and transition rule $\delta (s,a)=\{\begin{array}{ll}\text{the published longest-suffix state for }sa,& \text{if }sa\text{ avoids }B,\\ \mathrm{\perp },& \text{if }sa\text{ contains a factor in }B,\end{array}\delta (\mathrm{\perp },a)=\mathrm{\perp }\mathrm{.}$ By [L1] and [L2], this is a total transition function on a finite state set, so $D_B$ is a DFA.

We prove by induction on the length of a word $w$ that the run of $D_B$ from $\epsilon$ behaves as follows: if $w$ avoids $B$, the final state is the longest suffix of $w$ belonging to $S_B$; if $w$ contains a forbidden factor, the final state is $\mathrm{\perp }$. The induction step is exactly the two cases built into the definition of $\delta$ in step 1.1.

If $w$ avoids $B$, then step 2.1 places the run in a state of $S_B$, hence [L3] says that $D_B$ accepts $w$. If $w$ contains a factor in $B$, then step 2.1 places the run in $\mathrm{\perp }$, so [L3] says that $D_B$ rejects $w$.

Therefore $L(D_B)$ is exactly the language of words over $\mathrm{\Sigma }$ that avoid every forbidden factor in $B$.

In the displayed picture, the input pair $(q,0)$ has a specified next state, namely $q$. But the input pair $(q,1)$ has no specified next state at all.

Therefore the picture does not determine a total function on $Q\times \mathrm{\Sigma }$, so by [L1] it does not yet define a DFA.

This contradicts the conclusion of [A1]. The omitted transition really matters: one must add a sink or some other specified $1$-transition to obtain a DFA.

By [L1], the complement of $L(D)=\{0,1{\}}^{\ast }$ is the empty language, obtained by keeping the same looping transitions and changing only the accepting set from $\{q\}$ to $\mathrm{\varnothing }$.

If one literally complements the transition graph instead, both loop edges are removed because they were the only edges present. The resulting picture has no outgoing transition on either input letter, so by [L2] it is not even a DFA.

Thus graph complementation does not produce the complement DFA from step 1.1 and does not in general preserve the DFA conditions. The claim [A1] is false.