10

Лемма 2.3.1. Каждый автоматный язык распознается некоторым конечным автоматом, не содержащим переходов с метками длины больше единицы и имеющим ровно одно начальное состояние и ровно одно заключительное состояние.

Пример 2.3.2. Рассмотрим язык, заданный конечным автоматом $\langle Q , \Sigma , \Delta , I , F \rangle$ , где Q = {1,2}, $\Sigma = \{ a , b , c , d \}$ , I = {1,2}, F = {1,2},

$\Delta = \{ \langle 1 , ab , 2 \rangle ,\ \langle 2 , cd , 1 \rangle \} .$

$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { % & *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \ar `dr_dl{[2,0]}_{ab} "3,2" & \\ % & & \\ % & *=[o][F=]{2} \ar @`{+/l16mm/} [] ^{} \ar `ul_ur{[-2,0]}_{cd} "1,2" & }$

Тот же язык распознается конечным автоматом $\langle Q' , \Sigma , \Delta' , I' , F' \rangle$ , где Q' = {0,1,2,3,4,5}, I' = {0}, F' = {5},

$\Delta' = \{ \langle 1 , a , 3 \rangle , \langle 3 , b , 2 \rangle , \langle 2 , c , 4 \rangle , \langle 4 , d , 1 \rangle , \langle 0 , \varepsilon , 1 \rangle , \langle 0 , \varepsilon , 2 \rangle , \langle 1 , \varepsilon , 5 \rangle , \langle 2 , \varepsilon , 5 \rangle \} .$

$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { % & & *=[o][F-]{1} \ar "2,4" _{a} \ar "2,5" ^{\varepsilon} & & \\ *=[o][F-]{0} \ar @`{+/l16mm/} [] ^{} \ar "1,3" ^{\varepsilon} \ar "3,3" _{\varepsilon} & *=[o][F-]{4} \ar "1,3" _{d} & & *=[o][F-]{3} \ar "3,3" _{b} & *=[o][F=]{5} \\ % & & *=[o][F-]{2} \ar "2,2" _{c} \ar "2,5" _{\varepsilon} & & }$

Здесь первые два перехода заменяют старый переход $\langle 1 , ab , 2 \rangle$ и следующие два перехода заменяют старый переход $\langle 2 , cd , 1 \rangle$ . Чтобы обеспечить единственность начального состояния, добавлены переходы $\langle 0 , \varepsilon , 1 \rangle$ и $\langle 0 , \varepsilon , 2 \rangle$ . Последние два перехода в $\Delta'$ обеспечивают единственность заключительного состояния.

Лемма 2.3.3. Каждый автоматный язык распознается некоторым конечным автоматом, содержащим только переходы с метками длины единица и имеющим ровно одно начальное состояние.

Доказательство. Согласно лемме 2.3.1 можно предположить, что исходный язык задан конечным автоматом $\langle Q , \Sigma , \Delta , I , F \rangle$ , не содержащим переходов с метками длины больше единицы, причем |I| = 1. Построим искомый конечный автомат $\langle Q' , \Sigma , \Delta' , I' , F' \rangle$ , положив Q' = Q, I' = I,

$\begin{align*} \Delta' &= \{ \langle p , a , r \rangle \mid a \in \Sigma \;\text{и найдется такое}\; q \in Q , \\&\quad \text{что}\; \langle q , a , r \rangle \in \Delta \;\text{и существует путь из}\; p \;\text{в}\; q \;\text{с меткой}\; \varepsilon \} ,\\ F' &= \{ p \in Q \mid \text{найдется такое}\; q \in F , \\&\quad \text{что существует путь из}\; p \;\text{в}\; q \;\text{с меткой}\; \varepsilon \} . \end{align*}$

Теорема 2.4.1. Каждый автоматный язык является праволинейным.

Без ограничения общности можно предположить, что исходный язык задан конечным автоматом $\langle Q , \Sigma , \Delta , I , F \rangle$ , где $Q \cap \Sigma = \varnothing$ и I = {q₀}. Положим N = Q, S = q₀ и

$P = \{ p \to x q \mid \langle p , x , q \rangle \in \Delta \} \cup \{ p \to \varepsilon \mid p \in F \} .$

Теорема 2.4.3. Каждый праволинейный язык является автоматным.

Доказательство. Без ограничения общности можно предположить, что исходный язык задан праволинейной грамматикой, не содержащей правил вида $A \to u$ , где $u \in \Sigma ^+$ . Положим Q = N, I = {S}, $F = \{ A \in N \mid ( A \to \varepsilon ) \in P \}$ и $\Delta = \{ \langle A , u , B \rangle \mid ( A \to u B ) \in P \}$ .