Учебная работа № 5935. «Контрольная Конечный автомат
Учебная работа № 5935. «Контрольная Конечный автомат
Содержание:
«Введение 3
1. Понятие конечные автоматы 4
2. Типы конечных автоматов 5
3. Представление конечных автоматов 6
4. Анализ конечных автоматов 8
6.Система конечных автоматов 11
7. Минимизация автоматов 13
8. Триггер как конечный автомат 15
Заключение 21
Список использованной литературы 22
1. Акимов В.А. Дискретная математика: логика, группы, графы. М.: Лаборатория Базовых Знаний, 2003. – 376 с.
2. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. — М.: ФОРУМ: ИНФРА-М, 2004. — 128 с.
3. Ершов Ю.А., Полюнин Е.А. Математическая логика: Учебное пособие для вузов. М.: Наука. Гл. ред. физ. — мат. лит., 1987. — 336 с.
4. Новиков Ф.А. Дискретная математика для программистов. — СПб: Питер, 2001. — 304 с.
5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Высшая школа, 2003. — 256 с.
6. Р. Хаггарти Дискретная математика для программистов Москва: Техносфера, 2003. — 320 с.
7. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. — М.: ИНФРА — М; Новосибирск: НГТУ, 2003. — 280 с.
»
Выдержка из похожей работы
Sх({})
в множество состояний недетерминированного
конечного автомата, Для детерминированного
автомата функция переходов отражает
множество Sх
во множество состояний автомата, Другими
словами, в зависимости от состояния и
входного символа,
определяет новое состояние автомата,
S0
— начальное состояние конечного автомата,
S0
S,
F
— множество конечных состояний автомата,
F
S,
Работа
конечного автомата представляет собой
последовательность шагов, Шаг определяется
состоянием автомата и входным символом,
Сам шаг состоит в изменении состояния
автомата и считывании следующего символа
входной последовательности,
Существуют
следующие правила преобразования
регулярных выражений в конечный автомат,
1 Регулярное
выражение “”
преобразуется в автомат из двух состояний
и
-перехода между ними (рисунок 1),
Рисунок
1, – Автомат для -перехода
2 Регулярное
выражение из одного символа “а”
преобразуется в конечный автомат из
двух состояний и перехода между ними
по входному сигналу а (рисунок 2),
Рисунок
2, – Автомат для перехода по символу а
3 Пусть
есть регулярное выражение rs
и уже построены конечные автоматы для
выражения r
и выражения s,
Тогда два автомата соединяются
последовательно, На рисунке 3 представлены
исходные автоматы для языков r
и s,
На рисунке автомат для распознавания
конкатенации этих языков,
Автомат
для r
Автомат для s
Рисунок
3, – Исходные автоматы
Рисунок
4, – Автомат для конкатенации языков
4 Пусть
есть регулярное выражение r
| s
и уже построены конечные автоматы для
выражения r
и выражения s
(рисунок 3)
