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

  • $\begingroup$ Can you provide exact definition of $prefix(L)$? Because as per my interpretation that is not regular. $\endgroup$ Commented Nov 20, 2019 at 3:34
  • $\begingroup$ $\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? $\endgroup$
    – Ryan Gomez
    Commented Nov 20, 2019 at 4:25
  • 2
    $\begingroup$ Duplicate: math.stackexchange.com/questions/3442894/… $\endgroup$ Commented Nov 20, 2019 at 7:32
  • 1
    $\begingroup$ How to prove it? About the same as for L itself. $\endgroup$
    – gnasher729
    Commented Nov 20, 2019 at 7:35

2 Answers 2


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.

  • $\begingroup$ 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)$? $\endgroup$
    – Ryan Gomez
    Commented Nov 20, 2019 at 18:26
  • $\begingroup$ @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. $\endgroup$ Commented 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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