2
$\begingroup$

Let $\Sigma=\{0,1\}$ and $L$ be a regular language. Prove that $$Z(L) = \{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$$ is a regular language.

I tried to build a NFA based on the DFA that accepts $L$ but failed to do so. I don't know how to ensure the $\, ww \,$ part. Please advise.

Improve this question
$\endgroup$
3
  • $\begingroup$ Related: the language $\{ w \mid ww\in L\}$ is sometimes called the root of $L$. The root of a regular language is again regular. See If L is a regular language then so is √L={w:ww∈L} $\endgroup$
    – Hendrik Jan
    May 21 at 12:35
  • $\begingroup$ @HendrikJan I don't see how this helps (though it looks close). Any hint? $\endgroup$
    – Dennis
    May 21 at 12:41
  • $\begingroup$ My aim was to indicate that the $ww$ suffixes can be recognized using a finite state construction. Nathaniel made that explicit in his answer. In the $\sqrt L$ construction you keep $w$, in Nathaniels construction it is omitted from the string. $\endgroup$
    – Hendrik Jan
    May 21 at 18:41
2
$\begingroup$

Let $A = (Q, \delta, q_0, F)$ a DFA that accepts $L$. For $q, q' \in Q$, define:

  • $L_{q,q'} = \{u\in \Sigma^*, \delta^*(q, u) = q'\}$;
  • $L_{q',F} = \{u\in \Sigma^*, \delta^*(q', u) \in F\}$.

It is quite easy (can you prove it?) to see that those languages are regular.

Now the language $\{x\in \Sigma^*\mid \exists w\in\Sigma^*, xww\in L\}$ can be written as: $$\bigcup\limits_{q\in Q}L_{q_0,q}\cdot M(q)$$ Where $M(q) = \left\{\begin{array}{rl}\emptyset&\text{if }\bigcup\limits_{q'\in Q}L_{q,q'}\cap L_{q',F}=\emptyset\\\{\varepsilon\}&\text{otherwise}\end{array}\right.$

$M(q)$ is regular since it is either $\emptyset$ or $\{\varepsilon\}$, so that means that $Z(L)$ is regular.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you @Nathaniel, can you please explain the intuition behind $M(q)$? I'm trying to understand what it means. I can't see why the original language can be expressed in that way. $\endgroup$
    – Dennis
    May 21 at 12:45
  • $\begingroup$ We want to find the states $q$ such that there is a "double" path to a final state of $A$, that is states $q$ such that $\exists w\in \Sigma^*, \delta^*(q, ww)\in F$. Those $w$ are expressed by $\bigcup\limits_{q'\in Q}L_{q,q'}\cap L_{q',F}$, so we just need to now if this set is empty or not, and that is what is expressed by $M(q)$. $\endgroup$
    – Nathaniel
    May 21 at 12:50
  • $\begingroup$ Thank you. If this set is empty, shouldn't we accept only $x \in L$? In this case the union would accept any path from $q_0$ to $q$, wouldn't it? $\endgroup$
    – Dennis
    May 21 at 12:56
  • $\begingroup$ If $M(q) = \emptyset$, that means that $q$ is not a good state to end with when reading $x$. In this case, $L_{q_0,q}\cdot M(q) = \emptyset$ (because the concatenation with the empty set is the empty set), so those paths are not considered. $\endgroup$
    – Nathaniel
    May 21 at 12:58
  • $\begingroup$ Oh, I didn't know that the concatenation with the empty set if the empty set. Now it's clear, thank you! $\endgroup$
    – Dennis
    May 21 at 13:00
2
$\begingroup$

The operator $Z(L) = \{ x \mid xww\in L \text{ for some } w\}$ takes strings from the original language $L$ but keeps only prefixes $x$ that are obtained by chopping a suffix of the form $ww$.

This is a special application of the right quotient operation: $L/K = \{ x \mid xy\in L \text{ for some } y\in K\}$.

It is known that the family of regular languages is closed under right quotient of arbitrary languages, see Show L1 /L2 is regular. For your problem take $K = \{ww\mid w\in \Sigma^*\}$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, that's a neat solution :) $\endgroup$
    – Dennis
    May 22 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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