Combining DFAs and Regular Languages

Combining DFAs

Last time, we defined DFAs and saw how to design a few for simple languages. However, as the conditions for membership in a language get more complicated, the DFA design is going to get more complicated. It would be nice if we could break a design down into simpler pieces and then compose them in a systematic way. In other words, we’d like to construct DFAs from other DFAs.

To make the upcoming exposition a little less tedious, let’s recall some notation. We can write a DFA over a fixed alphabet $\Sigma$ as a 4-tuple $M = (Q, \delta, s, A)$ where

$Q$ is the set of states,
$\delta: Q \times \Sigma \to Q$ is the transition function,
$s \in Q$ is the start state, and
$A \subseteq Q$ is the subset of accepting states.

We defined the extended transition function $\delta^*: Q \times \Sigma^*$ as $\delta^*(q, w) = \begin{cases} q &\text{if $w = \varepsilon$}\\ \delta^*(\delta(q, a), x) &\text{if $w = ax$}. \end{cases}$

DFA $M$ accepts a set of strings, i.e., a language. Let $\begin{aligned} L(M) :&= \{w \mid \text{$M$ accepts $w$}\}\\ &= \{w \mid \delta^*(s, w) \in A\} \end{aligned}$ denote the language of (or accepted by) machine $M$ . For example, consider the following DFA that accepts those binary strings $w$ with the substring 11.¹ A DFA accepting binary strings that contain the substring 11

Let’s name the above DFA $M_{11}$ . The set of binary strings with the substring 11 is therefore $L(M_{11})$ . Note that there are an infinite number of other machines that share the same language!

I’m using the not-quite-so-useful $s$ , $a$ , and $b$ for state names here, because this figure was taken directly from Jeff Erickson’s notes. The reason for doing so will become clear when it’s time to have copy-pasted a big DFA built from this and another DFA.

Now, suppose we don’t like 11. We want to avoid it. Is there a machine $M'$ such that $L(M') = \overline{L(M_{11})} = \Sigma^* \setminus L(M_{11})$ ? Well, we want our new machine to accept exactly when $M_{11}$ rejects and reject exactly when $M_{11}$ accepts. The most straightforward way to do so is to simply swap the accept and reject states.² A DFA accepting binary strings that do not contain the substring 11

This time, I drew it myself by hand, because it’s an example not directly from Jeff’s notes, and I’m in a hurry.

More generally, given a machine $M = (Q, \delta, s, A)$ , there is a machine $\overline{M} = (Q, \delta, s, \overline{A})$ , with $\overline{A} = Q \setminus A$ such that $L(\overline{M}) = \overline{(L(M))}$ . Not bad, so far.

To describe our next construction, we’ll need a second machine. For example, if we take $M_{11}$ and swap all the 0s and 1s in the transitions, we get a machine $M_{00}$ whose language is the strings containing 00 as a substring. A DFA accepting binary strings that contain the substring 00

Now, suppose we like 11 after all. But we also like 00. Is there a machine to accept strings with both? In other words, can we easily make a machine whose language is $L(M_{00}) \cap L(M_{11})$ ? Intuitively, we’d like to run both $M_{00}$ and $M_{11}$ in parallel, updating both of their states each time we read a symbol from an input string. We’d accept if and only if both machines reach an accept state.

It turns out there’s another DFA that precisely models this intuition using the product construction of $M_{11}$ and $M_{00}$ as first proposed by Moore in 1956.

The states of the new DFA are ordered pairs $(p, q)$ where $p$ is a state of $M_{00}$ and $q$ is a state of $M_{11}$ .
It starts in state $(s, s')$ where $s$ is the start state of $M_{00}$ and $s'$ is the start state of $M_{11}$ .
We include transitions $(p, q) \xrightarrow{a} (p', q')$ (i.e., $\delta((p, q) a) = (p', q')$ ) if and only if $M_{00}$ contains transition $p \xrightarrow{a} q$ and $M_{11}$ contains transition $p' \xrightarrow{a} q'$ .
We accept at a state $(p, q)$ if and only if $M_{00}$ has accepting state $p$ and $M_{11}$ has accepting state $q$ .

Intuitively, every time we read a character $a$ , we update the paired state based on what each machine would be doing. Arriving in one of our new machine’s accepting states means both machines would have reached their corresponding accepting state using the same input string.

More formally, let’s say we have two machines $M_1 = (Q_1, \delta_1, s_1, A_1)$ and $M_2 = (Q_2, \delta_2, s_2, A_2)$ . A product or product construction of $M_1$ and $M_2$ is some machine $M = (Q, \delta, s, A)$ such that:

$Q = Q_1 \times Q_2 = \{(p, q) \mid p \in Q_1 \text{ and } q \in Q_2\}$ ,
$\delta((p, q), a) = (\delta_1(p, a), \delta_2(q, a))$ , and
$s = (s_1, s_2)$ .

With this construction, we get the following lemma which states that reading a string $w$ transitions the pair of states $(p, q)$ the same as if you fed $w$ to $M_1$ and $M_2$ individually. In other words, the new machine $M$ simulates running $M_1$ and $M_2$ in parallel on the same input.

Lemma: $\delta^*((p, q), w) = (\delta_1^*(p, w), \delta_2^*(q, w))$ for any string $w$ .

The proof is a straight forward but somewhat tedious use of induction over $w$ . You might want to try it for yourself before looking in Erickson for the details.

It’s important to understand that I haven’t defined the accept states $A$ for machine $M$ . The reason is because different choices of $A$ give us different combinations of the languages of $M_1$ and $M_2$ . If you do a product construction on the homework or exams, you must tell us what the accept states of the resulting machine are. We will not try to guess.

Suppose we want $L(M) = L(M_1) \cap L(M_2)$ . We want to model both machines accepting, so let’s set $A = \{(p, q) \mid p \in A_1 \textbf{ and } q \in A_2\}$ .
To get $L(M) = L(M_1) \cup L(M_2)$ , set $A = \{(p, q) \mid p \in A_1 \textbf{ or } q \in A_2\}$ .
To get $L(M) = L(M_1) \setminus L(M_2)$ , set $A = \{(p, q) \mid p \in A_1 \textbf{ and } q \mathbf{\notin} A_2\}$ .
To get $L(M) = L(M_1) \oplus L(M_2)$ , set $A = \{(p, q) \mid p \in A_1 \textbf{ xor } q \in A_2\}$ .

“Automatic” languages and Kleene’s theorem

From the above product construction, we see that we can combine languages of/accepted by DFAs to make other languages of/accepted by DFAs. Let’s (just for the next few paragraphs) call a language “automatic” if it is accepted by at least one DFA. The following theorem states the automatic languages are closed under simple boolean operations.

Theorem: Let $L_1$ and $L_2$ be automatic languages over the same alphabet. Then, the following languages are also automatic:

$\overline{L_1} = \Sigma^* \setminus L_1$
$L_1 \cup L_2$
$L_1 \cap L_2$
$L_1 \setminus L_2$
$L_1 \oplus L_2$

But those of you who came into this class familiar with DFAs and regular languages may be confused right now by the use of the phrase automatic language. In fact, a quick search in my current search engine doesn’t provide anything relevant to DFAs. The reason is because we just made up a new term for when there’s a perfectly good one we’ve already seen. We just don’t know that the old term applies yet.

Theorem (Kleene): A language $L$ is automatic if and only if it is regular.

In other words, for any regular expression $R$ , there is a DFA $M$ such that $L(M) = L(R)$ , and for any DFA $M$ , there is a regular expression $R$ such that $L(R) = L(M)$ .

We’ll have to wait until next week to (mostly) prove this theorem. Unfortunately/fortunately, doing so requires learning a powerful new tool we haven’t seen yet, a third model of computation called nondeterministic finite-state automata (NFAs) that also accept exactly the regular languages. Strangely, though, they feel more powerful than both DFAs and regular expressions in practical use, and we’re going to take advantage of that power.

Before getting into NFAs, though, we’re going to see what else DFAs have to teach us about regular languages and vice versa. First, all those closure properties for automatic languages apply to regular languages as well.

Corollary: Let $L_1$ and $L_2$ be regular languages over the same alphabet. Then, the following languages are also regular:

$\overline{L_1} = \Sigma^* \setminus L_1$
$L_1 \cup L_2$
$L_1 \cap L_2$
$L_1 \setminus L_2$
$L_1 \oplus L_2$

In the other direction, the additional closure properties for regular languages (as given in their definition) apply to the automatic languages, because the automatic languages are the regular languages. So, if $L_1$ and $L_2$ are both accepted by DFAs, there is a DFA that accepts $L_1 \bullet L_2$ and another DFA that accepts $L_1^*$ .

Also, we now have a few ways to show a particular language $L$ is regular:

Build a regular expression that represents $L$ .
Build a DFA that accepts $L$ .
Build either of those things from simpler regular expressions or DFAs, i.e., show simpler languages are regular and apply the above closure properties.

Finally, we can use Kleene’s theorem to argue not only what languages are regular, because we can construct a DFA for them, but also what languages are not regular, because we can not construct a DFA for them.