Недетерминированный автомат - Большая Энциклопедия Нефти и Газа, статья, страница 1
Единственный способ удержать бегущую лошадь - сделать на нее ставку. Законы Мерфи (еще...)

Недетерминированный автомат

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]



Страницы:      1    2