construction for proof of regularity of language

66 Views Asked by At

$L$ is regular. $L'=\{vw:v\in L, w\notin L\}$
Show that $L'$ is regular.
I ask you for controlling my construction:
$M=(Q,\Sigma,\delta, q_0,F)$ for $L$
$M'=(Q,\Sigma,\delta', (q_0, F') $
$Q'=(\{1\}\times Q) \cup (Q\times Q)$
Transitions
$\delta'((1,q),a)=(1,\delta(q,a))$
$\delta'((1,q),\epsilon)=(q,q_0)$
$\delta'((q_1,q_2),a\in\Sigma) = (q_1,\delta(q_2,a))$
$q_0'=(1,q_0)$
$F'=\{(q_1,q_2):q_1,q_2\in Q\wedge q_1\in F\wedge q_2\notin F\}$

1

There are 1 best solutions below

0
On BEST ANSWER

Your construction seems to be correct, but there is a much shorter proof. Since $L$ is regular, its complement $L^c$ is also regular. Now $L' = LL^c$ and since the product of two regular languages is regular, $L'$ is regular.