3
$\begingroup$

Suppose we have some regular language $L$, then can we say that $$L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $$ is also regular?

I have a 'feeling' that it is, but I can't sketch a proof for it.

$\endgroup$
0

1 Answer 1

10
$\begingroup$

Yes, the language is regular: Consider a DFA A such that $L(A)=L$ Now, assume that you know, somehow, that when given a word $w$, the run of $A$ will end up in state $q$.

All you need to check now is that there is a run of $A$ on some word of length $|w|$ that gets from $q$ to an accepting state. This can be done by using the product automaton $A\times A$, where the first component acts exactly like $A$, and the second acts like $A$, but starts from state $q$ and ignores the input - that is, for each letter it nondeterministically goes anywhere that $A$ can go. Then, a run is accepting if the first component ends up in $q$, and the second component ends in an accepting state.

Finally, you can drop the assumption by taking $|Q|$ copies of this construction, where each copy "guesses" in which state $A$ will end up in. You end up with a nondeterministic construction of size $|Q|^3$

$\endgroup$
2
  • $\begingroup$ Do you want me to move your answer (maybe in modified form) to the question this is a duplicate of? $\endgroup$
    – Raphael
    Sep 9, 2013 at 10:16
  • $\begingroup$ As you see fit. The duplicate already has its answers, so move mine only if you think it has any additional value. $\endgroup$
    – Shaull
    Sep 9, 2013 at 15:50

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