Курсовая на тему Модель недетерминированного конечного автомата

Автор: Антон

Тип работы: Курсовая

Предмет: Программирование

Страниц: 12

Год сдачи: 2010

ВУЗ, город: МЭИ (ТУ)

Выдержка

Теоретический материал.

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

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

Содержание

1. Постановка задачи.
2. Теоретический материал.
3. Математические расчёты.
4. Тестовые файлы.

Литература

1. Журнал RSDN #2 ¬ 2007
2. «Введение в схемы, автоматы и алгоритмы», М. И. Дехтярь. - М.: Наука, 2002. С. 642.
3. Статья на сайте Википедии: http://ru.wikipedia.org/wiki/Конечный_автомат
4. «Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход», М. В. Мозговой. - М.: Наука и Техника, 2006. С. 320.
5. «Справочник по математике для инженеров и учащихся втузов», И. Н. Бронштейн, К. А. Семендяев. - М.: Наука, 2007. - 708 с.