1
$\begingroup$

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

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

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.

|cite|improve this answer|||||
$\endgroup$
  • $\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 Nov 20 '19 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$ – Ashwin Ganesan Nov 21 '19 at 3:07

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.