How can I prove that the language $L = \{0^nw1^n\mid n\geq0,w\in\{0,1\}\}$ is irregular? I've tried the pumping lemma but that seems not to work.

  • 1
    $\begingroup$ Show us what you've done so we can guide you. You can easily do this using the pumping lemma. And please use LateX for mathematical notation to make it more understandable for anyone that read this question. $\endgroup$ May 24, 2016 at 20:25
  • 2
    $\begingroup$ The pumping lemma should work just fine for this one. I don't want to sound unhelpful but "Try harder!" is probably the best advice I can give. $\endgroup$ May 24, 2016 at 20:25
  • $\begingroup$ I agree with @DavidRicherby. In this case, the most obvious first attempt to use the PL on this is to pump the string $0^p11^p$, where $p$ is the PL integer. It's easy to force this string to have too many 0's to be in $L$. Try it. $\endgroup$ May 24, 2016 at 20:46


Browse other questions tagged or ask your own question.