The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
276 views
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?
asked in Theory of Computation by Veteran (98.3k points) | 276 views

1 Answer

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

answered by Boss (13.3k points)
edited by
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

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

chk here

0

In the above question

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

right?

For which string you have made this division? 

0
2nd one


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

40,851 questions
47,514 answers
145,842 comments
62,274 users