$w = 0001000 \in L'$, but this $w$ is not in $L$?

32 Views Asked by At

Suppose if $L ⊆ Σ^∗$ is a regular language then the following language is also regular:

$$L' = \{w\mid ∃x, y ∈ Σ^∗ : w = xy ∧ yx ∈ L\}$$

For a simple example, let L be given by the regular expression $0^∗1$, so that $L$ is the set of words over $Σ=\{0,1\}$ consisting of a (possibly empty) string of zeroes followed by a single $1$. Then $L′$ is given by the regular expression $0^∗10^∗$ and is the set of words over $Σ$ that contain exactly one $1$.

So according to this example, $w = 0001000 \in L'$, but this $w$ is not in $L$. How is that possible?