1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – Ajinkya Taranekar Jan 8 at 15:18
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 8 at 15:19
  • $\begingroup$ 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. $\endgroup$ – Ajinkya Taranekar Jan 8 at 15:24
  • $\begingroup$ Unfortunately I'm not aware of such resources. Perhaps you'll have to write a simulator yourself. $\endgroup$ – Yuval Filmus Jan 8 at 15:25
  • $\begingroup$ Okay, thank you for your time. $\endgroup$ – Ajinkya Taranekar Jan 8 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.