# Find a linear bounded automaton that accepts the language $L = \{ a^{n!} : n \geq 0 \}$

I need to construct linear bounded automaton for the language $$L = \{ a^{n!} : n \geq 0 \}$$. I know how LBA functions, however, I don't have a thought how it can check the n! that to in the power of a. I might want to hear a few suggestions, as I am experiencing difficulty in developing the specific LBA for it.

## 1 Answer

The LBA maintains a counter $$c$$, initialized by $$1$$, which is stored on a parallel track. It thinks of the rest of the tape as an integer $$m$$. It then repeatedly executes the following instructions: divide $$m$$ by $$c$$, and increment $$c$$. The algorithm terminates when one of the following happens: $$m = 1$$, in which case you can declare success; or $$m$$ is not divisible by $$c$$, in which case you can declare failure.

• The idea seems good, yet would you be able to give more knowledge by really assembling the LBA, as I don't have the foggiest idea how I may continue with this, I took reference in Peter Linz book yet missed to do so. – Ajinkya Taranekar Jan 8 at 15:18
• Think of it like a programming exercise. It's your exercise, you should spend the effort. Start with easier tasks, such as just implementing the division step. – Yuval Filmus Jan 8 at 15:19
• Alright Thank you, I will attempt the problem, could you give some learning resources, as I see I am able to grasp algorithm however I don't have a clue how to check if I made a right one. – Ajinkya Taranekar Jan 8 at 15:24
• Unfortunately I'm not aware of such resources. Perhaps you'll have to write a simulator yourself. – Yuval Filmus Jan 8 at 15:25
• Okay, thank you for your time. – Ajinkya Taranekar Jan 8 at 15:27