Изменения
Новая страница: «{{Определение |definition = '''Линейно ограниченный автомат''' ''(lba)'' — недетерминированная одно...»
{{Определение
|definition = '''Линейно ограниченный автомат''' ''(lba)'' — недетерминированная одноленточная машина Тьюринга, которая никогда не покидает те ячейки, на которых размещен ее ввод.}}
Более формально:
{{Определение
|definition = '''Линейно ограниченный автомат''' ''(lba)'' — формальная система <tex>M = (Q, \Sigma, \Gamma, \delta, q_0, F)</tex>, в которой
*<tex>Q</tex> — множество состояний.
*<tex>q_0 \in Q</tex> — начальное состояние.
*<tex>F \subset Q</tex> — множество конечных состояний.
*<tex>\Gamma</tex> — алфавит допустимых символов ленты.
*<tex>\Sigma \subset \Gamma</tex> — алфавит входных символов, который содержит два особых символа: <tex>\#</tex> и <tex>\$</tex> — левый и правый маркеры, находящиеся с самого начала на концах входной цепочки для того, чтобы предотвращать выход головки ленты за пределы участка, на котором размещается входная цепочка (считается, что маркеры могут использоваться только в этой роли: на место маркера нельзя записать какой-нибудь другой символ ленты, и никакой символ ленты не может быть заменен каким-нибудь маркером).
*<tex>\delta</tex> — отображение типа <tex>Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, R\}}</tex>.}}
|definition = '''Линейно ограниченный автомат''' ''(lba)'' — недетерминированная одноленточная машина Тьюринга, которая никогда не покидает те ячейки, на которых размещен ее ввод.}}
Более формально:
{{Определение
|definition = '''Линейно ограниченный автомат''' ''(lba)'' — формальная система <tex>M = (Q, \Sigma, \Gamma, \delta, q_0, F)</tex>, в которой
*<tex>Q</tex> — множество состояний.
*<tex>q_0 \in Q</tex> — начальное состояние.
*<tex>F \subset Q</tex> — множество конечных состояний.
*<tex>\Gamma</tex> — алфавит допустимых символов ленты.
*<tex>\Sigma \subset \Gamma</tex> — алфавит входных символов, который содержит два особых символа: <tex>\#</tex> и <tex>\$</tex> — левый и правый маркеры, находящиеся с самого начала на концах входной цепочки для того, чтобы предотвращать выход головки ленты за пределы участка, на котором размещается входная цепочка (считается, что маркеры могут использоваться только в этой роли: на место маркера нельзя записать какой-нибудь другой символ ленты, и никакой символ ленты не может быть заменен каким-нибудь маркером).
*<tex>\delta</tex> — отображение типа <tex>Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, R\}}</tex>.}}
