everyone.

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 . . .$$, define $$third(w) = a_3 a_6 a_9 ...$$.

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, 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!