# 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. Nov 20, 2019 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? Nov 20, 2019 at 4:25
• Nov 20, 2019 at 7:32
• How to prove it? About the same as for L itself. Nov 20, 2019 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)$? Nov 20, 2019 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. Nov 21, 2019 at 3:07

The language $$\textrm{prefix}(L) = \{0^n1^m:n \geq m\}$$. It's not regular.

From the pumping lemma:

Let $$L$$ be a regular language. Then there exists an integer $$p \geq 1$$ depending only on $$L$$, such that every string $$w \in L$$, of length at least $$|w| \geq p$$ ( $$p$$ is called the "pumping length") can be written as $$w = x \cdot y \cdot z$$(i.e., $$w$$ can be divided into three substrings), satisfying the following conditions:

• $$|y| \geq 1$$
• $$|xy| \leq p$$
• $$\forall n \geq 0 : xy^nz \in L$$

Let's create a word $$0^p1^p$$. Since $$|xy| \leq p$$, than the substring of $$w$$, that we will be pumping has to be wholly within first $$p$$ characters, meaning that it can consist only of $$0$$-es.

However, $$w = xy^0z \notin L$$, since it would contain less $$0$$-es than $$1$$-s