toc book

Question

L={${a^{n^{2}}/n\geq 0}^{\ast }$}$^{\bigstar }$ find machine which accept

Comments

It will give a* which is regular .

And only one state is requird in dfa

---

Linear bounded automata

---

for n=0 it will be 1,what about n>=1 i mean L=$a^{1},a^{4},a^{9},a^{16},a^{25}.......$for(n=1,2,3) so it can't be accepted by DFA.

Answer 1

Since there is a * waiting outside, putting n = 1 gives the string $a^1$ which is $a$. Now use your friend *, the one who is waiting for you outside. So it will generate every string over the unary alphabet as the language generated will be $a^*$. So the machine accepting $a^*$ needs only 1 state.