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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Jan 8, 2021 at 15:11
-
$\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$ Commented Jan 8, 2021 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$ Commented Jan 8, 2021 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$ Commented Jan 8, 2021 at 15:24
-
$\begingroup$ Unfortunately I'm not aware of such resources. Perhaps you'll have to write a simulator yourself. $\endgroup$ Commented Jan 8, 2021 at 15:25
-
$\begingroup$ Okay, thank you for your time. $\endgroup$ Commented Jan 8, 2021 at 15:27