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

Определение:

Линейно ограниченный автомат (lba) — недетерминированная одноленточная машина Тьюринга, которая никогда не покидает те ячейки, на которых размещен ее ввод.

Более формально:

Определение:

Линейно ограниченный автомат (lba) — формальная система [math]M = (Q, \Sigma, \Gamma, \delta, q_0, F)[/math], в которой [math]Q[/math] — множество состояний. [math]q_0 \in Q[/math] — начальное состояние. [math]F \subset Q[/math] — множество конечных состояний. [math]\Gamma[/math] — алфавит допустимых символов ленты. [math]\Sigma \subset \Gamma[/math] — алфавит входных символов, который содержит два особых символа: [math]\#[/math] и [math]\$[/math] — левый и правый маркеры, находящиеся с самого начала на концах входной цепочки для того, чтобы предотвращать выход головки ленты за пределы участка, на котором размещается входная цепочка (считается, что маркеры могут использоваться только в этой роли: на место маркера нельзя записать какой-нибудь другой символ ленты, и никакой символ ленты не может быть заменен каким-нибудь маркером). [math]\delta[/math] — отображение типа [math]Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, R\}}[/math].