1
$\begingroup$

Show that regularity is closed under prefixes. That is, if $L$ is regular, then so is

$$L_1 = \{x \mid \exists y: xy\in L\}$$

I am having a hard time trying to work this through. Can you please help me? Also, From what I understand, $L$ will be a subset of $L_1$ since a string can have a prefix as the entire string itself concatenated with the null string? Thanks!

$\endgroup$
  • $\begingroup$ It's just a corollary of the general theorem that, any regular language $L$, and any language $K$, the quotient $L/K$ is regular. Then take $K$ to be the language that includes all words. $\endgroup$ – MaudPieTheRocktorate Nov 16 '18 at 13:02
1
$\begingroup$

The idea is: An automaton recognizing $L$ can be transfered into one recognizing $L_1$ if we make all states accepting which lie on a path leading to an accepting state (we have to read $y$):

Let $A = (Q, \Sigma, \delta, q_0, F)$ a dfa recognizing $L$, define $F_1$ by $$ F_1 = \{q \in Q : \exists y \in \Sigma^*. \delta^*(q,y) \in F\} $$ Then $A_1 = (Q, \Sigma, \delta, q_0, F_1)$ recognizes $L_1$, as for $x \in \Sigma^*$ we have \begin{align*} x \in L(A_1) &\iff \delta^*(q_0, x) \in F_1\\ &\iff \exists y : \delta^*\bigl(\delta^*(q_0, x), y\bigr) \in F\\ &\iff \exists y: \delta^*(q_0, xy) \in F\\ &\iff \exists y : xy \in L\\ &\iff x \in L_1 \end{align*} Hence, $L_1$ is regular.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.