1

Is this language regular? I cannot find a solution for it and I have mixed feelings about it, by the way I am only doing these the last 2 weeks.

enter image description here

Naoimi
  • 35
  • 5

1 Answers1

1

This language is not regular and we can prove as much using the pumping lemma for regular languages. Suppose the language were regular. Then the string 0^p 1^p in the language can be written as uvx where |uv| <= p, |v| > 0 and for all natural numbers k, u(v^k)x is in the language. However, our uv must consist only of leading 0, and since we can pump down by choosing k = 0, we violate |w| <= n. This is a contradiction so the language can't be regular.

Patrick87
  • 27,682
  • 3
  • 38
  • 73