The Gateway to Computer Science Excellence

+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?

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

+4 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"?)

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"?)

+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**.

+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

–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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,047 comments

104,671 users