0
$\begingroup$

I don't how to prove these.

(a) Show that the regular languages are closed under the following operations: $$ \mathbb{DROPOUT}(L) = \{ xz \mid xyz \in L,\enspace where \enspace x,z \in \Sigma^*, y \in \Sigma \}. $$ Namely, $\mathbb{DROPOUT}(L)$ is the language containing all strings that can be obtained by removing one symbol from a string in $L$.$\enspace$ For example, if $L = \{012\}$, then $\mathbb{DROPOUT}(L) = \{12, 02, 01\}$.

(b) $$ \mathbb{INIT}(L) = \{ w\in \Sigma^+ \mid w \enspace for\enspace some\enspace x, wx \in L\}. $$ For example, if $L = \{01, 110\}$, then $\mathbb{INIT}(L) = \{0, 01, 1, 11, 110\}$.$\enspace$ (HINT: Start with a DFA$\enspace A$ for $L$ and describe how to construct an FA for $\mathbb{INIT}(L)$ using $A$. We assume that $A$ has no sink states.)

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.