08

Определение 2.1.7. Путь (path) конечного автомата - это кортеж $\langle q_0 , e_1 , q_1 , e_2 , \ldots , q_n \rangle$ , где $n \geqslant 0$ и $e_i = \langle q_{i-1} , w_i , q_i \rangle \in \Delta$ для каждого i. При этом q₀ - начало пути q_n - конец пути n - длина пути w₁...w_n - метка пути.

Замечание 2.1.8. Для любого состояния $q \in Q$ существует путь $\langle q \rangle$ . Его метка - $\varepsilon$ , начало и конец совпадают.

Определение 2.1.9. Путь называется успешным если его начало принадлежит I, а конец принадлежит F.

Пример 2.1.2. Пусть Q = {1,2}, $\Sigma = \{ a , b \}$ , I = {1}, F = {2},

$\Delta = \{ \langle 1 , aaa , 1 \rangle ,\ \langle 1 , ab , 2 \rangle ,\ \langle 1 , b , 2 \rangle ,\ \langle 2 , \varepsilon , 1 \rangle \} .$

Тогда $\langle Q , \Sigma , \Delta , I , F \rangle$ - конечный автомат

Пример 2.1.10. Рассмотрим конечный автомат из примера 2.1.2. Путь $\langle 1 ,\ \langle 1 , b , 2 \rangle ,\ 2 ,\ \langle 2 , \varepsilon , 1 \rangle ,\ 1 ,\ \langle 1 , aaa , 1 \rangle ,\ 1 ,\ \langle 1 , b , 2 \rangle ,\ 2 \rangle$ является успешным. Его метка - 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. Если $I \cap F \neq \varnothing$ , то язык, распознаваемый конечным автоматом $\langle Q , \Sigma , \Delta , I , F \rangle$ , содержит $\varepsilon$ .

Определение 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) конечного автомата $\langle Q , \Sigma , \Delta , I , F \rangle$ называется любая упорядоченная пара $\langle q , w \rangle$ , где $q \in Q$ и $w \in \Sigma ^*$ .

Замечание 2.2.2. Содержательно конфигурация представляет собой "мгновенное описание" конечного автомата. Если представить, что исходное слово, принадлежность которого рассматриваемому языку надо проверить, дано в некотором "входном потоке", то в конфигурации $\langle q , w \rangle$ слово w есть та часть исходного слова, которая пока осталась во входном потоке (это некоторый суффикс исходного слова), а q - текущее состояние "управляющего устройства".

Определение 2.2.3. Определим на множестве всех конфигураций конечного автомата M бинарное отношение $\vdash$ (такт работы (step)) следующим образом. Если $\langle p , x , q \rangle \in \Delta$ и $w \in \Sigma ^*$ , то $\langle p , x w \rangle \vdash \langle q , w \rangle$ . Иногда вместо $\vdash$ пишут $\underset{ \Delta }{\vdash}$ .

Пример 2.2.4. Рассмотрим конечный автомат

$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{aaa} \ar `ur_r{+/u7mm/}`r_dr{[0,2]}^{ab} "1,3" \ar "1,3" ^{b} & & *=[o][F=]{2} \ar `dl_l{+/d7mm/}`l_ul{[0,-2]}^{\varepsilon} "1,1" }$

из примера 2.1.2. Тогда $\langle 1 , abba \rangle \vdash \langle 2 , ba \rangle$ .

Определение 2.2.5. Бинарное отношение $\overset * {\vdash}$ определяется как рефлексивное, транзитивное замыкание отношения $\vdash$ .

Пример 2.2.6. Для конечного автомата из примера 2.1.2 выполняется $\langle 1 , aaaab \rangle \overset * {\vdash} \langle 1 , aaaab \rangle$ и $\langle 1 , aaaab \rangle \overstar{\vdash} \langle 2 , \varepsilon \rangle$ .

Лемма 2.2.7. Пусть дан конечный автомат $M = \langle Q , \Sigma , \Delta , I , F \rangle$ . Слово $w \in \Sigma ^*$ принадлежит языку L(M) тогда и только тогда, когда для некоторых $p \in I$ и $q \in F$ верно $\langle p , w \rangle \overset * {\vdash} \langle q , \varepsilon \rangle$ .

Лемма 2.2.8. Если $\langle q_1 , x \rangle \overset * {\vdash} \langle q_2 , \varepsilon \rangle$ и $\langle q_2 , y \rangle \overset * {\vdash} \langle q_3 , \varepsilon \rangle$ , то $\langle q_1 , x y \rangle \overset * {\vdash} \langle q_3 , \varepsilon \rangle$ .