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..