@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.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 450
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,106 questions

45,608 answers

132,245 comments

49,230 users