$$
L = \{w \mid w \text{ does not contain } 000\}
$$
$$
L_2 = \{w \mid xwy \in L \text{ for some } x,y \in (0+1)^*\}
$$
Is $L_2$ regular? I am thinking regular language is closed under concatenation, but it seems that this language should be irregular. And I have no idea how to prove this, how do I apply pumping lemma or is there a counter example?
Asked
Active
Viewed 32 times
0
J.-E. Pin
- 40,163
Louis Kuang
- 293
2 Answers
3
Actually, you have $L = L_2$.
Let $w\in L$. Then $w\in L_2$, as $\varepsilon w \varepsilon \in L$.
Let $w\in L_2$. Then, let $x$ and $y$ be such that $xwy\in L$, i.e. $xwy$ does not contain $000$. But if $w$ contained $000$, then $xwy$ would too. Thus $w\in L$.
Kevin Quirin
- 1,395
-
Thanks anyway. Feel like the answer is right in front of my eyes but didn't see it. – Louis Kuang Dec 10 '15 at 10:47
2
$L_2$ is regular, because $L_2 = L_1$ (and $L_1$ is regular).
($L_2 \subseteq L_1$) If $w\in L_2$, then there are $x,y$ such that $xwy\in L_1$, so $xwy$ does not contain $000$. But then $w$ can't contain $000$, so $w\in L_1$.
($L_1 \subseteq L_2$) If $w\in L_1$, then does not contain $000$, so if $x=y=\varepsilon$, then $xwy = w \in L_1$, thus $w\in L_2$.
BrianO
- 16,579