Линейный ограниченный автомат является многодорожечной недетерминированной машиной Тьюринга с лентой некоторой ограниченной конечной длины.
Длина = функция (длина исходной входной строки, константа с)
Вот,
Информация о памяти ≤ c × Входная информация
Вычисление ограничено постоянной ограниченной областью. Входной алфавит содержит два специальных символа, которые служат в качестве маркеров левого конца и маркеров правого конца, что означает, что переходы не перемещаются ни влево от левого маркера конца, ни справа от правого маркера конца ленты.
Линейный ограниченный автомат может быть определен как 8-набор (Q, X, ∑, q 0 , ML, MR, δ, F), где —
-
Q — конечное множество состояний
-
X это ленточный алфавит
-
∑ является входным алфавитом
-
q 0 — начальное состояние
-
M L — маркер левого конца
-
M R — маркер правого конца, где M R ≠ M L
-
δ — это функция перехода, которая отображает каждую пару (состояние, символ ленты) в (состояние, символ ленты, константа ‘c’), где c может быть 0, +1 или -1
-
F — множество конечных состояний
Q — конечное множество состояний
X это ленточный алфавит
∑ является входным алфавитом
q 0 — начальное состояние
M L — маркер левого конца
M R — маркер правого конца, где M R ≠ M L
δ — это функция перехода, которая отображает каждую пару (состояние, символ ленты) в (состояние, символ ленты, константа ‘c’), где c может быть 0, +1 или -1
F — множество конечных состояний
Детерминированный линейный ограниченный автомат всегда чувствителен к контексту, а линейный ограниченный автомат с пустым языком неразрешим. ,