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

Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...

Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...

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

2020-04-01 103
Функциональные модели и блок-схемы решения задачи 0.00 из 5.00 0 оценок
Заказать работу

Функциональные модели и блок-схемы решения задачи представлены на рисунках 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 для описания поведения объектов используются диаграммы состояний. Кроме того, явное выделение состояний используется в описании сетевых протоколов.

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

 

 



Поделиться с друзьями:

Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...

Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.013 с.