Определение 2.1.7. Путь (path) конечного автомата - это кортеж , где и для каждого i. При этом q0 - начало пути
qn - конец пути n
- длина пути w1...wn - метка пути.
Замечание 2.1.8. Для любого состояния существует путь . Его метка - , начало и конец совпадают.
Определение 2.1.9. Путь называется успешным если его начало принадлежит I, а конец принадлежит F.
Пример 2.1.2. Пусть Q = {1,2},
, I = {1}, F = {2},
Тогда - конечный автомат
Пример 2.1.10. Рассмотрим конечный автомат из примера
2.1.2. Путь является
успешным. Его метка - baaab.
Длина этого пути - 4.
Определение 2.1.11. Слово w допускается (is accepted, is
recognized) конечным автоматом M,
если оно является меткой некоторого успешного пути.
Определение 2.1.12. Язык, распознаваемый
конечным автоматом M, - это язык L(M), состоящий из меток всех успешных путей (то есть из
всех допускаемых данным автоматом слов). Будем также говорить, что автомат M распознает (recognizes, accepts) язык L(M).
Замечание 2.1.13. Если , то язык, распознаваемый конечным автоматом , содержит .
Определение 2.1.15. Два конечных автомата эквивалентны, если они распознают один и тот же язык.
Определение 2.1.16. Язык L
называется автоматным (finite-state
language), если существует конечный автомат,
распознающий этот язык.
Замечание 2.1.19. Каждый конечный язык является
автоматным.
Определение 2.1.20. Состояние q достижимо (reachable) из состояния p, если существует путь, началом которого
является p, а концом - q.
Определение 2.2.1. Конфигурацией
или мгновенным описанием (instantaneous
description) конечного автомата называется любая упорядоченная
пара , где и .
Замечание 2.2.2. Содержательно конфигурация представляет
собой "мгновенное описание" конечного автомата. Если представить, что
исходное слово, принадлежность которого рассматриваемому языку надо проверить,
дано в некотором "входном потоке", то в конфигурации слово w
есть та часть исходного слова, которая пока осталась во входном потоке (это
некоторый суффикс исходного слова), а q
- текущее состояние "управляющего устройства".
Определение 2.2.3. Определим на множестве всех
конфигураций конечного автомата M бинарное
отношение (такт работы (step))
следующим образом. Если и , то . Иногда вместо пишут .
Пример 2.2.4. Рассмотрим конечный автомат
из примера 2.1.2. Тогда .
Определение 2.2.5. Бинарное отношение определяется как рефлексивное, транзитивное замыкание
отношения .
Пример 2.2.6. Для конечного автомата из примера 2.1.2
выполняется и
.
Лемма 2.2.7. Пусть дан конечный
автомат . Слово принадлежит языку L(M) тогда
и только тогда, когда для некоторых и верно .
Лемма 2.2.8. Если и
,
то .