The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
26 views
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).
in Theory of Computation by Junior (545 points)
edited by | 26 views
0

@abhishekmehta4u can you please see this.

Please log in or register to answer this question.

Related questions

0 votes
0 answers
2
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,807 questions
54,729 answers
189,326 comments
79,940 users