Автоматы и регулярные языки

2.4 Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет – так называется множество слов, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.

 

3. Функциональные модели и блок-схемы решения задачи

 

Функциональные модели и блок-схемы решения задачи представлены на рисунках 4 – 7.

Условные обозначения:

·          cur – текущее слово;

·          char – текущий символ;

·          text – входное слово;

·          funct – функция смены состояний;

·          start – начальное состояние;

·          end – список конечных состояний.

Рисунок 4 – Функциональная модель решения задачи для функции KA

Рисунок 5 – Функциональная модель решения задачи для функции function1

Рисунок 6 – Функциональная модель решения задачи для функции function2

Рисунок 7 – Функциональная модель решения задачи для функции isOneof

 

4. Программная реализация решения задачи

 

; Тестовый конечный автомат – функция, преобразуюцая состояние

; Аргументы: 'cur' – текущее состояние

; '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 с.