linear bounded automaton

GPTKB entity

Statements (23)
Predicate Object
gptkbp:instanceOf theoretical computer science
gptkbp:abbreviation gptkb:LBA
gptkbp:accepts_language_class context-sensitive language
gptkbp:decidability emptiness problem is undecidable
membership problem is decidable
gptkbp:has_finite_control true
gptkbp:has_input_alphabet finite
gptkbp:has_tape_alphabet finite
https://www.w3.org/2000/01/rdf-schema#label linear bounded automaton
gptkbp:introduced gptkb:John_Myhill
gptkb:Peter_Landin
1960
gptkbp:relatedTo gptkb:Chomsky_hierarchy
context-sensitive grammar
gptkbp:tape_boundaries cannot move beyond input
gptkbp:tape_head_movement stationary
left or right
gptkbp:tape_size bounded by input length
gptkbp:type Technical Machine
gptkbp:used_in automata theory
formal language theory
gptkbp:bfsParent gptkb:Formal_language_theory
gptkbp:bfsLayer 7