Lineárně ohraničené automaty: Definice
Definice: Lineárně ohraničený automat (LOA) je TS, který nemůže žádným pravidlem prodloužit pásku.
Myšlenka: Se vstupním řetězcem w je páska omezena na pouze |w| políček
32/45
Ilustrace:
w
s
x
y
f
D
D
Stejná délka