Skip to main content
Computer Science

Return to Answer

A few more examples
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91

Yes, non-regular languages are closed under complement as well.

Suppose the complement of L1 is a non-regular language. If L1 is regular, then "the complement of L1 is also a regular language", which is not true. Hence L1 cannot be regular.

More generally, suppose we have defined a collection of languages as myLanguages. Then

myLanguages are closed under complement $\Longleftrightarrow$ non-myLanguages are closed under complement

For example, we have

  • non-context-free languages are not closed under complement.
  • non-context-sensitive languages are closed under complement.
  • non-deterministic-context-free languages are closed under complement.

Yes, non-regular languages are closed under complement as well.

Suppose the complement of L1 is a non-regular language. If L1 is regular, then "the complement of L1 is also a regular language", which is not true. Hence L1 cannot be regular.

Yes, non-regular languages are closed under complement as well.

Suppose the complement of L1 is a non-regular language. If L1 is regular, then "the complement of L1 is also a regular language", which is not true. Hence L1 cannot be regular.

More generally, suppose we have defined a collection of languages as myLanguages. Then

myLanguages are closed under complement $\Longleftrightarrow$ non-myLanguages are closed under complement

For example, we have

  • non-context-free languages are not closed under complement.
  • non-context-sensitive languages are closed under complement.
  • non-deterministic-context-free languages are closed under complement.
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91

Yes, non-regular languages are closed under complement as well.

Suppose the complement of L1 is a non-regular language. If L1 is regular, then "the complement of L1 is also a regular language", which is not true. Hence L1 cannot be regular.