If L = {0^n 1^n | n > 0 } is L^c (complement of L) regular?

Question

My teacher stated that If L = {0^n 1^n | n > 0 } then the complement was regular. I don't think it is.

Is there anyone that can clear this up to me? I thought that if L was irregular then the complement also was irregular.

Answer 1

The complement of a nonregular language is never regular. If L is nonregular and L^c were regular, then (L^c)^c = L would be regular, a contradiction. Therefore, L^c in your example isn't regular. You can use the pumping lemma or Myhill-Nerode to prove this.

Hope this helps!