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

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.

computer-sciencetheoryfinite-automata


Solution 1:[1]

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

Hope this helps!

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1

Related Questions