@Deepakk

there are two things to check any language

Countably infinite and uncountably infinite

and CFL is closed under countably infinite

chk here

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+4 votes

1)$L_{1}=\left \{ a^{2^{n}} \right \}$ where n is a positive integer.

Is it Reguler, CFL or CSL?

2)$L_{2}=\left \{ (a^{n})^{m}.b^{n}|n,m\geq 1 \right \}$ Is it Regular CFL or CSL?

Is it Reguler, CFL or CSL?

2)$L_{2}=\left \{ (a^{n})^{m}.b^{n}|n,m\geq 1 \right \}$ Is it Regular CFL or CSL?

+7 votes

$L_1 =\{a^{2^n}\}=\{aa,aaaa,aaaaaaaa....\}$

It's Exponential power.

So CSL.

$L_2$ = $\left \{ (a^{n})^{m}.b^{n}|n,m\geq 1 \right \} =\{a^+.b \ |n=1,m \geq1\} \cup \ \{a^n.b^n |n\geq1,m=1\}\cup \ \{a^{2n}.b^n |n\geq1,m=2\}\cup \ \{a^{3n}.b^n |n\geq1,m=3\}...$

According to me, It looks like CFL.

But it's not CFL. It's CSL.

CFL is not closed under infinite union.

Of course, it's not DCFL so DPDA can't be sufficient.

As Union is infinite and No. of states in NPDA is finite so NPDA is also not sufficient for it.

0

@Deepakk

there are two things to check any language

Countably infinite and uncountably infinite

and CFL is closed under countably infinite

chk here

0

Every link , it is saying about infiniteness of CFL, but not infinite union

https://www.cs.ox.ac.uk/people/paul.goldberg/FCS/slides2.pdf

0

CFL is closed under countably infinite

Did you mean "CFL is closed under **countably infinite union**"?

Because if you did, I could very easily disprove it.

Take this example.. We know that {$a^nb^nc^n | n \geq 1$} is Non-CFL CSL. And We also know that the language {$a^nb^nc^n | n \geq 1$} is Countably Infinite (Because we know that $\Sigma^*$ is itself countably infinite and every subset of Countably infinite is also Countably Infinite).

Now, Take each string of above language i.e. {$a^nb^nc^n | n \geq 1$} and make into languages of One string Only.

i.e. $\left \{ abc \right \} \cup \left \{ a^2b^2c^2 \right \} \cup \left \{ a^3b^3c^3 \right \} \cup ........$ Here, All the languages are CFL and There are Countably Infinite such languages.... But Union is Not CFL but CSL.

No Family of languages is closed under Infinite Union. Not even NOT RE family.

And Even Set of **Non-Regular CFL** if you consider... Is NOT closed under Infinite Union...It is not even closed under Union..Let alone Infinite union.

0

$\left \{ abc \right \} \cup \left \{ a^2b^2c^2 \right \} \cup \left \{ a^3b^3c^3 \right \} \cup .....\left \{ a^{n}b^{n}c^{n} \right \}$

where last one is $\left \{ a^{n}b^{n}c^{n} \right \}$ which is not CFL, it is CSL.

Moreover if CFL is closed, that doesnot not mean CSL is not closed

where last one is $\left \{ a^{n}b^{n}c^{n} \right \}$ which is not CFL, it is CSL.

Moreover if CFL is closed, that doesnot not mean CSL is not closed

0

@Deepakk

One more thing we only told Regular language is not closed under infinite union

But it is not told All language are not closed under infinite union

right?

One more thing we only told Regular language is not closed under infinite union

But it is not told All language are not closed under infinite union

right?

0

One more thing we only told Regular language is not closed under infinite union

But it is not told All language are not closed under infinite union

I said "All Language Families" i.e. All the Standard families like Set of Regular languages, Set of Context free languages, Set of context sensitive languages, Set of Recursive languages, Set of RE languages, Set of NOT RE languages.......All such sets...None of them is closed under Infinite Union.

Of course, Set of all languages i.e. $2^{\Sigma^*}$ will be closed under every operation which produces a language.

0

In pumping lemma, it is told

let $x\epsilon L$ with $|x|\geq p$ and $x=uvw$ where $|v|\geq 1$ and $m\geq 0$ and $uv^{m}w\epsilon L$

and it is also possible that length of u and v is atmost p. $|uv|\leq p$

-----------------------------------------------------------------------

In the above question

u= 0 length string , v=2 loops for a and b both and w= 0 length string

right?

here

$|uv|\leq p$ satisfying??

let $x\epsilon L$ with $|x|\geq p$ and $x=uvw$ where $|v|\geq 1$ and $m\geq 0$ and $uv^{m}w\epsilon L$

and it is also possible that length of u and v is atmost p. $|uv|\leq p$

-----------------------------------------------------------------------

In the above question

u= 0 length string , v=2 loops for a and b both and w= 0 length string

right?

here

$|uv|\leq p$ satisfying??

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 435
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,157 questions

43,608 answers

123,961 comments

42,860 users