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

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

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

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

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

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

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

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

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

 

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

 

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

 

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

 

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

 

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

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

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

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

; Возвращаемое значение: новое состояние

(defun function 1 (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)

Пример выполнения программы

 

Пример 1

 

Рисунок 8 – Входные данные

 

Рисунок 9 – Выходные данные

 

Пример 2

 

Рисунок 10 – Входные данные

 

Рисунок 11 – Выходные данные

Пример 3.

 

Рисунок 12 – Входные данные

 

Рисунок 13 – Выходные данные

 

 

Заключение

 

Мышление в терминах конечных автоматов (то есть разбиение исполнения программы на шаги автомата и передача информации от шага к шагу через состояние) необходимо при построении событийно-ориентированных приложений. В этом случае программирование в стиле конечных автоматов оказывается единственной альтернативой порождению множества процессов или потоков управления.

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

Итогом работы можно считать созданную функциональную модель реализации конечных автоматов. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.