Automaty liniowe ograniczone
Automat z ograniczeniami liniowymi to wielościeżkowa niedeterministyczna maszyna Turinga z taśmą o określonej ograniczonej długości.
Length = function (Length of the initial input string, constant c)
Tutaj,
Memory information ≤ c × Input information
Obliczenia są ograniczone do stałego obszaru ograniczonego. Alfabet wejściowy zawiera dwa specjalne symbole, które służą jako lewe znaczniki końcowe i prawe znaczniki końcowe, co oznacza, że przejścia nie przesuwają się na lewo od lewego znacznika końcowego ani na prawo od prawego znacznika końcowego taśmy.
Automat z ograniczeniami liniowymi można zdefiniować jako 8-krotkę (Q, X, ∑, q 0 , ML, MR, δ, F), gdzie -
Q jest skończonym zbiorem stanów
X to alfabet taśmy
∑ jest alfabetem wejściowym
q0 jest stanem początkowym
ML to lewy znacznik końca
MRjest prawym końcowym znacznikiem, gdzie M R ≠ M L
δ jest funkcją przejścia, która odwzorowuje każdą parę (stan, symbol taśmy) na (stan, symbol taśmy, Stała 'c'), gdzie c może wynosić 0 lub +1 lub -1
F jest zbiorem stanów końcowych
Deterministyczny liniowo ograniczony automat jest zawsze context-sensitive a automat liniowo ograniczony z pustym językiem to undecidable..