Log In
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?
in Theory of Computation
retagged by
is the lang is (a+b)^*a or (a+b)* ???

5 Answers

5 votes
Best answer
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

Sir but for this example CFL(anbn) is subset of RL(a*b*) ????

You can see once more.
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.

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


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 vote

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

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

–2 votes

A language is reg  if you can draw to fa for that language. since(a + b)* is a language containing all possible string over ∑=(a,b) and it is regular as we can build a finite automata,

Now coming to you query regular language is the super-set of all languages ?

For proving that we have to prove regular language should be able to do some thing which other language (CFL,REC etc) can,t do.

If you want your assumption is valid so it should be universally valid.
But simply speaking this is not true.Whatever regular language do CFL can also do or even CSL can do.
However CFL can do more which regular language can,t be able to do .String comparision where memory is unlimited.
Even there are higher class of language rather than reg language for that refer  Chomsky hierarchy.

edited by

Related questions

3 votes
4 answers
1 vote
1 answer
How could we construct a FA by finding out a pattern in this language if we take n is odd then we consider n=1 ,3 ,5 ,7 (here string is in AP so we would be able to find out FA) it is okay but it it not said that we should only take n =1 3 5 7 9 we could ... (this is also odd but now there is no pattern now how can we construct a FA ).... can someone explain this ? Assume same for if n is even.
asked May 11, 2016 in Theory of Computation shekhar chauhan 515 views
8 votes
1 answer
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 are regular but not L3 ? Please explain.
asked Dec 30, 2015 in Theory of Computation Utk 908 views
1 vote
3 answers
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
asked Jul 26, 2017 in Theory of Computation Durgesh Singh 1.6k views