Учебники

Линейно ограниченные автоматы

Линейный ограниченный автомат является многодорожечной недетерминированной машиной Тьюринга с лентой некоторой ограниченной конечной длины.

Длина = функция (длина исходной входной строки, константа с)

Вот,

Информация о памяти ≤ 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 – множество конечных состояний

Линейно ограниченные автоматы

Детерминированный линейный ограниченный автомат всегда чувствителен к контексту, а линейный ограниченный автомат с пустым языком неразрешим. ,