2,113 views
5 votes
5 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?

1 Answer

9 votes
9 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.

edited by

Related questions

0 votes
0 votes
0 answers
1
1 votes
1 votes
1 answer
2
1 votes
1 votes
1 answer
3
2 votes
2 votes
1 answer
4
One asked Jul 22, 2016
1,168 views
Let L1=0*1* ,L2=1*0* ,L3=(0+1)* and L4=0*1*0*. Then Find The Number Of Strings In The Following Language L.L= (L1 ∩ L2) - (L3 ∩ L4)