The Gateway to Computer Science Excellence
+2 votes
1.1k views
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 by Active (1.6k points)
retagged by | 1.1k views
0
is the lang is (a+b)^*a or (a+b)* ???

5 Answers

+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"?)
by Veteran (430k points)
selected by
0

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

0
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.
                                            (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.

by (499 points)
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

by Veteran (118k points)
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

by Loyal (5.6k points)
–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.

by Boss (38.6k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
198,047 comments
104,671 users