Курсовая работа: Лисп-реализация конечных автоматов
a, b, c – входной алфавит, из которого формируются строки, считываемые автоматом;
cc – строка, считываемая автоматом.
Проверим допустимо ли слово на ленте для данного автомата.
Согласно таблице переходов получаем:
с qb®q0
с q0®q0.
Так как q0 не соответствует множеству заключительных состояний, следовательно данное слово cc не допустимо.
Пример 2.
Таблица 2 – Таблица переходов
| char | a | b | c | a | b | с |
| cur | qb | qb | qb | q1 | q2 | q3 |
| state | q1 | q2 | q3 | q1 | q2 | q3 |
q1 – начальное состояние автомата;
q1, q2, q3 – множество заключительных состояний;
a, b, c – входной алфавит, из которого формируются строки, считываемые автоматом;
aaaaaa – строка, считываемая автоматом.
Проверим допустимо ли слово на ленте для данного автомата.
Согласно таблице переходов получаем:
a q1®q1
a q1®q1
a q1®q1
a q1®q1
a q1®q1
a q1®q1
Так как q1 соответствует множеству заключительных состояний, следовательно данное слово aaaaaa допустимо для данного автомата.
2. Математические и алгоритмические основы решения задачи
2.1 Понятие конечного автомата
Конечный автомат – в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии, что общее возможное количество состояний конечно. Конечный автомат является частным случаем абстрактного автомата.
Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров:
где:
Q – конечное множество состояний автомата;
q0 – начальное состояние автомата (
);