HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Why is the complement of a language that is not regular also not regular?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whytheregularlanguagealsothatcomplementnot

Problem

In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not regular, he wrote that it follows from the fact that the second language was the complement of the first, which we had already proved was not regular.

I was wondering if anyone could explain why this is the case?

Solution

Because regular langauges are closed under complementation. That is, if $L$ is regular, so is $\overline{L}$. (Exercise: prove this.)

So, suppose that $L$ is non-regular. If its complement $\overline{L}$ were regular, then $\overline{\overline{L}}=L$ would also have to be regular.

Context

StackExchange Computer Science Q#49648, answer score: 12

Revisions (0)

No revisions yet.