Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L

Question

I'm having trouble with proving the following, and my attempt and confusion is mentioned further below.

PROBLEM STATEMENT:

For a string $w = a_1 a_2 a_3 a_4 a_5 a_6 a_7 \dots$, define $third(w) = a_3 a_6 a_9 \dots$

Then, for a language $L$, define $third(L) = \{third(w) : w ∈ L\}$.

Show that if $L$ is regular, then $third(L)$ is also regular.

(Hint: Construct an ϵ-NFA from the DFA for $L$.)

TEACHER'S SOLUTION:

If $L$ is regular, it is accepted by some DFA, say $A = (Q,Σ,δ,s_0,F)$.

We will construct an ϵ-NFA $B$ such that $L(B) = third(L(A))$.

Here, you need four copies of $A$.

Formally, $B = (Q × \{1,2,3,4\}, Σ, ρ, F × \{2,3,4\})$,

where $ρ =$

${\{(⟨p, 1⟩, ϵ, ⟨q, 2⟩) : (p, a, q) ∈ δ}$, for some ${a ∈ Σ\}}$ ${∪}$

${\{(⟨p, 2⟩, ϵ, ⟨q, 3⟩) : (p, a, q) ∈ δ}$, for some ${a ∈ Σ\}}$ ${∪}$

${\{(⟨p, 3⟩, a, ⟨q, 4⟩) : (p, a, q) ∈ δ\}}$ ${∪}$

${\{(⟨p, 4⟩, ϵ, ⟨p, 1⟩) : p ∈ Q\}}$.

(Do not confuse ρ and p.)

WHAT I DO UNDERSTAND:

• I understand how Cartesian products work.

WHAT I MAY OR MAY NOT UNDERSTAND:

• Are the ${(p, a, q) ∈ δ}$ parts another way of saying ${δ(p,a) = q}$?

• I suspect that the gist of the proof is to modify the initial DFA of L with ϵ transitions, so that there are only non-ϵ transitions for every third symbol in any particular string of L, w, being analyzed. And, I suspect that that's the purpose of the stuff with the angle brackets.

• I suspect that the purpose of taking the Cartesian product of Q and ${\{1,2,3,4\}}$ and the purpose of taking the Cartesian product of F with ${\{2,3,4\}}$ is to have a state for each copy of A, where ${⟨p, 1⟩}$ represents the state p of the first copy of A (but is technically a state of B, not A).

• Should ${⟨s_0, 1⟩}$ be the start state of B, such that B's n-tuple is a 5-tuple, rather than a 4-tuple, and that that 5-tuple is ${B = (Q × \{1,2,3,4\}, Σ, ρ, ⟨s_0, 1⟩, F × \{2,3,4\})}$?

WHAT I DON'T UNDERSTAND:

• I don't understand what the transitions regarding the four copies (defined by B's transition relation, ρ) achieve exactly.

• Also, why does one need four copies of A? Can't one just add those additional transitions to a single copy of A?

Any input would be GREATLY appreciated!

Edit for adding new information (#1): Thanks to all of you for responses. :)

I have a comparatively small question: The transition relation, ρ, is also function in this case, because each state of the NFA B only has one transition to another state, per input, right?

Answer 1

And, I suspect that that's the purpose of the stuff with the angle brackets.

This is just a way to write elements of a cross product. For example: $$\lbrace 1,2\rbrace\times\lbrace 3,4\rbrace = \lbrace \langle 1,3\rangle,\langle 1,4\rangle,\langle 2,3\rangle,\langle 2,4\rangle \rbrace$$

I suspect that the gist of the proof is to modify the initial DFA of L with ϵ transitions, so that there are only non-ϵ transitions for every third symbol in any particular string of L, w, being analyzed.

Basically yes. The construction creates four copies of $A$. The first three copies behave just as $A$ behaved originally with a minor twist: If state $q$ is reached, instead afterwards the state $q$ in the next copy of $A$ is reached. (I will ignore the $\epsilon$ edge inscriptions for now. I come back to this later.)

Thus, initially we are in state $s_0$ of the first copy of $A$ (written as $\langle s_0,1\rangle$). Then, some letter $a$ is read. Let's say that in $A$ this would lead from $s_0$ to state $p$. Now, in the new automaton, this leads to state $p$ in the second copy of $A$, i.e. $\langle p,2\rangle$. Next, some letter $b$ is read. Let's say that this would lead from $p$ to $q$ in $A$. In the new product automaton, this leads from $\langle p,2\rangle$ to $\langle q,3\rangle$, i.e. it also moves on to the next copy of $A$.

The effect of this construction so far is that we not only "behave as $A$ would behave", but also that we know if the current letter position is exactly a multiple of three, or a multiple of three plus one, or a multiple of three plus two: All multiplies of three end up in the first copy of $A$, all multiplies of three plus one in the second copy, etc.

Now, let's go back to the $\epsilon$ edge inscriptions: So far, the automaton that was constructed just behaves as the original automaton $A$. But we want it to read just every third letter and skip the other two. We do this by replacing all edge inscriptions in the first two copies of $A$ with $\epsilon$. This will lead to a lot of non-determinism, because now all outgoing edges have the same label. The idea here is that when we have an input $a_3a_6a_9\dots$ the automaton "guesses" what the missing symbols $a_1, a_2, a_4, \dots$ could be. Each such guess is represented by taking an $\epsilon$-labelled edge. Only the third copy of $A$ is not modified, so this copy still actually reads $a_3a_6a_9\dots$

What does the fourth copy do?

(No one actually wrote this question, but I need it for structure ;-) )

The fourth copy in the construction from the question actually does not do anything. When the automaton is in state $\langle q,4\rangle$, the only option to continue is to go to state $\langle q,1\rangle$ (via an $\epsilon$-transition). Thus, the fourth copy can just be removed and instead we go directly to $\langle q,1\rangle$.

Can't one just add those additional transitions to a single copy of A?

First, there are no additional transitions (well, okay, the transitions from $\langle q,4\rangle$ to $\langle q,1\rangle$ can count as additional transitions). Instead, the construction keeps the original transitions but replaces some of the inscriptions with $\epsilon$.

Next, a single copy is not enough. The automaton still has to keep track on the position in the input. As an exercise, construct a DFA accepting $(abcd)^*$ and try out the construction on it.

Answer 2

The answer by Uli is excellent. It gives a detailed intuition behind the three-step construction. Still I was wondering whether it was possible to avoid the product construction.

We can "summarize" the three step construction as follows. Construct a new automaton $C$ with state set $Q$, the original state set of $A$; initial state $s_0$.

Now for every three consecutive transitions $(p,a_1,p_1), (p_1,a_2,p_2), (p_2,a_3,p_3)$ in $A$, add the transition $(p,a_3,p_3)$ to $C$. A state $q$ in $Q$ is final in $C$ if in $A$ from $q$ we can reach a final state in $F$ in zero, one or two steps (letters).

Now $C$ is a nondeterministic automaton (without epsilon-transitions) for the language $third(L)$. The above construction basically is the product construction with the standard construction for removing epsilon transitions merged into it. Sort of.