# show that language $L'$ is regular (given $L$ regular)

I am working on the following question:

$L$ is regular. Show that $L'=\{x|\exists y,z,\ xyz\in L\wedge |x|=|y|=|z|\}$ is also regular.

Firstly I show my idea. When you accept it I will try to formalize it. Every automata can has an equivalent automata with exactly one accept state. So let the automata for language $L$ have exactly one accept state $q_{accept}$.

And now we start in two places - in the normal start state $q_0$ and $q_{accept}$. From $q_{accept}$ we guess symbol. For one symbol we do two steps. From $q_0$ we go according to symbol - one step. A state is accepting is when two "starts" meet in one state.

Am I on the right track with this idea?

• What is the quantification on $y$ and $z$? For all $y,z$? Exist $y,z$? The question is ill-defined without it. – Shaull Apr 11 '15 at 11:23
• Sorry, I forgot tell about it. Yes, Exista $y,z$ – user220688 Apr 11 '15 at 11:53
• Crosspost with math.stackexchange – J.-E. Pin Apr 11 '15 at 12:21
• I would not say it is very clearly stated, but it seems to be the right direction ... provided you make it a bit more formal with states cross product. Try to write your own answer to the question. – babou Apr 11 '15 at 14:06

For language $L-$ $M=(Q,\Sigma,\delta, q_0, F)$
For language $L'-$ $M'=(Q',\Sigma,\delta, q_{start}, F')$
$Q'=(Q\times Q)\cup q_{start}$
Transistions
$\delta'(q_{start}, \epsilon)=\{(q,q_{acc})|q_{acc}\in F\}$
Transition from $(q_1, q_2)$ to $(q_3,q_4)$
$\delta'((q_1,q_2),a\in\Sigma) = \{(q_3,q_4)\}\text{ iff }\delta(q_1,a )=q_3 \text{ and } \delta(\delta(q_4,b),c)=q_2$ for some $b,c\in\Sigma$
Accepting states $F'=\{(q,q)|q\in Q\}$

• You goofed on the definition of $\delta'$ for the second component.: exchange $q_2$ and $q_4$ as you are going backward. Also,you are building a NFA. So your transition $\delta'$ is not a function but a relation., i.e. $\delta'((q_i,q_j),a)$ is a set of state pairs, not a single state pairs. Also, if you assume $M$ is deterministic, you may have a problem with your single accept state hypothesis. – babou Apr 11 '15 at 15:12
• Thanks, I edited post. When it comes to problem with single accept state hypothesis. What do you mean ? – user220688 Apr 11 '15 at 15:28
• I mean that a DFA may need more than 1 accept state. But, you may forget that: the simplest is to consider a NFA. In that case, you do not write $\delta(q_i,a)=q_j$ but $q_j\in\delta(q_i,a)$ because the transition function $\delta$ gives a set of states, not a single state. - - - another point is that a complete proof should actually show that this automaton answers the question. You can sketch that, but you should at least expolain a bit. – babou Apr 11 '15 at 15:45

start with $D$: a DFA for $L$. Construct an NFA $N$ for $L'$ in the following way:

1. $N$ has the same set of states $Q$ as $D$ with the same starting state.
2. for every $q\in Q$, let $i(q)$ be the length(s) of path(s) from the starting state to $q$ in $D$. Only paths of length at most $Q$ should be considered, then $i(q) \subseteq \{0,1,\ldots, |Q|-1\}$.

3. for any $l\in i(q)$: make $q$ accepting in $N$ if

3.1. $q$ is accepting in $D$, or

3.2. there is a path of length $2l$ from $q$ to an accepting state in $D$.

Now prove that this is what you need.