Return to 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?

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?

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!

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?

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!

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!