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$ – Renato Sanhueza May 24 '16 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$ – David Richerby May 24 '16 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$ – Rick Decker May 24 '16 at 20:46

Browse other questions tagged or ask your own question.