Cтраница 1
Недетерминированные автоматы составляют последний важный класс. Интуитивно поведение такого автомата не определено однозначно: функция б может быть многозначна. Автомат принимает строку, если он окажется после считывания этой строки в одном из принимающих конечных состояний, независимо от того, какую из допустимых линий поведения он избрал. Известно, что любой контекстно-свободный язык может быть принят подходящим недетерминированным автоматом. [1]
По определению, недетерминированный автомат допускает заданную цепочку, если ( начав из начального состояния) после ее прочтения он способен оказаться в конечном состоянии. Модель программируется в виде бинарного отношения допускается, которое определяет принятие цепочки из данного состояния. [2]
Для любого конечного недетерминированного автомата можно построить эквивалентный ему конечный детерминированный автомат. [3]
Введем сейчас класс недетерминированных автоматов, которые допускают КС языки. Такие автоматы, называемые недетерминированными автоматами с магазинной памятью ( коротко МП автоматы), впервые появились как одно из средств автоматического перевода, а также для целей программирования. [4]
Так, элементами таблицы Ту конечного недетерминированного автомата могут быть произвольные подмножества множества S. Поведение конечного недетерминированного акцептора описывается регулярным выражением, как и в детерминированном случае. [5]
Теорема 5.8. Класс языков, воспринимаемых-конечными недетерминированными автоматами, совпадает с классом языков, воспринимаемых конечными детерминированными автоматами. [6]
В то же время большая общность - понятия недетерминированного автомата проявляется в том, что для представления некоторых событий с помощью недетерминированного автомата требуется меньшее число состояний. [7]
Доказательство следующего предложения демонстрирует большую гибкость, достигаемую благодаря применению недетерминированных автоматов. [8]
Как видно из доказательства, предлагаемый способ детерминизации может дать скачок от п состояний исходного недетерминированного автомата до 2 состояний результирующего детерминированного автомата. Рабином в 1967 г. Ответ был получен только в 1972 г. А. [9]
Абстрактное устройство подобного рода, могущее переходить из одного состояния в другое, называется конечным недетерминированным автоматом. [10]
Язык L является языком типа 2 тогда и только тогда, когда он представим в некотором недетерминированном автомате с магазинной памятью. [11]
Из этой теоремы и из того факта, что детерминированный ли-лейноограниченный автомат заведомо не может делать больше, чем недетерминированный автомат такого же типа, следует, что класс - линейноограниченных автоматов обоих этих типов заведомо уже, чем класс машин Тьюринга, в том смысле, что область представимости этих автоматов является точным включением области представимости машин Тьюринга. Следовательно, линейноограниченные автоматы являются промежуточными между конечными автоматами и машинами Тьюринга и притом адекватными определенному классу языков типа 1 - контекстным языкам. [12]
В то же время большая общность - понятия недетерминированного автомата проявляется в том, что для представления некоторых событий с помощью недетерминированного автомата требуется меньшее число состояний. [13]
Так как мага-зин может заполняться неограниченно долго, автомат с магазинной памятью может иметь неопределенно много вариантов конфигурации, чем отличается от конечного автомата. Недетерминированный автомат с магазинной памятью - это автомат, способный выбирать действия, исходя из условий. Языки, распознаваемые недетерминированными автоматами, - это обязательно бесконтекстные языки ( С. Но не каждый бесконтекстный язык распознается детерминированным магазинным автоматом. [14]
Введем сейчас класс недетерминированных автоматов, которые допускают КС языки. Такие автоматы, называемые недетерминированными автоматами с магазинной памятью ( коротко МП автоматы), впервые появились как одно из средств автоматического перевода, а также для целей программирования. [15]