07 Combining Automata and Proving Non-Regularity

A Warm-Up: Recognizing Suffixes

Let’s get our hands dirty and jump straight into designing an automaton. We’ll start with a classic problem: recognizing words that end in a specific pattern.

Consider the language $L_1$ over the alphabet $\Sigma =\{a,b\}$:

$$L_1=\{w\in \{a,b{\}}^{\ast }\mid w\text{ ends with }aa\text{ or }ab\}$$

The core of the problem is that our automaton needs to remember the last one or two symbols it has seen. Since it has no variables, this memory must be encoded in its states.

The Design Strategy

The most crucial information is the suffix of length two. This suggests we’ll need states corresponding to the four possible two-letter suffixes: aa, ab, ba, and bb.

Let’s start with these core states.

• $q_{aa}$: The last two symbols seen were aa.
• $q_{ab}$: The last two symbols seen were ab.
• $q_{ba}$: The last two symbols seen were ba.
• $q_{bb}$: The last two symbols seen were bb.

Now, let’s think about the transitions. If we are in state $q_{aa}$ (meaning the word so far ends in aa) and we read a new symbol, say b, the new suffix of length two is ab. So, we should transition from $q_{aa}$ to $q_{ab}$. If we read an a, the new suffix is aa, so we loop back to $q_{aa}$.

Applying this logic to all four states gives us the core of our machine. But what about short words, of length 0 or 1? They don’t have a two-letter suffix. We need states to handle the beginning of the computation:

• $q_{\lambda }$: The start state, representing the empty word prefix.
• $q_a$: We have seen exactly one symbol, and it was a.
• $q_b$: We have seen exactly one symbol, and it was b.

Putting it all together, we get the following automaton. The accepting states are $q_{aa}$ and $q_{ab}$, since those are the desired endings.

Let’s trace an example word like aabababba to see it in action:

1. Start at $q_{\lambda }$. Read a $\to$ $q_a$.
2. In $q_a$. Read a $\to$ $q_{aa}$. (If the word stopped here, it would be accepted).
3. In $q_{aa}$. Read b $\to$ $q_{ab}$. (Still an accepting state if the word ended).
4. In $q_{ab}$. Read a $\to$ $q_{ba}$.
5. In $q_{ba}$. Read b $\to$ $q_{ab}$.
6. In $q_{ab}$. Read a $\to$ $q_{ba}$.
7. In $q_{ba}$. Read b $\to$ $q_{bb}$.
8. In $q_{bb}$. Read a $\to$ $q_{ba}$. The word ends, and we are in state $q_{ba}$, which is not accepting. The word is correctly rejected.

State Classes for the Suffix Automaton

We can formally describe what each state means by defining its class:

• For short prefixes:
  • $C(q_z)=\{z\}$ for $z\in \{\lambda ,a,b\}$.
• For the main states (words of length $\ge 2$):
  • $C(q_z)=\{w\in \{a,b{\}}^{\ast }\mid |w|\ge 2\text{ and }w\text{ ends with }z\}$ for $z\in \{aa,ab,ba,bb\}$.

Counting Modulo a Constant

Finite automata cannot count indefinitely, but they are perfect for counting modulo a fixed number. This is a powerful technique.

Consider the language $L_2$:

$$L_2=\{w\in \{a,b{\}}^{\ast }\mid (|w{|}_a+2\cdot |w{|}_b)(\mathrm{mod}4)=3\}$$

The expression $(|w{|}_a+2\cdot |w{|}_b)(\mathrm{mod}4)$ can only have four possible outcomes: 0, 1, 2, or 3. This suggests a beautiful design: one state for each possible remainder.

• $q_0$: The current sum modulo 4 is 0. (This is our start state, for the empty word).
• $q_1$: The current sum modulo 4 is 1.
• $q_2$: The current sum modulo 4 is 2.
• $q_3$: The current sum modulo 4 is 3. (This is our only accepting state).

Now, how do the transitions work?

• If we are in state $q_i$ and read an a, the total sum increases by 1. So we move from $q_i$ to $q_{(i+1)(\mathrm{mod}4)}$. This creates a cycle: $q_0\stackrel{a}{\to }{q}_1\stackrel{a}{\to }{q}_2\stackrel{a}{\to }{q}_3\stackrel{a}{\to }{q}_0$.
• If we are in state $q_i$ and read a b, the total sum increases by 2. So we move from $q_i$ to $q_{(i+2)(\mathrm{mod}4)}$. This creates two separate cycles: $q_0\stackrel{b}{\to }{q}_2\stackrel{b}{\to }{q}_0$ and $q_1\stackrel{b}{\to }{q}_3\stackrel{b}{\to }{q}_1$.

The resulting automaton is symmetric and elegant:

The class of each state $q_i$ is precisely the set of words for which the condition holds for the remainder $i$:

$$\forall i\in \{0,1,2,3\}:C(q_i)=\{w\in \{a,b{\}}^{\ast }\mid (|w{|}_a+2\cdot |w{|}_b)(\mathrm{mod}4)=i\}$$

What Finite Automata Can Do

Let’s summarize the capabilities we’ve uncovered. Finite automata can:

• Recognize any finite set of words.
• Count modulo a constant.
• Recognize patterns like prefixes, suffixes, and infixes.
• Combine a finite number of these conditions using boolean logic ($\wedge ,\vee ,\neg$).

This last point is key. If we have automata for two different languages, can we combine them to recognize their union, intersection, or difference? The answer is yes, and the technique is called simulation.

Simulations: The Product Construction

The core idea is to build a new, larger automaton that simulates two smaller automata, $A_1$ and $A_2$, simultaneously.

Lemma 3.3: Let $\Sigma$ be an alphabet and let $A_1=(Q_1,\Sigma ,{\delta }_1,q_{01},F_1)$ and $A_2=(Q_2,\Sigma ,{\delta }_2,q_{02},F_2)$ be two DFAs. For any set operation $\odot \in \{\cup ,\cap ,\setminus \}$, there exists a DFA $A$ such that:

$$L(A)=L(A_1)\odot L(A_2)$$

This proves that the class of regular languages is closed under union, intersection, and set difference.

The Proof Idea: A “Simulcast” Automaton

We construct a new automaton $A=(Q,\Sigma ,\delta ,q_0,F)$ that runs $A_1$ and $A_2$ in parallel.

• States: The states of our new automaton are pairs of states, one from each of the original automata. This is the Cartesian product of the state sets. $$Q=Q_1\times Q_2$$ A state in $A$ looks like $(p,q)$, where $p\in Q_1$ and $q\in Q_2$.
• Start State: The start state is the pair of the original start states. $$q_0=(q_{01},q_{02})$$
• Transition Function: To simulate both automata, a transition in $A$ on a symbol a simply applies the respective transition functions of $A_1$ and $A_2$ to each component of the state pair. $$\forall p\in Q_1,q\in Q_2,a\in \Sigma :\delta ((p,q),a)=({\delta }_1(p,a),{\delta }_2(q,a))$$
• Accepting States: This is where the set operation comes in. The set of accepting states $F$ is defined based on whether the components are in their respective accepting sets, $F_1$ and $F_2$.
  • For Union ($L(A_1)\cup L(A_2)$): We accept if either automaton accepts. $F=\{(p,q)\mid p\in F_1\vee q\in F_2\}$
  • For Intersection ($L(A_1)\cap L(A_2)$): We accept only if both automata accept. $F=\{(p,q)\mid p\in F_1\wedge q\in F_2\}$
  • For Set Difference ($L(A_1)\setminus L(A_2)$): We accept if the first accepts and the second does not. $F=\{(p,q)\mid p\in F_1\wedge q\notin F_2\}$

Example: A Modular Design

Let’s build an automaton for the language $L=\{w\in \{a,b{\}}^{\ast }\mid |w{|}_a\text{ is even OR }w\text{ contains the infix }bba\}$.

We can break this down into two simpler problems:

1. $L_1=\{w\in \{a,b{\}}^{\ast }\mid |w{|}_a\text{ is even}\}$
2. $L_2=\{w\in \{a,b{\}}^{\ast }\mid w\text{ contains the infix }bba\}$

We can easily design automata for each of these. Let’s call the states of the first automaton $q_0,q_1$ and the states of the second $p_0,p_1,p_2,p_3$.

Now, we construct the product automaton. The states will be pairs $(q_i,p_j)$, which we can arrange in a grid. The transitions are determined by combining the transitions of the two base automata.

The start state is $(q_0,p_0)$. Since the operation is OR (union), a state $(q_i,p_j)$ is accepting if its first component is accepting in $A_1$ (i.e., $q_i=q_0$) OR its second component is accepting in $A_2$ (i.e., $p_j=p_3$). This corresponds to the entire first row and the entire last column of our grid.

Small exercise:

Task: Build the product automata.

Proving Non-Existence

We’ve seen what finite automata can do. Now we turn to the more profound question: what can’t they do? We will show that there are languages that are not in the class ${\mathcal{L}}_{REG}$.

To prove that something doesn’t exist is fundamentally harder than proving it does. As the lecturer said, to prove white rabbits exist, I just need to show you one. To prove green rabbits don’t exist, showing you a lack of a green rabbit isn’t enough. We need a more powerful, indirect argument. We will assume the thing we want to disprove does exist, and then derive a logical contradiction.

The contradiction will always hinge on the one great weakness of a DFA: its finite memory.

The Core Limitation: Obliviousness

A DFA has no auxiliary memory. All it “knows” about the input it has processed so far is encoded in its current state. If two different input strings, $x$ and $y$, drive the automaton to the same state, the automaton becomes “oblivious” to the difference between them. From that point on, it must treat them identically.

This is the key insight, formalized in the following lemma.

Lemma 3.3: Let $A=(Q,\Sigma ,{\delta }_A,q_0,F)$ be a DFA. Let $x,y\in {\Sigma }^{\ast }$ be two different strings ($x\ne y$) that lead to the same state:

$${\hat{\delta }}_A(q_0,x)={\hat{\delta }}_A(q_0,y)=p\text{for some state }p\in Q$$

Then, for any suffix string $z\in {\Sigma }^{\ast }$, the strings $xz$ and $yz$ must also lead to the same final state. Consequently:

$$xz\in L(A)⟺yz\in L(A)$$

Proof

The proof is a direct consequence of the definition of $\hat{\delta }$.

1. We are given that after reading $x$ or $y$, the automaton is in state $p$.
2. From state $p$, reading the suffix $z$ will lead to some state $r={\hat{\delta }}_A(p,z)$.
3. Since the automaton is deterministic, the path from $p$ determined by $z$ is unique.
4. Therefore, the computation for $xz$ ends in state $r$, and the computation for $yz$ also ends in state $r$.
5. If $r\in F$, both strings are accepted. If $r\notin F$, both are rejected.

Transclude of Diagram-illustrating-Lemma-3.3,-from-lecture-slide

The First Non-Regular Language: $L=\{a^n{b}^n\mid n\in \mathbb{N}\}$

This is the canonical example of a non-regular language. It represents the problem of balanced parentheses or matching tags in a programming language. Intuitively, to check if a string is in $L$, an automaton would need to count the number of $a$‘s. But since $n$ can be arbitrarily large, this would require an infinite number of states (memories) to store the count. A finite automaton cannot do this. Let’s prove it formally.

Theorem: The language $L=\{a^n{b}^n\mid n\in \mathbb{N}\}$ is not regular.

Proof by Contradiction

1. Assumption: Assume $L$ is regular. By definition, there must exist a DFA $A=(Q,\{a,b\},{\delta }_A,q_0,F)$ such that $L(A)=L$. Let $|Q|$ be the finite number of states in this automaton.

2. Pigeonhole Principle: Consider the following set of $|Q|+1$ distinct words:

   $$\{a^1,a^2,a^3,\dots ,a^{|Q|+1}\}$$

   When the automaton $A$ processes these $|Q|+1$ words, each one ends in some state in $Q$. Since there are more words (pigeons) than states (pigeonholes), at least two of these words must end in the same state.

3. Finding the Collision: Therefore, there must exist two distinct integers $i,j\in \{1,\dots ,|Q|+1\}$ with $i\ne j$, such that:

   $${\hat{\delta }}_A(q_0,a^i)={\hat{\delta }}_A(q_0,a^j)$$

4. Applying the Lemma: We have found our two words, $x=a^i$ and $y=a^j$, that land in the same state. Now we apply Lemma 3.3. The lemma states that for any suffix $z$, the automaton must treat $a^{i}z$ and $a^{j}z$ identically.

5. Choosing the Killer Suffix: We can choose any $z$ we want to create a contradiction. Let’s choose a $z$ that completes one of the words to be in the language $L$. A clever choice is $z=b^i$.

   • Consider the word $a^{i}z=a^i{b}^i$. By the definition of $L$, this word is in the language. Therefore, our automaton $A$ must accept it: $a^i{b}^i\in L(A)$.
   • Now consider the word $a^{j}z=a^j{b}^i$. Since $i\ne j$, this word is not in the language $L$.
   • However, according to Lemma 3.3, since $a^i$ and $a^j$ lead to the same state, appending $b^i$ must also lead to the same final outcome. Because $a^i{b}^i$ is accepted, $a^j{b}^i$ must also be accepted by the automaton $A$.

6. The Contradiction: We have shown that the automaton $A$ accepts the word $a^j{b}^i$, but this word is not in the language $L$. This contradicts our initial assumption that $L(A)=L$.

7. Conclusion: The assumption that $L$ is regular must be false.

A Preview of the Pumping Lemma

This method of proof is powerful, but there is another, closely related technique called the Pumping Lemma. The core idea is similar, but instead of considering two different words, we consider one single, very long word.

If a word is longer than the number of states in the automaton, the path it takes through the state diagram must visit at least one state twice. This creates a loop.

This means we can decompose the word $w$ into three parts, $w=yxz$, where:

• $y$ is the part that leads up to the first visit to the repeated state.
• $x$ is the part that traverses the loop.
• $z$ is the part that follows the loop to the end.

The crucial insight is that we can traverse the loop ($x$) any number of times, zero, one, or many, and the resulting word must still be treated the same way by the automaton. We can “pump” the middle section:

$$w_k=y{x}^{k}z$$

If the original word $w$ was accepted, then all pumped versions $w_k$ must also be accepted. This gives us another powerful tool to prove that languages requiring unbounded counting, like $\{a^n{b}^n\}$, cannot be regular. We will formalize this next time.

Continue here: 08 Proving Non-Regularity