retagged by
2,969 views
2 votes
2 votes
The language (a+b)* is regular as there is a regular expression for it.But this language contains all possible strings. So it should imply that regular language is the super-set of all languages, but clearly it isn't!

Subsets like $a^{n}b^{n}$ are not regular. Can someone tell me what am I missing?
retagged by

5 Answers

Best answer
5 votes
5 votes
Let $D$ be a regular set. So, $D$ contains a set of strings which all can be accepted by a FA.

Now, $CFL \supset RL$.

This means set of all context-free languages (not set of strings, rather set of set of strings), is a super set of set of all regular languages. No need to prove this as every regular language is a CFL and there are CFLs which are not regular.

Individually there may or may not be any subset/superset relation between a regular language and a CFL. (The relation is between set of all regular languages (RL) and set of all context-free languages (CFL)). For example the regular set $\{\}$ is a subset of any CFL and the regular set $\Sigma^*$ is a super set of any CFL.

(Consider Indians (set of people born in India) as a subset of Asians. Now can we say an Indian - say "Mohan" a subset of an Asian "Lee"?)
selected by
3 votes
3 votes

Every subset of regular language is may or may not be Regular.

e.g:   a*b* is a Regular Language than $a^nb^n\subseteq a^*b^*; n\geq 0$ and its not Regular.
                                            (or)

Let take $a^mb^n$ than its subset 'aabb' string is not Regular(i.e $a^nb^n\subseteq a^mb^n$)


Similarly,

Every superset of Regular language is may or may not be regular.
e.g: If Empty language $\o$ is Regular than its superset $a^nb^n$ need not be  Regular,        where $n\geq 0$.

Therefore, according to the properties of regular languages, it is not closed under subset or superset.

edited by
1 votes
1 votes

DFA for (a+b)* is

Actually all regular language are CFL

But all CFL are not regular.

Because Regular language are subset of CFL

0 votes
0 votes

according to closure property regular language  is  not closed under  subset , superset , infinite union thats means subset of regular lanuage is may or may not regular. and  above question is the best example of it . which means  (a+b)* is regular and subset of (a+b)* is a^n b^n  which is not regular thats why we said regular language  is  not closed under  subset

Related questions

12 votes
12 votes
1 answer
3
Utk asked Dec 30, 2015
2,204 views
Consider following languages :L1 = { wxwy | x,w,y $\in$(a + b)+ } ,L2 = { xwyw | x,w,y $\in$(a + b)+ } ,L3 = { wxyw | x, y, w $\in$(a+b)+ } How can we say that L1 , L2 ar...
3 votes
3 votes
3 answers
4
Durgesh Singh asked Jul 25, 2017
5,472 views
We can say there are four types of strings in the language so the regex will be: a(a+b)+a + b(a+b)+b + a(a+b)+b + b(a+b)+a Please expleain where I am wrong