CODEWITHSUNDEEP
regular-languagecomputation-theory
Chen
Chen

Reputation: 309

For regular language a*b*, is there a superset of it which is non-regular?

Language A = a*b* is absolutely a regular language. But I am wondering if there is a superset of it is non-regular language? And the superset must use the same alphabet {a,b}

Upvotes: 1

Views: 1430

Answers (1)

biziclop
biziclop

Reputation: 49754

Yes, there is. Take B=bnabn (where n>0), that is the language of palindromes that start with b and contain a single a in the middle. This language is non-regular because the pumping lemma doesn't apply to it. It is also completely disjoint with A because every word in B contains the ba substring, while none of the words in A do.

A union of A and B is therefore a non-regular superset of A.

It is also easy to prove that not all regular languages can be extended this way because for example the language of every possible word over a given alphabet is by definition regular. Since there is no way to formulate a non-trivial superset of this language over the same alphabet, all supersets of the "Kleene star" language over a given alphabet will also be regular.

More generally, any language A whose complement language (CA=Σ*\A) is finite won't have a non-regular superset, because CA and all its subsets are by definition regular (finite languages are always regular), and therefore the union of any of them with A is also regular (the union of two regular languages is regular).

Upvotes: 2

Related Questions