Peter Linz Edition 4 Example 10.5 (Page No. 272)

Question

Find a linear bounded automata that accepts the language

1. L={a^(n!) : n>=0}

2. L ={a^n : n is perfect square}

Please explain.

Comments

Thanks for the response

@Surajit I am unable to come up with any algorithm. Could u give some hint?

---

for the first one....I think it will be more easy if we use multiple tapes.Start with value one and keep on multiplying with the 'n' value in n!. Store that in a place then decrement n and multiply again and keep on repeating the step.See below for detailed steps.Its bit tedious to form the entire transformations.

https://math.stackexchange.com/questions/1153376/construct-a-turing-machine-for-factorialunary

---

Thanks a lot. I am now clear about both the problems. It becomes easy by using multiple tapes.

The second problem can be solved using the fact that a perfect square number can be obtained by adding odd numbers. For e.g. 4=1+3; 9=1+3+5 and so on. Two tapes can be used to generate perfect square number and that number can be matched with the length of string.