retagged by
1,125 views

2 Answers

Best answer
7 votes
7 votes

It is necessary to understand  the set of strings that are accepted by both the languages.

a^n b^n = {∈, ab,aabb, aaabbb, aaaabbbb, aaaaabbbbb,...........}

a*b*= {∈, a, b, aa, ab, aab, aabb, abbb, aabbbb,aaabbb,aaabb, aaaabbbb,........}

Clearly former one is the subset of later one.

So when union is done on the two languages, the resultant language is the later one i.e. a*b*, which is a regular language. Hence the union of the two is a regular language.

The empty language is a regular subset of any language at all.

More generally, every finite subset of any language is regular.

e.g Let L be the language {a^n|n is prime}={aa,aaa,aaaaa,aaaaaaa,…}.

Let R be the subset of L consisting just of {aa, aaaaa,aaaaaaaaaaa}.

Then L is not regular but R is.

selected by
3 votes
3 votes

a*b* U a^nb^n = a*b*. That's why it is regular.

No it does not imply that a subset of non regular language can be regular.

It implies that subset of regular language can be non regular !

In fact every non regular language is subset of regular Language Σ*  !

Related questions

4 votes
4 votes
2 answers
1