Конечные автоматы

Министерство образования и науки, молодежи и спорта Украины

Донбасская Государственная Машиностроительная Академия

Кафедра КИТ

Реферат

на тему «Конечные автоматы»

Ст. гр. ИТ-10-1

Ерфорта Д.В.

Проверил

преподаватель каф КИТ

Богдан М.П.

Краматорск 2011

Содержание

1. Введение

2. Детерминированный конечный автомат

3. Недетерминированный конечный автомат

4.Список используемой литературы

Введение

Следует понять, что такое конечный автомат. Конечный автомат – это абстрактное вычислительное устройство, которое на входе принимает цепочки, а на выходе сообщает о их принадлежности к определенному множеству символов.

Программисты очень часто сталкиваются с проблемой разделения строк на некоторые осмысленные части, проверки правильности ввода значений и т.д. В принципе, так как очень часто пользователем является человек, то самым естественным для него путем передачи информации будет человеческая речь. Тем не менее, задача выделения смысла из человеческой речи до сих пор не решена, поэтому для подобных случаев используется формальные описания некоторых структур - формальные грамматики. Конечные автоматы применяются для простейших грамматик. Обычно КА применятся для того, что называется лексическим анализом, т.е. для разбиения исходной строки на набор некоторых лексических единиц (например, выделение из текста слов и чисел).Простейший детерминированый КА работает следующим образом: в нем находится внутренний регистр для хранения текущего состояния и таблица правил вида "символ-состояние => состояние" позволяющая по текущему символу на ленте и текущему состоянию перейти в другое состояние (со сдвигом по ленте). Цепочка символов допустима, если КА завершил свою работу в одном из "разрешенных" состояний и не допустима в обратном случае.

Детерминированный конечный автомат

  Детерминированным конечным  автоматом  (ДКА) называется машина,  распознающая цепочки символов, в которой для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.Она имеет  входную ленту,  разбитую на клетки, головку на входной ленте (входную головку) и управляющее  устройство  с  конечным  числом состояний. Конечный автомат М можно представить в виде пятерки (S, L,  a,  s, F), где

           1) S - множество состояний  управляющего устройства 

           2) L -  входной алфавит  (каждая клетка входной ленты со-

держит символ из I),

           3) a - отображение SxL в S (если  a( s ,a1 ) =  s`, то всякий раз,  когда  М  находится  в состоянии s , а входная головка обозревает символ  a1 ,  М  сдвигает  входную  головку вправо и переходит в состояние s`),

           4) s- выделенное состояние в S, называемое  начальным 

           5) F - подмножество в S, называемое множеством допускающих (или  заключительных )  состояний

Рис.1 Пример ДКА

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

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

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

Конечный автомат можно описать с помощью диаграмм состояний и таблиц переходов.

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

Таблица переходов — табличное представление функции F. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

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

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

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

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

Рис.2 Пример НКА с пустыми переходами

Недетерминированным конечным  автоматом  называется пятерка (S, L, a , s, F), где

1) S - конечное множество состояний устройства управления;

           2) L - алфавит  входных символов;

           3)  a-  функция переходов, отображающая S x (I U {i}) в множество подмножеств множества S;

           4) s - начальное состояние  устройства управления;

           5) F   -  множество  заключительных (допускающих)  состояний.

Рис.3 НКА из одного состояния выходит несколько переходов, помеченных одним  символом

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

Приведем определение для графа ( или диаграммы) переходов автомата М = (S, I,  a,  s , F). Графом переходов автомата  М  называют  ориентированный граф G = (S,  E) с помеченными ребрами.

           Существует дополнительный результат или возможность сопоставить какому-либо взятому НКА эквивалентную "детерминированную" машину.  Однако  детерминированный конечный автомат, эквивалентный данному НКА с n состояниями, может иметь вплоть до 2 в n степени состояний. Поэтому переход от НКА к детерминированному автомату не всегда дает эффективный способ моделирования  недетерминированного конечного автомата.

Используемая литература

1.Л. Стерлинг, Э. Шапиро. Искусство программирования на языке Пролог(раздел 14.3)

2. http://www.rsdn.ru/article/alg/nka.xml

3. http://rensref.ru/14/dok.php?id=0132

4. http://ru.wikipedia.org/wiki/Конечный_автомат

5. http://chernykh.net/content/view/247/263/

6. http://www.codenet.ru/progr/alg/03.php