@abhishekmehta4u can you please see this.

The Gateway to Computer Science Excellence

0 votes

How do a^n! and a^n^2 come under machine Linear Bound Automata?

I know that LBA is a reduced form of standard Turing Machine where tape is restricted to be used for inputs(for also input of infinite length)

But can anyone help me by designing a Turing Machine for a^n! or a^n^2 or giving any idea by following what kind of mechanism it accepts those languages? Somewhat I am understanding the concept but still I feel gaps in my understanding.

-------------Following lines I am writing to get verified whether I am understanding those right or not---------------------

Like I have understood completely that why a^n b^n c^n comes under LBA (as there is no restriction on using tape for input and one by one they can be compared by marking them)and not in FA(as we can’t hold count of a’s and b’s to compare) or not in PDA (As these machines are represented with using finite number of states and a stack which may help for comparing any two of them only i.e, either for a & b or b&c or a&c).

I know that LBA is a reduced form of standard Turing Machine where tape is restricted to be used for inputs(for also input of infinite length)

But can anyone help me by designing a Turing Machine for a^n! or a^n^2 or giving any idea by following what kind of mechanism it accepts those languages? Somewhat I am understanding the concept but still I feel gaps in my understanding.

-------------Following lines I am writing to get verified whether I am understanding those right or not---------------------

Like I have understood completely that why a^n b^n c^n comes under LBA (as there is no restriction on using tape for input and one by one they can be compared by marking them)and not in FA(as we can’t hold count of a’s and b’s to compare) or not in PDA (As these machines are represented with using finite number of states and a stack which may help for comparing any two of them only i.e, either for a & b or b&c or a&c).

52,345 questions

60,497 answers

201,860 comments

95,316 users