3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ What is the quantification on $y$ and $z$? For all $y,z$? Exist $y,z$? The question is ill-defined without it. $\endgroup$
    – Shaull
    Commented Apr 11, 2015 at 11:23
  • $\begingroup$ Sorry, I forgot tell about it. Yes, Exista $y,z$ $\endgroup$
    – user220688
    Commented Apr 11, 2015 at 11:53
  • 2
    $\begingroup$ Crosspost with math.stackexchange $\endgroup$
    – J.-E. Pin
    Commented Apr 11, 2015 at 12:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – babou
    Commented Apr 11, 2015 at 14:06

2 Answers 2

Reset to default
1
$\begingroup$

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\}$

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – babou
    Commented Apr 11, 2015 at 15:12
  • $\begingroup$ Thanks, I edited post. When it comes to problem with single accept state hypothesis. What do you mean ? $\endgroup$
    – user220688
    Commented Apr 11, 2015 at 15:28
  • $\begingroup$ 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. $\endgroup$
    – babou
    Commented Apr 11, 2015 at 15:45
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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