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?

  • The solution is indeed missing an initial state. – Yuval Filmus Dec 6 at 3:14
  • 1
    I'm not sure why we need four copies – it seems that three should be enough. Perhaps you also need an additional initial state to handle $\epsilon$. – Yuval Filmus Dec 6 at 3:15
  • 1
    You ask whether $(p,a,q) \in \delta$ is the same as $\delta(p,a) = q$. It isn't since for an NFA, $\delta(p,a)$ is a set of states rather than a single state. – Yuval Filmus Dec 6 at 3:16
  • In the third line of the transition relation, if you replace $\langle q,4\rangle$ with $\langle q,1\rangle$ in $(\langle p,3\rangle,a,\langle q,4\rangle)$, then you no longer need the fourth copy of $A$. Also, the initial state should be $\langle s_0,1\rangle$. – Uli Schlachter Dec 6 at 15:32
  • Thank you both (regarding this series of comments). :) – Alfred Kaminski Dec 7 at 23:33

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.

  • 1
    quote: "What does the fourth copy do? (No one actually wrote this question, ...)". Well,actually as Yuval commented, we all were wondering why four instead of three, it seems. – Hendrik Jan Dec 6 at 19:02
  • 1
    Thanks for your answer, but I have a follow-up question.: "A single copy is not enough." Doesn't what Hendrik Jan said show that a single copy of the DFA A is enough? – Alfred Kaminski Dec 7 at 23:34
  • 1
    @AlfredKaminski Yes and no. We can do with a single copy, but this needs a slightly different construction. The original idea (counting transitions modulo three) needs three copies. – Hendrik Jan Dec 8 at 1:37

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.

  • 0) Thanks for this. While I still care about understanding the three- and four-copy versions of the proof, this version feels more natural to me, and I wanted to know about it, especially if it was acceptable to do so. – Alfred Kaminski Dec 7 at 23:35
  • 1) When you say "now for every three consecutive transitions (p,a1,p1),(p1,a2,p2),(p2,a3,p3) in A, add the transition (p,a3,p3) to C," you mean to not also add, to C, the other transitions that A has, right? – Alfred Kaminski Dec 7 at 23:35
  • 2) "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)." I don't understand why it's in zero, one or two steps. Shouldn't it just be in every state p3 in C for which there are three consecutive transitions (p,a1,p1),(p1,a2,p2),(p2,a3,p3) in A? Are both of these statements somehow equivalent? – Alfred Kaminski Dec 7 at 23:35
  • 1) Yes, we start with an empty set of transitions, and add one new transition for each triple (keeping the last letter). The single transition represents a three letter path. 2) This seems a matter of interpretation. In the every third letter of an accepting computation is kept, but it is not said that the string should have an exact multiple of three letters. So we could have $3k+1$ or $3k+2$ letters where the last letters lead to a final state, but are forgotten. If you insist on multiples of three then your remark here is valid. – Hendrik Jan Dec 8 at 0:33
  • I) Can't one just say that the implication (p,a_1,p_1)∈δ,(p_1,a_2,p_2)∈δ, (p_2,a_3,p_3)∈δ⇒(p, a_3, p_3)∈ρ (this is a rho, not p) is also true, but in a vacuous way, for any extra amount of symbols being processed by A, meaning that an extra one or two (but not zero - I don't understand why you said zero, as well) symbols can be processed? Also, why do they have to be final states? It seems to me that for any given p_3 in A, the state p_3 in B would only need to be final if the corresponding state of A is as well, and I believe that the aforementioned implication has this handled as well. – Alfred Kaminski Dec 10 at 0:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.