Линейный ограниченный автомат является многодорожечной недетерминированной машиной Тьюринга с лентой некоторой ограниченной конечной длины.
Длина = функция (длина исходной входной строки, константа с)
Вот,
Информация о памяти ≤ 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 – множество конечных состояний
Детерминированный линейный ограниченный автомат всегда чувствителен к контексту, а линейный ограниченный автомат с пустым языком неразрешим. ,