1
$\begingroup$

Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular? $$ \mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \} $$ (This problem is taken from Introduction to the Theory of Computation by Mike Sipser.)

$\endgroup$
2

1 Answer 1

1
$\begingroup$

(1) If the regular language is given by a finite state automaton $M$ the language of prefixes can be obtaines by extending the set of accepting states. Choose all states that lie on a path from initial state to one of the original accepting states.

The prefix operation is a special case of the operation quotient

$K/L = \{ x \mid xy\in L, \text{ for some } y\in K\}$

where we take $L$ to be the language $A^*$ of all strings. Surprisingly, the regular languages are closed under quotient by arbitrary languages. See are regular languages closed under division, and Closure against right quotient with a fixed language.

(2) If the regular language is given by a regular expression instead, then we can construct a new regular expression for the prefix language, directly using the inductive definition of regular expressions. See Regularity of “middles” of words from regular language.

(3) Also, there is a characterization in terms of Myhill-Nerode equivalence classes: a language is regular iff its number of equivalence classes is finite. In can be observed that $x \equiv_L y$ implies $x\equiv_{\text{pref }L} y$, so if $\equiv$ is of finite index, then so is $\equiv_{\text{pref }L}$. More on this see Myhill-Nerode and closure properties.

(As Yuval noted, the exercise is somewhat standard, but I would like to have some remarks here to close the issue. Feel free to add relevant links.)

$\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.