1
$\begingroup$

I know how to use the pumping lemma to do so, but I don't think that can be used for this language:

$$L = \{x \in \{0,1\}^* : \text{no prefix of $x$ has more $1$'s than $0$'s}\}. $$

What other method can I use to prove this?

$\endgroup$
  • $\begingroup$ The pumping lemma should be enough. Think about what the prefix condition tells you about the whole string. $\endgroup$ – David Richerby Oct 27 '13 at 19:48
  • $\begingroup$ can I use a pumping length p? or is that too general? If can use p you could just do (0^p-1)1 and pump 1 p times $\endgroup$ – user11006 Oct 27 '13 at 21:22
  • $\begingroup$ That looks like the right approach, yes. If the language was regular, there would be a pumping length. The pumping length is essentially the number of states of some automaton that accepts the language, so you can't choose it: that means you have to be general and just let it be $p$. $\endgroup$ – David Richerby Oct 28 '13 at 0:26
  • $\begingroup$ I suggest you have a look at our reference question: cs.stackexchange.com/questions/1031/…. $\endgroup$ – Yuval Filmus Oct 28 '13 at 5:03
1
$\begingroup$

Hint: use $0^n1^n$ for large enough $n$.

Another approach is to use the Myhill-Nerode criterion, say with the words $0^n$.

| cite | improve this answer | |
$\endgroup$

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