#"#"
title=Увеличить>#"1.files/image008.gif">
Рисунок 2 –
Недетерминированный конечный автомат с пустыми переходами
2. Из одного
состояния выходит несколько переходов, помеченных одним и тем же символом
(рисунок 3).
Рисунок 3 –
Недетерминированный конечный автомат с несколькими переходами
Существует
теорема, гласящая, что «Любой недетерминированный конечный автомат может быть
преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы
называются эквивалентными).
Однако, поскольку количество состояний в эквивалентном детерминированном
конечном автомате в худшем случае растёт экспоненциально с ростом количества
состояний исходного недетерминированного конечного автомата, на практике подобная
детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом
в общем случае не поддаются детерминизации.
В силу
последних двух замечаний, несмотря на большую сложность недетерминированных
конечных автоматов, для задач, связанных с обработкой текста, преимущественно
применяются именно недетерминированные конечные автоматы.
2.4 Автоматы и регулярные языки
Для автомата
можно определить язык (множество слов) в алфавите Σ, который он представляет –
так называется множество слов, при вводе которых автомат переходит из
начального состояния в одно из состояний множества F.
Теорема
Клини
гласит, что класс языков, представимых конечными автоматами, совпадает с
классом регулярных
языков. Кроме того, этот класс совпадает с классом языков,
задаваемых регулярными
грамматиками.
3.
Функциональные модели и блок-схемы решения задачи
Функциональные
модели и блок-схемы решения задачи представлены на рисунках 4 – 7.
Условные
обозначения:
·
cur – текущее слово;
·
char – текущий символ;
·
text – входное слово;
·
funct – функция смены состояний;
·
start – начальное состояние;
·
end – список конечных состояний.
Рисунок 4 –
Функциональная модель решения задачи для функции KA
Рисунок 5 – Функциональная
модель решения задачи для функции function1
Рисунок 6 –
Функциональная модель решения задачи для функции function2
Рисунок 7 – Функциональная
модель решения задачи для функции isOneof
4. Программная
реализация решения задачи
; Тестовый конечный автомат – функция, преобразуюцая состояние
; 'char' – текущий символ
; Возвращаемое значение: новое состояние
(defun function1 (cur char)
(cond
((and (eq char `a) (eq cur `qb))
`q1)
((and (eq char `b) (eq cur `qb))
`q2)
((and (eq char `c) (eq cur `q1))
`qe)
((and (eq char `c) (eq cur `q2))
`qe)
(t `q0)
)
)
; Тестовый конечный автомат – функция, преобразуюцая состояние
; Аргументы: 'cur' – текущее состояние
; 'char' – текущий символ
; Возвращаемое значение: новое состояние
(defun function2 (cur char)
(cond
((and (eq char `a) (eq cur `qb))
`q1)
((and (eq char `b) (eq cur `qb))
`q2)
((and (eq char `c) (eq cur `qb))
`q3)
((and (eq char `a) (eq cur `q1))
`q1)
((and (eq char `b) (eq cur `q2))
`q2)
((and (eq char `c) (eq cur `q3))
`q3)
(T nil)
)
)
; Функция проверки, является ли 'char' элементом 'set' (необходима для
остановки)
; Алгоритм проверки:
; 1. 'set' пусто => нет
; 2. 'char' совпадает с головой 'set' => да
; 3. 'char' является злементом хвоста 'set' => да
; 4. 'set' – не список => нет
(defun isOneOf (set char)
(cond
((eq set nil) nil)
((eq char (car set)) T)
((isOneOf (cdr set) char) T)
(T nil)
)
)
; Непосредственно конечный автомат
; Аргументы: 'begin' – начальное состояние
; 'end' – список конечных состояний
; 'move' – функция смены состояний
; 'text' – входное слово
; Возвращаемое значение: 'Correct' – входное слово
допустимо
; 'Incorrect' – входное слово недопустимо
; Алгоритм:
; 1. Лента пуста и
; а. текущее состояние финальное => слово допустимо
; б. текущее состояние не финальное => слово
недопустимо
; 2. Текущий символ допустим и лента не пуста =>
движемся дальше
(defun KA (begin end move text)
(cond
((eq text nil)
(cond
((isOneOf end begin) `Correct)
(T `Incorrect)
)
)
(T (KA (funcall move begin (car text))
end move (cdr text)))
)
)
(setq input_stream (open «d:\\text.txt»:direction:input))
; входное слово
(setq text (read input_stream))
; функция смены состояний
(setq funct (read input_stream))
; начальное состояние
(setq start (read input_stream))
(setq end (read input_stream))
(close input_stream)
(setq output_stream (open «d:\\KA.txt»:direction:output))
(print (KA start end funct text) output_stream)
(terpri output_stream)
(close output_stream)
5. Пример
выполнения программы
Пример 1
Рисунок 8 –
Входные данные
Рисунок 9 –
Выходные данные
Пример 2
Рисунок 10 –
Входные данные
Рисунок 11 –
Выходные данные
Пример 3.
Рисунок 12 –
Входные данные
Рисунок 13 –
Выходные данные
Заключение
Мышление в
терминах конечных автоматов (то есть разбиение исполнения программы на шаги
автомата и передача информации от шага к шагу через состояние) необходимо при
построении событийно-ориентированных приложений. В этом
случае программирование в стиле конечных автоматов оказывается единственной
альтернативой порождению множества процессов
или потоков управления.
Часто понятие
состояний и машин состояний используется для спецификации программ. Так, при проектировании
программного обеспечения с помощью UML для
описания поведения объектов используются диаграммы состояний. Кроме того, явное
выделение состояний используется в описании сетевых
протоколов.
Итогом работы можно считать созданную функциональную модель реализации
конечных автоматов. Созданная функциональная модель и ее программная реализация
могут служить органической частью решения более сложных задач.
Список использованных источников и литературы
1.
Бронштейн, И.Н. Справочник по математике для инженеров
и учащихся втузов [Текст] / И.Н. Бронштейн, К.А. Семендяев. – М.: Наука,
2007. – 708 с.
2.
Дехтярь,
М.И. Введение в схемы, автоматы и алгоритмы. [Электронный ресурс] / М.И. Дехтярь.
– М.: Наука, 2002. С. 642.
3.
Конечный
автомат [Электронный ресурс] – Режим доступа: http://ru/wikipedia.org/wiki/Конечный_автомат.
4.
Мозговой, М.В. Классика программирования:
алгоритмы, языки, автоматы, компиляторы. Практический подход. / М.В. Мозговой.
– М.: Наука и Техника, 2006. С. 320.
5.
Семакин,
И.Г. Основы программирования. [Текст] / И.Г. Семакин, А.П. Шестаков.
– М.: Мир, 2006. C. 346.
6.
Симанков,
В.С. Основы функционального программирования [Текст] / В.С. Симанков,
Т.Т. Зангиев, И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.
7.
Степанов,
П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] /
П.А. Степанов, А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.
8.
Хювенен Э. Мир Лиспа [Текст] / Э. Хювенен,
Й. Сеппянен. – М.: Мир, 1990. – 460 с.