# Prove that $\texttt{prefix}(L)$ is regular

Given that $$L = \lbrace 0^n1^n : n \geq 0\rbrace$$ is a non-regular context-free language, prove that $$\texttt{prefix}(L)$$ is regular.

So far I have provided that the grammar to produce this language is: $$S \rightarrow 0S1 \thinspace | \thinspace \epsilon$$

Would you go about proving $$\texttt{prefix}(L)$$ is regular just like you would any language, proving that $$\Sigma^\star$$ = $$\texttt{prefix}(L)$$, or by induction on the length of the words in $$\texttt{prefix}(L)$$.

• Can you provide exact definition of $prefix(L)$? Because as per my interpretation that is not regular. – Vimal Patel Nov 20 '19 at 3:34
• $\texttt{prefix}(L)$ contains all prefix words in $L$, where a prefix of a word $w$ is a string $x$ such that $w = xy$ for some $y \in \Sigma^\star$. If it is the case for the language given that $\texttt{prefix}(L)$ is not regular, how would you go about proving that then? – Ryan Gomez Nov 20 '19 at 4:25
• – f9c69e9781fa194211448473495534 Nov 20 '19 at 7:32
• How to prove it? About the same as for L itself. – gnasher729 Nov 20 '19 at 7:35

It appears that $$prefix(L)$$ is non-regular.
Let $$L = \{0^n 1^n: n \ge 0\}$$. Then, $$prefix(L)$$, defined to be the set of all prefixes of strings in $$L$$, is the set of all strings that consist of zero or more $$0$$'s followed by at most the same number of $$1$$'s, i.e. $$prefix(L) = \{0^n 1^m: m \le n\}$$. Intuitively, the reason $$prefix(L)$$ is nonregular is that a machine that can check whether the number of $$1$$'s does not exceed the number of $$0$$'s must store a count of the number of $$0$$'s in the input seen so far, and so this language cannot be recognized by a machine with a finite number of states.
A formal proof that $$L' := prefix(L)$$ is nonregular is as follows. Consider the subset $$S = \{0^1, 0^2, \ldots, 0^p\}$$. Any DFA $$M$$ that recognizes $$L'$$ must take the inputs $$0^i$$ and $$0^j$$ $$(i < j)$$ to different states because $$0^i 1^j \notin L'$$ but $$0^j 1^j \in L'$$. Hence, the machine $$M$$ contains at least $$p$$ states. But $$p$$ was arbitrary. This proves there does not exist a DFA (with a finite number of states) recognizing $$L'$$.
This proof method requires us to find an infinite subset $$S$$ of pairwise distinguishable prefixes; see online about the Myhill-Nerode theorem.
• In your formal proof section, did you mean to say "$L'$ must take inputs $0^i$ and $0^j$ $(i < j)$" or did you mean to have "$L'$ must take inputs $0^i$ and $1^j$ $(i > j)$" since that is the definition for the language of $prefix(L)$? – Ryan Gomez Nov 20 '19 at 18:26
• @RyanGomez I meant $0^j$. These are just prefixes of strings in the language. Different prefixes in S must take the machine to different states because concatenating them with the same suffix $1^j$ leads in one case to acceptance and in the others case to non-acceptance of input. – Ashwin Ganesan Nov 21 '19 at 3:07