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.)


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.