Find the language

Question

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?

Answer 1

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

Comments

chk here

---

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? 

---

2nd one