# Regular languages closed under prefix operation

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

• This is a very standard exercise. It was asked on Mathematics: math.stackexchange.com/questions/1656668/…, and probably elsewhere. Commented Mar 6, 2021 at 17:22
• Had no idea, thanks for helping me. Commented Mar 6, 2021 at 18:29

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