Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Реферат - Детерминированные и недетерминированные конечные автоматы - файл Доклад.doc


Реферат - Детерминированные и недетерминированные конечные автоматы
скачать (43.5 kb.)

Доступные файлы (1):

Доклад.doc68kb.03.11.2008 02:26скачать

Загрузка...

Доклад.doc

Реклама MarketGid:
Загрузка...
Детерминированным конечным автоматом (ДКА) называется устройство, описываемое следующими параметрами:

Q – конечное множество состояний.

Σ – конечное множество входных символов.

δ – функция перехода. Аргументы – состояние и входной символ, результат – состояние.

q0 – начальное состояние, принадлежит Q.

F – множество допускающих состояний, является подмножеством Q.

И функционирующее следующим образом:

Автомат начинает работу в состоянии q0.

Если автомат находится в состоянии qi, а на вход поступает символ b, то автомат переходит в состояние δ(qi, b).

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

Работа ДКА заключается в распознавании цепочек символов, принадлежащих множеству Σ. Если, обработав цепочку, автомат оказался в допускающем состоянии, то цепочка считается допустимой, если нет, то нет. Таким образом, ДКА задаёт некоторый язык – множество допускаемых им цепочек, алфавит этого языка – множество Σ.

Конечные автоматы удобно изображать графически. На рисунке 1 приведён несложный ДКА, допускающий цепочки из 0 и 1, заканчивающиеся символом 0. Начальное состояние помечено входящей в него стрелочкой, допускающее (в данном случае оно одно) – двойным кружком.



Рисунок 1. Простой детерминированный конечный автомат.

Второй вариант изображения автоматов – таблица переходов.

0 1

-> q0 q1 q0

    * q1 q1 q0

Таблица 1. Тот же самый конечный автомат.

По горизонтали отложены символы входного алфавита, по вертикали – состояния, начальное состояние отмечено стрелочкой, а допускающие – звёздочками. Этот способ изображения менее нагляден, и приведён только в качестве примера, использовать его «для дела» я не буду.

Определение недетерминированного конечного автомата (НКА) практически полностью повторяет приведённое выше определение ДКА. Отличий всего два:

δ – функция перехода. Аргументы – состояние и входной символ, результат – множество состояний (возможно – пустое).

Если автомат находится в состоянии qi, а на вход поступает символ b, то автомат переходит во множество состояний δ(qi, b). Если автомат находится во множестве состояний {qi}, то он переходит во множество состояний, получаемое объединением множеств δ(qi, b).



НКА тоже распознаёт цепочки символов, цепочка считается допустимой, если после её обработки множество состояний, в котором оказался автомат, содержит хотя бы одно допускающее. Таким образом, НКА также задаёт некоторый язык.

На рисунке 2 изображён простой НКА, допускающий цепочки из 0 и 1, заканчивающиеся на 00.



Рисунок 2. Простой недетерминированный конечный автомат.

Этот же автомат в виде таблицы:

0 1

-> q0 {q0, q1} {q0}

q1 {q2} (

    * q2 ( (

Таблица 2. Тот же самый недетерминированный конечный автомат.

Разберёмся, как он работает.

Допустим, на вход автомату поступила цепочка «100100».



Рисунок 3. Обработка цепочки 100100

В данном случае мы несколько удаляемся от определения НКА (множества состояний не представлены так явно). Картинка основана на следующей идее: каждый раз, когда по входному символу возможен переход в несколько состояний, порождается новая ветка вычислений, когда переходов нет – ветка «засыхает». Если хоть одна из «живых» веток ведёт в допускающее состояние – цепочка допущена.

В общем, подходы дают аналогичные результаты, за исключением одной мелочи. Слегка изменённый НКА, изображённый на рисунке 4, допускает любую цепочку символов {0, 1}, содержащую два нуля подряд. Если каждый раз честно порождать новую ветку, то при обработке цепочки «1001001….» получится дерево, изображённое на рисунке 5. Понятно, что две нижние ветки полностью совпадают (они представляют одинаковые состояния автомата, получают одинаковые входы, значит и результаты будут одинаковые), более того, каждый раз, когда в цепочке будет встречаться 00, будет порождаться ещё одна точно такая же ветка.


Скачать файл (43.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации