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

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

Cтраница 2


Важным обобщением рассматриваемого понятия является недетерминированный конечный автомат. Для каждого состояния и каждого входного символа недетерминированный автомат имеет нуль или более вариантов выбора следующего шага. Он может также выбирать, сдвигать ему входную головку при изменении состояния или нет.  [16]

Рекурсивная сеть переходов ( в дальнейшем просто рекурсивная сеть) - это ориентированный граф с помеченными состояниями и дугами, выделенным состоянием, которое называется начальным, и выделенным множеством состояний, которые называются заключительными. Она имеет по существу такой же вид, как и диаграмма переходов конечного недетерминированного автомата, с тем исключением, что символы при дугах могут быть как терминальными, так и именами состояний. Пустота магазина, обнаруженная при попытке поднять его содержимое в тот момент, когда обработан последний входной символ, есть критерий допустимости входной цепочки. Имена состояний, которые в этой модели могут встречаться на дугах, - это по существу имена конструкций, которые могут быть обнаружены как самостоятельные группы ( phrase) на входной ленте. Переход по дуге, помеченной именем состояния, может произойти, если конструкция указанного типа опознана как группа в соответствующем месте входной цепочки.  [17]

Аналогично можно доказать разрешимость структурной эквивалентности других объектов, связанных с порождением структур типа дерево, например, рекурсивных структур данных составных объектоВ ( ETOL - систем, моделирующих растущие биологические объекты, и ряд им подобных. При рассмотрении автоматов на деревьях свойство распознаваемости дерева формулируется в терминах параллельного пробега недетерминированного автомата по дереву.  [18]

Структуры данных вместе с сопоставлением, автоматическими возвратами и арифметикой представляют собой мощный инструмент программирования. В этой главе мы расширим навыки использования этого инструмента при помощи следующих учебных программных примеров: получение структурированной информации из базы данных, моделирование недетерминированного автомата, планирование маршрута поездки и решение задачи о расстановке восьми ферзей на шахматной доске. Мы увидим также, как в Прологе реализуется принцип абстракции данных.  [19]

20 Недетерминированная диаграмма переходов. [20]

Этот автомат недетерминированный, ибо одно из его состояний является таким узлом, из которого выходят две дуги, помеченные одним и тем же входным символом. Если автомат в состоянии q получает слово ( входной символ) этот, то он переходит в состояния 72 и 7з - Как указывалось в § 5.2.3, понятия конечного детерминированного автомата и конечного недетерминированного автомата эквивалентны в том смысле, что оба эти множества автоматов воспринимают регулярные языки. Однако недетерминированные автоматы значительно удобнее при описании языков.  [21]

22 Недетерминированная диаграмма переходов. [22]

Этот автомат недетерминированный, ибо одно из его состояний является таким узлом, из которого выходят две дуги, помеченные одним и тем же входным символом. Если автомат в состоянии q получает слово ( входной символ) этот, то он переходит в состояния 72 и 7з - Как указывалось в § 5.2.3, понятия конечного детерминированного автомата и конечного недетерминированного автомата эквивалентны в том смысле, что оба эти множества автоматов воспринимают регулярные языки. Однако недетерминированные автоматы значительно удобнее при описании языков.  [23]

Так как мага-зин может заполняться неограниченно долго, автомат с магазинной памятью может иметь неопределенно много вариантов конфигурации, чем отличается от конечного автомата. Недетерминированный автомат с магазинной памятью - это автомат, способный выбирать действия, исходя из условий. Языки, распознаваемые недетерминированными автоматами, - это обязательно бесконтекстные языки ( С. Но не каждый бесконтекстный язык распознается детерминированным магазинным автоматом.  [24]

Так как регулярные ( распознаваемые конечными автоматами) подмножества S замкнуты относительно, f /, 1 и у то отсюда следует, что Empty ( S) рекурсивно и в действительности примитивно рекурсивно. Легко построить конечный автомат для L ( a) и проверить, допускает ли автомат некоторое слово; для этого существуют хорошо известные процедуры. Априорный анализ такой процедуры, однако, показывает, что из детерминированных автоматов для у-выражений a, p получился бы недетерминированный автомат для а р или у ( а), и тогда пришлось бы применить подмножественную конструкцию Рабина - Скотта, чтобы получить автомат для - l ( tx p) или Пу ( а) - Поскольку под-множественная конструкция может экспоненциально увеличить число состояний в автомате, у-выражения, в которых k дополнений чередуются с у и конкатенациями, могут привести к автомату с th ( 2) состояниями.  [25]

Недетерминированные автоматы составляют последний важный класс. Интуитивно поведение такого автомата не определено однозначно: функция б может быть многозначна. Автомат принимает строку, если он окажется после считывания этой строки в одном из принимающих конечных состояний, независимо от того, какую из допустимых линий поведения он избрал. Известно, что любой контекстно-свободный язык может быть принят подходящим недетерминированным автоматом.  [26]

Большая часть понятий и задач, характерных для конечных автоматов, может быть, перенесена в различных вариантах и на вероятностные автоматы. При этом часто сохраняются свойства, присущие конечным автоматам. Например, можно так ввести по - нятие неотличимости состояний вероятностного автомата, что сохранятся некоторые теоремы об отличимости состояний простыми экспериментами. Вместе с тем в отличие от конечных автоматов, для которых минимальная форма автомата определена с точностью до изоморфизма однозначно, для данного вероятностного автомата может существовать континуум эквивалентных минимальных форм. Следующей модификацией понятия абстрактного конечного автомата является так называемый недетерминированный автомат, представляющий собой объект ( A, Q, В, х), где A, Q, В - алфавиты, имеющие прежний смысл, а х - QxAxQxB - отношение переходов-выходов. QxA в QXB, недетерминированный автомат называется детерминированным и фактически совпадает с абстрактным конечным автоматом, поскольку в этом случае функцию х можно рассматривать как пару функций ф -, if, отображающих QX в Q и В соответственно.  [27]

Большая часть понятий и задач, характерных для конечных автоматов, может быть, перенесена в различных вариантах и на вероятностные автоматы. При этом часто сохраняются свойства, присущие конечным автоматам. Например, можно так ввести по - нятие неотличимости состояний вероятностного автомата, что сохранятся некоторые теоремы об отличимости состояний простыми экспериментами. Вместе с тем в отличие от конечных автоматов, для которых минимальная форма автомата определена с точностью до изоморфизма однозначно, для данного вероятностного автомата может существовать континуум эквивалентных минимальных форм. Следующей модификацией понятия абстрактного конечного автомата является так называемый недетерминированный автомат, представляющий собой объект ( A, Q, В, х), где A, Q, В - алфавиты, имеющие прежний смысл, а х - QxAxQxB - отношение переходов-выходов. QxA в QXB, недетерминированный автомат называется детерминированным и фактически совпадает с абстрактным конечным автоматом, поскольку в этом случае функцию х можно рассматривать как пару функций ф -, if, отображающих QX в Q и В соответственно.  [28]

Состояния автомата, сигналы-воздействия и сигналы-реакции задаются буквами соответствующих алфавитов: алфавита состояний, а также алфавитов входных и выходных сигналов. Законы взаимодействия букв этих алфавитов задаются двумя функциями - функцией переходов и функцией выходов, отображающими пары ( состояние - входная буква), в состояния и выходные буквы соответственно. Входной средой для автомата является множество слов во входном алфавите, а внутренней и выходной его средами являются множества слов в алфавите состояний и выходном алфавите. Автомат побуквенно перерабатывает слова из входной среды в слова двух других сред. Этот процесс называется поведением автомата. Свойства алфавитов и функций определяют разл. В случае когда все алфавиты конечны, получают конечный автомат, в противном случае автомат называют бесконечным. Замена функций на отношения приводит к частичным и недетерминированным автоматам; использование случайных функций приводит к вероятностному автомату. При интерпретации входной среды термами или графами приходят к автоматам над термами и автоматам в лабиринтах.  [29]



Страницы:      1    2