Два наиболее распространенных способа конечного задания
формального языка - это грамматики и автоматы.
Автоматами в данном контексте называют математические модели
некоторых вычислительных устройств.
В этой лекции рассматриваются конечные автоматы,
соответствующие в иерархии Хомского
праволинейным грамматикам.
Более сильные
В разделе 2.1 определяются понятия конечного автомата (для ясности такой автомат можно называть недетерминированным конечным автоматом) и распознаваемого конечным автоматом языка. В следующем разделе дается другое, но эквивалентное первому определение языка, распознаваемого конечным автоматом. Оно не является необходимым для дальнейшего изложения, но именно это определение поддается обобщению на случаи автоматов других типов.
В разделе 2.3 доказывается, что тот же класс автоматных языков можно получить, используя лишь конечные автоматы специального вида (они читают на каждом такте ровно один символ и имеют ровно одно начальное состояние). Во многих учебниках конечными автоматами называют именно такие автоматы.
Целую серию классических результатов теории формальных языков составляют теоремы о точном соответствии некоторых классов грамматик некоторым классам автоматов. Первая теорема из этой серии, утверждающая, что праволинейные грамматики порождают в точности автоматные языки, доказывается в разделе 2.4.
Другая серия результатов связана с возможностью сузить некоторый класс грамматик, не изменив при этом класс порождаемых ими языков. Обычно в таком случае грамматики из меньшего класса называются грамматиками в нормальной форме. В разделе 2.5* формулируется результат такого типа для праволинейных грамматик. Сама эта теорема не представляет большого интереса, но аналогичные результаты, доказываемые позже для контекстно-свободных грамматик, используются во многих доказательствах и алгоритмах.
Не все конечные автоматы подходят для конструирования распознающих устройств, пригодных для практических приложений, так как в общем случае конечный автомат не дает точного указания, как поступать на очередном шаге, а разрешает продолжать вычислительный процесс несколькими способами. Этого недостатка нет у детерминированных конечных автоматов (частного случая недетерминированных конечных автоматов), определенных в разделе 2.6. В разделе 2.7 доказывается, что каждый автоматный язык задается некоторым детерминированным конечным автоматом.
Определение 2.1.1. Конечный автомат
(Q
называются состояниями
(state),
элементы I - начальными
(initial) состояниями,
элементы F - заключительными
или допускающими
(final, accepting) состояниями.
Если $$\langle p , x , q \rangle \in \Delta$$,
то $$\langle p , x , q \rangle$$
называется переходом
(transition) из p в q,
а слово x - меткой
(label) этого перехода.
Пример 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.3.
Конечные автоматы можно изображать в виде диаграмм состояний
(state diagram) (иногда их называют диаграммами переходов
(transition diagram)).
На диаграмме каждое состояние обозначается кружком,
а переход - стрелкой.
Стрелка из p в q,
помеченная словом x,
показывает, что $$\langle p , x , q \rangle$$
является переходом данного конечного автомата.
Каждое начальное состояние распознается
по ведущей в него короткой стрелке.
Каждое допускающее состояние отмечается на диаграмме
двойным кружком.
Пример 2.1.4. На диаграмме изображен конечный автомат из примера 2.1.2.$$\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.5.
Если в конечном автомате имеются
несколько переходов с общим началом и общим концом,
то такие переходы называются параллельными.
Иногда на диаграмме состояний конечного автомата
параллельные переходы изображают одной стрелкой.
При этом
Пример 2.1.6. На диаграмме снова изображен конечный автомат из примера 2.1.2.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{aaa} \ar "1,3" <1mm> ^{ab,b} *=[o][F=]{2} \ar "1,1" <1mm> ^{\varepsilon} }$$
Определение 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.
При этом q0 - начало пути qn - конец пути n - длина пути w1...wn - метка пути.
Замечание 2.1.8. Для любого состояния $$q \in Q$$ существует путь $$\langle q \rangle$$. Его метка - $$\varepsilon$$, начало и конец совпадают.
Определение 2.1.9.
Путь называется успешным
если его начало принадлежит I,
а конец принадлежит F.
Пример 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 распознает
(L(M).
Замечание 2.1.13. Если $$I \cap F \neq \varnothing$$, то язык, распознаваемый конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$, содержит $$\varepsilon$$.
Пример 2.1.14.
Пусть $$M = \langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {1,2}, $$\Sigma = \{ a , b \}$$, I = {1}, F = {1,2},$$\Delta = \{
\langle 1 , a , 2 \rangle ,\
\langle 2 , b , 1 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F=]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" <0.6mm> ^{a}
*=[o][F=]{2}
\ar "1,1" <0.6mm> ^{b}
}$$
Тогда$$L ( M ) = \{ (ab)^n \mid n \geqslant 0 \} \cup \{ (ab)^n a \mid n \geqslant 0 \} .$$
Определение 2.1.15. Два конечных автомата эквивалентны, если они распознают один и тот же язык.
Определение 2.1.16.
Язык L называется автоматным
(
Замечание 2.1.17. Обычно в учебниках используется более узкое определение недетерминированного конечного автомата, но это не меняет класса автоматных языков (см. лемму 2.3.3.).
Пример 2.1.18. Рассмотрим однобуквенный алфавит $$\Sigma = \{ a \}$$. При любых фиксированных $$k \in \mathbb{N}$$ и $$m \in \mathbb{N}$$ язык $$\{ a^{ k + m n } \mid n \in \mathbb{N} \}$$ является автоматным.
Замечание 2.1.19. Каждый конечный язык является автоматным.
Определение 2.1.20.
Состояние q достижимо
(reachable)
из состояния p,
если существует путь, началом которого является p,
а концом - q.
Лемма 2.1.21. Каждый автоматный язык распознается некоторым конечным автоматом, в котором каждое состояние достижимо из некоторого начального состояния и из каждого состояния достижимо хотя бы одно заключительное состояние.
Пример 2.1.22.
Рассмотрим конечный автомат $$\langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {1,2,3,4}, $$\Sigma = \{ a , b , c , d \}$$, I = {1,2,4}, F = {1,3,4},$$\Delta = \{
\langle 1 , a , 2 \rangle ,\
\langle 1 , b , 4 \rangle ,\
\langle 3 , c , 4 \rangle ,\
\langle 4 , d , 1 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
%
*=[o][F=]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "2,1" _{a}
\ar "2,2" <0.6mm> ^{b}
*=[o][F=]{3}
\ar "2,2" ^{c}
\\
*=[o][F-]{2}
\ar @`{+/l16mm/} [] ^{}
*=[o][F=]{4}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" <0.6mm> ^{d}
}$$
Удалим те состояния
(и содержащие их переходы),
которые не удовлетворяют требованиям леммы 2.1.21.
Получается эквивалентный конечный автомат $$\langle Q' , \Sigma , \Delta' , I' , F' \rangle$$,
где Q' = {1,4}, I' = {1,4}, F' = {1,4},$$\Delta' = \{
\langle 1 , b , 4 \rangle ,\
\langle 4 , d , 1 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F=]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "2,1" <0.6mm> ^{b}
\\
*=[o][F=]{4}
\ar @`{+/l16mm/} [] ^{}
\ar "1,1" <0.6mm> ^{d}
}$$
Замечание 2.1.23
Естественным обобщением конечного автомата
является конечный преобразователь
(
В данном пособии конечные преобразователи рассматриваться не будут.
Упражнение 2.1.24. Найти конечный автомат, распознающий язык $$\{ u c v \mid u \in \{a,b\}^* ,\ v \in \{a,b\}^* \}$$
Упражнение 2.1.25. Найти конечный автомат, распознающий язык $$\{ w \in \{a,b,c\}^* \mid | w |_c \neq 1 \}$$
Упражнение 2.1.26. Найти конечный автомат, распознающий язык $$\{a,b\}^* - (\{ a^n \mid n \geqslant 0 \} \cup \{ b^n \mid n \geqslant 0 \})$$
Упражнение 2.1.27. Найти конечный автомат, распознающий язык $$\{ a u b \mid u \in \{a,b\}^* \} \cup \{ b u a \mid u \in \{a,b\}^* \}$$
Упражнение 2.1.28. Найти конечный автомат, распознающий язык $$\{ w \in \{a,b\}^* \mid | w |_a \geqslant 3 \}$$
Упражнение 2.1.28. Найти конечный автомат, распознающий язык $$\{ w \in \{a,b\}^+ \mid f(w) \ \vdots \ 4 \}$$, где $$f( \varepsilon ) \rightleftharpoons 0$$, $$f( x a ) \rightleftharpoons 1 - f( x )$$ и $$f( x b ) \rightleftharpoons -1 - f( x )$$ для любого $$x \in \{a,b\}^*$$
Определение 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}$$
определяется как рефлексивное,
Пример 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$$.
Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации $$\langle q_1 , x \rangle$$ в конфигурацию $$\langle q_2 , \varepsilon \rangle$$.
Упражнение 2.2.9. Рассмотрим конечный автомат.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \ar "1,2" ^{a} *=[o][F-]{2} \ar "1,3" ^{b} *=[o][F=]{3} }$$ Перечислить все конфигурации $$\langle q , w \rangle$$, удовлетворяющие условию $$\langle 1 , abaa \rangle \overset * {\vdash} \langle q , w \rangle$$.
Упражнение 2.2.10.
Существуют ли конечный автомат M,
состояния q1, q2
и слова x, y, z,
такие что $$\langle q_1 , x y \rangle \overset * {\vdash} \langle q_2 , y \rangle$$
и $$\langle q_1 , x z \rangle \overset * {\nvdash} \langle q_2 , z \rangle$$?
Упражнение 2.2.11. Как связаны |Q|, $$| \Sigma |$$, $$| \Delta |$$, |w|
и число достижимых из $$\langle q , w \rangle$$
(в смысле $$\overset * {\vdash}$$ )
конфигураций?
Лемма 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.3.4.
Пусть $$M = \langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {1,2,3}, $$\Sigma = \{ a , b \}$$, I = {1}, F = {3},$$\Delta = \{
\langle 1 , a , 2 \rangle ,\
\langle 2 , b , 2 \rangle ,\
\langle 2 , \varepsilon , 3 \rangle ,\
\langle 3 , a , 3 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" ^{a}
*=[o][F-]{2}
\rloop{0,1} ^{b}
\ar "1,3" ^{\varepsilon}
*=[o][F=]{3}
\rloop{0,1} ^{a}
}$$
Легко убедиться, что $$L ( M ) = \{ a b^m a^n \mid m \geqslant 0, n \geqslant 0 \}$$.
Тот же язык распознается конечным автоматом $$\langle Q , \Sigma , \Delta' , I , F' \rangle$$,
где F' = {2,3}
и$$\Delta' = \{
\langle 1 , a , 2 \rangle ,\
\langle 2 , b , 2 \rangle ,\
\langle 2 , a , 3 \rangle ,\
\langle 3 , a , 3 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" ^{a}
*=[o][F=]{2}
\rloop{0,1} ^{b}
\ar "1,3" ^{a}
*=[o][F=]{3}
\rloop{0,1} ^{a}
}$$
Упражнение 2.3.5. Найти конечный автомат с однобуквенными переходами, распознающий язык $$\{ a^n b^m \mid n \geqslant 3 ,\ m \geqslant 3 \}$$
Упражнение 2.3.6. Найти конечный автомат с однобуквенными переходами, распознающий язык $$\{ a^n b^m c^k d \mid n \geq 0 ,\ m \geqslant 0 ,\ k \geqslant 0 \}$$
Упражнение 2.3.7. Существуют ли автоматный язык, который не распознается никаким конечным автоматом, содержащим только переходы с метками длины единица и имеющим ровно одно начальное состояние и ровно одно заключительное состояние?
Теорема 2.4.1. Каждый автоматный язык является праволинейным.
Без ограничения общности можно предположить,
что исходный язык задан конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$,
где $$Q \cap \Sigma = \varnothing$$
и I = {q0}.
Положим N = Q, S = q0
и$$P = \{ p \to x q \mid \langle p , x , q \rangle \in \Delta \} \cup
\{ p \to \varepsilon \mid p \in F \} .$$
Пример 2.4.2. Язык, распознаваемый конечным автоматом из примера 2.1.2, порождается грамматикой$$\begin{align*} K_1 \; {\to} \; aaa K_1 , \\ K_1 \; {\to} \; ab K_2 , \\ K_1 \; {\to} \; b K_2 , \\ K_2 \; {\to} \; K_1 , \\ K_2 \; {\to} \; \varepsilon . \end{align*}$$
Теорема 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 \}$$.
Пример 2.4.4.
Пусть $$\Sigma = \{ a , b \}$$.
Рассмотрим грамматику$$\begin{align*}
S \; {\to} \; aa , \\
S \; {\to} \; T , \\
T \; {\to} \; baT , \\
T \; {\to} \; a .
\end{align*}$$
Она эквивалентна грамматике$$\begin{align*}
S \; {\to} \; aaE , \\
S \; {\to} \; T , \\
T \; {\to} \; baT , \\
T \; {\to} \; aE , \\
E \; {\to} \; \varepsilon .
\end{align*}$$
Язык, порождаемый этими грамматиками,
распознается конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {S,T,E}, I = {S}, F = {E}
и$$\Delta = \{
\langle S , aa , E \rangle ,\
\langle S , \varepsilon , T \rangle ,\
\langle T , ba , T \rangle ,\
\langle T , a , E \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{S}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" ^{\varepsilon}
\ar "2,2" _{aa}
*=[o][F-]{T}
\rloop{0,1} ^{ba}
\ar "2,2" ^{a}
\\
%
*=[o][F=]{E}
}$$
Упражнение 2.4.5. Найти праволинейную грамматику, порождающую язык $$\{ w \in \{a,b\}^* \mid | w |_a \ \vdots \ 2 ,\ | w |_b\ \vdots \ 2\} $$
Упражнение 2.4.6. Существует ли такая праволинейная грамматика G,
что язык L(G)R
не порождается ни одной праволинейной грамматикой,
имеющей столько же правил, сколько грамматика G?
Упражнение 2.4.7. Существует ли такая праволинейная грамматика G,
что язык L(G)R
не порождается ни одной праволинейной грамматикой с количеством правил n + 1,
где n - количество правил в грамматике G?
Упражнение 2.4.8. Существует ли такая праволинейная грамматика G
с тремя вспомогательными символами,
что язык L(G)R
не порождается ни одной праволинейной грамматикой
с тремя вспомогательными символами?
Определение 2.5.1. Праволинейная грамматика в нормальной форме
( автоматная грамматика, регулярная грамматика,
Теорема 2.5.2. Каждая праволинейная грамматика эквивалентна некоторой праволинейной грамматике в нормальной форме.
Доказательство. Применим последовательно теорему 2.4.3, лемму 2.3.3 и воспользуемся конструкцией из доказательства теоремы 2.4.1.
Теорема 2.5.3. Если праволинейный язык не содержит пустого слова, то он порождается некоторой праволинейной грамматикой в нормальной форме без $$\varepsilon$$ -правил.
Упражнение 2.5.4. Найти праволинейную грамматику, эквивалентную грамматике$$\begin{align*} S \; {\to} \; E, E \; {\to} \; a, \\ S \; {\to} \; b E, E \; {\to} \; b S . \\ S \; {\to} \; ca E, \end{align*}$$
Упражнение 2.5.5. Найти праволинейную грамматику в нормальной форме без $$\varepsilon$$ -правил, порождающую язык$$\{ a^k b^m c^n \mid k \geq 0 ,\ m \geqslant 1 ,\ n \geqslant 0 \} .$$
Упражнение 2.5.6. Найти праволинейную грамматику в нормальной форме без $$\varepsilon$$ -правил, порождающую язык$$\{a,b\}^* - (\{ a^n \mid n \geqslant 0 \} \cup \{ b^n \mid n \geqslant 0 \}) .$$
Определение 2.6.1.
Конечный автомат $$\langle Q , \Sigma , \Delta , I , F \rangle$$
называется детерминированным
(
I
содержит ровно один элемент;|x| = 1 ;Пример 2.6.2. Конечный автомат из примера 2.1.14 является детерминированным.
Определение 2.6.3. Детерминированный конечный автомат $$M = \langle Q , \Sigma , \Delta , I , F \rangle$$ называется полным (complete), если для каждого состояния $$p \in Q$$ и для каждого символа $$a \in \Sigma$$ найдется такое состояние $$q \in Q$$, что $$\langle p , a , q \rangle \in \Delta$$.
Пример 2.6.4.
Конечный автомат из примера 2.1.14
эквивалентен полному детерминированному конечному автомату $$\langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {1,2,3}, $$\Sigma = \{ a , b \}$$, I = {1}, F = {1,2},$$\Delta = \{
\langle 1 , a , 2 \rangle ,\
\langle 1 , b , 3 \rangle ,\
\langle 2 , a , 3 \rangle ,\
\langle 2 , b , 1 \rangle ,\
\langle 3 , a , 3 \rangle ,\
\langle 3 , b , 3 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F=]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" <0.6mm> ^{a}
\ar "2,2" _{b}
*=[o][F=]{2}
\ar "1,1" <0.6mm> ^{b}
\ar "2,2" ^{a}
\\
%
*=[o][F-]{3}
\rloop{1,0} ^{a}
\rloop{0,-1} ^{b}
}$$
Замечание 2.6.5. Некоторые авторы используют в определении полного детерминированного конечного автомата вместо отношения $$\Delta$$ функцию $$\delta \colon Q \times \Sigma \to Q$$. От функции $$\delta$$ можно перейти к отношению $$\Delta$$, положив$$\Delta = \{ \langle p , a , \delta ( p , a ) \rangle \mid p \in Q , \; a \in \Sigma \} .$$
Упражнение 2.6.6. Является ли детерминированным следующий конечный автомат?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=1mm{ % *=[o][F-]{2} \ar "2,5" ^{b} \rloop{0,1} ^{a} \rloop{0,-1} _{b} \\ *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,3" ^{a} \ar "3,3" ^{b} *=[o][F=]{4} \\ % *=[o][F-]{3} \rloop{0,1} _{a} \rloop{0,-1} ^{b} \ar "2,5" ^{a} }$$
Упражнение 2.6.7. Является ли полным следующий детерминированный конечный автомат с алфавитом $$\Sigma = \{a,b,c\}$$?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \ar "1,2" ^{c} *=[o][F-]{2} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \ar "1,3" ^{c} *=[o][F=]{3} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \rloop{1,0} ^{c} }$$
Теорема 2.7.1 Каждый автоматный язык распознается некоторым полным детерминированным конечным автоматом.
Доказательство. Без ограничения общности можно предположить, что исходный язык задан конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$, содержащим только переходы с метками длины единица. Для любых $$a \in \Sigma$$ и $$H \subseteq Q$$ обозначим$$\Delta _ a ( H ) \rightleftharpoons \{ q \in Q \mid \langle p , a , q \rangle \in \Delta \mathspace\text{для некоторого}\mathspace p \in H \} .$$
Обозначим через $$\mathcal{P} ({ Q })$$
множество всех подмножеств множества Q.
Построим искомый полный детерминированный конечный автомат $$\langle Q' , \Sigma , \Delta' , I' , F' \rangle$$,
положив $$Q' = \mathcal{P} ({ Q })$$,$$\Delta' = \{ \langle H , a , \Delta _ a ( H ) \rangle \mid
H \subseteq Q ,\; a \in \Sigma \} ,$$
$$I' = {I}$$
и $$F' = \{ H \subseteq Q \mid H \cap F \neq \varnothing \}$$.
Пример 2.7.2. Пусть $$\Sigma = \{ a , b \}$$. Рассмотрим конечный автомат $$M = \langle \{ 1 , 2 , 3 \} , \Sigma , \Delta , \{ 1 \} , \{ 3 \} \rangle$$, где$$\Delta = \{ \langle 1 , a , 1 \rangle ,\ \langle 1 , b , 1 \rangle ,\ \langle 1 , a , 2 \rangle ,\ \langle 2 , b , 3 \rangle \} .$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \ar "1,2" ^{a} *=[o][F-]{2} \ar "1,3" ^{b} *=[o][F=]{3} }$$ Если применить конструкцию из доказательства теоремы 2.7.1. и затем удалить состояния, не достижимые из начального состояния, то получится полный детерминированный конечный автомат$$M' = \langle \{ \{ 1 \} , \{ 1 , 2 \} , \{ 1 , 3 \} \} , \Sigma , \Delta' , \{ \{ 1 \} \} , \{ \{ 1 , 3 \} \} \rangle ,$$ где$$\begin{multiline*} \Delta' = \{ \langle \{ 1 \} , a , \{ 1 , 2 \} \rangle ,\ \langle \{ 1 \} , b , \{ 1 \} \rangle ,\ \langle \{ 1 , 2 \} , a , \{ 1 , 2 \} \rangle ,\ \\ \langle \{ 1 , 2 \} , b , \{ 1 , 3 \} \rangle ,\ \langle \{ 1 , 3 \} , a , \{ 1 , 2 \} \rangle ,\ \langle \{ 1 , 3 \} , b , \{ 1 \} \rangle \} . \end{multiline*}$$ $$\objectwidth={7.5mm} \objectheight={7.5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{b} \ar "1,2" ^{a} *=[o][F-]{1,2} \rloop{0,1} ^{a} \ar "2,2" <0.6mm> ^{b} \\ % *=[o][F=]{1,3} \ar "1,2" <0.6mm> ^{a} \ar "1,1" ^{b} }$$
Упражнение 2.7.3. Найти полный детерминированный конечный автомат, эквивалентный автомату, изображенному на диаграмме.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "2,1" ^{ab} \\ *=[o][F=]{2} \ar @`{+/l16mm/} [] ^{} \rloop{1,0} ^{a} }$$
Упражнение 2.7.4. Найти детерминированный конечный автомат для языка, порождаемого грамматикой$$\begin{align*} S \; {\to} \; a T , \\ S \; {\to} \; a R , \\ T \; {\to} \; b T , \\ T \; {\to} \; \varepsilon , \\ R \; {\to} \; a R , \\ R \; {\to} \; \varepsilon . \end{align*}$$
Упражнение 2.7.5. Найти детерминированный конечный автомат, распознающий язык $$\{ a u b \mid u \in \{a,b\}^* \} \cup \{ b u a \mid u \in \{a,b\}^* \} $$
Два наиболее распространенных способа конечного задания
формального языка - это грамматики и автоматы.
Автоматами в данном контексте называют математические модели
некоторых вычислительных устройств.
В этой лекции рассматриваются конечные автоматы,
соответствующие в иерархии Хомского
праволинейным грамматикам.
Более сильные
В разделе 2.1 определяются понятия конечного автомата (для ясности такой автомат можно называть недетерминированным конечным автоматом) и распознаваемого конечным автоматом языка. В следующем разделе дается другое, но эквивалентное первому определение языка, распознаваемого конечным автоматом. Оно не является необходимым для дальнейшего изложения, но именно это определение поддается обобщению на случаи автоматов других типов.
В разделе 2.3 доказывается, что тот же класс автоматных языков можно получить, используя лишь конечные автоматы специального вида (они читают на каждом такте ровно один символ и имеют ровно одно начальное состояние). Во многих учебниках конечными автоматами называют именно такие автоматы.
Целую серию классических результатов теории формальных языков составляют теоремы о точном соответствии некоторых классов грамматик некоторым классам автоматов. Первая теорема из этой серии, утверждающая, что праволинейные грамматики порождают в точности автоматные языки, доказывается в разделе 2.4.
Другая серия результатов связана с возможностью сузить некоторый класс грамматик, не изменив при этом класс порождаемых ими языков. Обычно в таком случае грамматики из меньшего класса называются грамматиками в нормальной форме. В разделе 2.5* формулируется результат такого типа для праволинейных грамматик. Сама эта теорема не представляет большого интереса, но аналогичные результаты, доказываемые позже для контекстно-свободных грамматик, используются во многих доказательствах и алгоритмах.
Не все конечные автоматы подходят для конструирования распознающих устройств, пригодных для практических приложений, так как в общем случае конечный автомат не дает точного указания, как поступать на очередном шаге, а разрешает продолжать вычислительный процесс несколькими способами. Этого недостатка нет у детерминированных конечных автоматов (частного случая недетерминированных конечных автоматов), определенных в разделе 2.6. В разделе 2.7 доказывается, что каждый автоматный язык задается некоторым детерминированным конечным автоматом.
Определение 2.1.1. Конечный автомат
(Q
называются состояниями
(state),
элементы I - начальными
(initial) состояниями,
элементы F - заключительными
или допускающими
(final, accepting) состояниями.
Если $$\langle p , x , q \rangle \in \Delta$$,
то $$\langle p , x , q \rangle$$
называется переходом
(transition) из p в q,
а слово x - меткой
(label) этого перехода.
Пример 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.3.
Конечные автоматы можно изображать в виде диаграмм состояний
(state diagram) (иногда их называют диаграммами переходов
(transition diagram)).
На диаграмме каждое состояние обозначается кружком,
а переход - стрелкой.
Стрелка из p в q,
помеченная словом x,
показывает, что $$\langle p , x , q \rangle$$
является переходом данного конечного автомата.
Каждое начальное состояние распознается
по ведущей в него короткой стрелке.
Каждое допускающее состояние отмечается на диаграмме
двойным кружком.
Пример 2.1.4. На диаграмме изображен конечный автомат из примера 2.1.2.$$\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.5.
Если в конечном автомате имеются
несколько переходов с общим началом и общим концом,
то такие переходы называются параллельными.
Иногда на диаграмме состояний конечного автомата
параллельные переходы изображают одной стрелкой.
При этом
Пример 2.1.6. На диаграмме снова изображен конечный автомат из примера 2.1.2.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{aaa} \ar "1,3" <1mm> ^{ab,b} *=[o][F=]{2} \ar "1,1" <1mm> ^{\varepsilon} }$$
Определение 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.
При этом q0 - начало пути qn - конец пути n - длина пути w1...wn - метка пути.
Замечание 2.1.8. Для любого состояния $$q \in Q$$ существует путь $$\langle q \rangle$$. Его метка - $$\varepsilon$$, начало и конец совпадают.
Определение 2.1.9.
Путь называется успешным
если его начало принадлежит I,
а конец принадлежит F.
Пример 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 распознает
(L(M).
Замечание 2.1.13. Если $$I \cap F \neq \varnothing$$, то язык, распознаваемый конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$, содержит $$\varepsilon$$.
Пример 2.1.14.
Пусть $$M = \langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {1,2}, $$\Sigma = \{ a , b \}$$, I = {1}, F = {1,2},$$\Delta = \{
\langle 1 , a , 2 \rangle ,\
\langle 2 , b , 1 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F=]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" <0.6mm> ^{a}
*=[o][F=]{2}
\ar "1,1" <0.6mm> ^{b}
}$$
Тогда$$L ( M ) = \{ (ab)^n \mid n \geqslant 0 \} \cup \{ (ab)^n a \mid n \geqslant 0 \} .$$
Определение 2.1.15. Два конечных автомата эквивалентны, если они распознают один и тот же язык.
Определение 2.1.16.
Язык L называется автоматным
(
Замечание 2.1.17. Обычно в учебниках используется более узкое определение недетерминированного конечного автомата, но это не меняет класса автоматных языков (см. лемму 2.3.3.).
Пример 2.1.18. Рассмотрим однобуквенный алфавит $$\Sigma = \{ a \}$$. При любых фиксированных $$k \in \mathbb{N}$$ и $$m \in \mathbb{N}$$ язык $$\{ a^{ k + m n } \mid n \in \mathbb{N} \}$$ является автоматным.
Замечание 2.1.19. Каждый конечный язык является автоматным.
Определение 2.1.20.
Состояние q достижимо
(reachable)
из состояния p,
если существует путь, началом которого является p,
а концом - q.
Лемма 2.1.21. Каждый автоматный язык распознается некоторым конечным автоматом, в котором каждое состояние достижимо из некоторого начального состояния и из каждого состояния достижимо хотя бы одно заключительное состояние.
Пример 2.1.22.
Рассмотрим конечный автомат $$\langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {1,2,3,4}, $$\Sigma = \{ a , b , c , d \}$$, I = {1,2,4}, F = {1,3,4},$$\Delta = \{
\langle 1 , a , 2 \rangle ,\
\langle 1 , b , 4 \rangle ,\
\langle 3 , c , 4 \rangle ,\
\langle 4 , d , 1 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
%
*=[o][F=]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "2,1" _{a}
\ar "2,2" <0.6mm> ^{b}
*=[o][F=]{3}
\ar "2,2" ^{c}
\\
*=[o][F-]{2}
\ar @`{+/l16mm/} [] ^{}
*=[o][F=]{4}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" <0.6mm> ^{d}
}$$
Удалим те состояния
(и содержащие их переходы),
которые не удовлетворяют требованиям леммы 2.1.21.
Получается эквивалентный конечный автомат $$\langle Q' , \Sigma , \Delta' , I' , F' \rangle$$,
где Q' = {1,4}, I' = {1,4}, F' = {1,4},$$\Delta' = \{
\langle 1 , b , 4 \rangle ,\
\langle 4 , d , 1 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F=]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "2,1" <0.6mm> ^{b}
\\
*=[o][F=]{4}
\ar @`{+/l16mm/} [] ^{}
\ar "1,1" <0.6mm> ^{d}
}$$
Замечание 2.1.23
Естественным обобщением конечного автомата
является конечный преобразователь
(
В данном пособии конечные преобразователи рассматриваться не будут.
Упражнение 2.1.24. Найти конечный автомат, распознающий язык $$\{ u c v \mid u \in \{a,b\}^* ,\ v \in \{a,b\}^* \}$$
Упражнение 2.1.25. Найти конечный автомат, распознающий язык $$\{ w \in \{a,b,c\}^* \mid | w |_c \neq 1 \}$$
Упражнение 2.1.26. Найти конечный автомат, распознающий язык $$\{a,b\}^* - (\{ a^n \mid n \geqslant 0 \} \cup \{ b^n \mid n \geqslant 0 \})$$
Упражнение 2.1.27. Найти конечный автомат, распознающий язык $$\{ a u b \mid u \in \{a,b\}^* \} \cup \{ b u a \mid u \in \{a,b\}^* \}$$
Упражнение 2.1.28. Найти конечный автомат, распознающий язык $$\{ w \in \{a,b\}^* \mid | w |_a \geqslant 3 \}$$
Упражнение 2.1.28. Найти конечный автомат, распознающий язык $$\{ w \in \{a,b\}^+ \mid f(w) \ \vdots \ 4 \}$$, где $$f( \varepsilon ) \rightleftharpoons 0$$, $$f( x a ) \rightleftharpoons 1 - f( x )$$ и $$f( x b ) \rightleftharpoons -1 - f( x )$$ для любого $$x \in \{a,b\}^*$$
Определение 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}$$
определяется как рефлексивное,
Пример 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$$.
Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации $$\langle q_1 , x \rangle$$ в конфигурацию $$\langle q_2 , \varepsilon \rangle$$.
Упражнение 2.2.9. Рассмотрим конечный автомат.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \ar "1,2" ^{a} *=[o][F-]{2} \ar "1,3" ^{b} *=[o][F=]{3} }$$ Перечислить все конфигурации $$\langle q , w \rangle$$, удовлетворяющие условию $$\langle 1 , abaa \rangle \overset * {\vdash} \langle q , w \rangle$$.
Упражнение 2.2.10.
Существуют ли конечный автомат M,
состояния q1, q2
и слова x, y, z,
такие что $$\langle q_1 , x y \rangle \overset * {\vdash} \langle q_2 , y \rangle$$
и $$\langle q_1 , x z \rangle \overset * {\nvdash} \langle q_2 , z \rangle$$?
Упражнение 2.2.11. Как связаны |Q|, $$| \Sigma |$$, $$| \Delta |$$, |w|
и число достижимых из $$\langle q , w \rangle$$
(в смысле $$\overset * {\vdash}$$ )
конфигураций?
Лемма 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.3.4.
Пусть $$M = \langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {1,2,3}, $$\Sigma = \{ a , b \}$$, I = {1}, F = {3},$$\Delta = \{
\langle 1 , a , 2 \rangle ,\
\langle 2 , b , 2 \rangle ,\
\langle 2 , \varepsilon , 3 \rangle ,\
\langle 3 , a , 3 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" ^{a}
*=[o][F-]{2}
\rloop{0,1} ^{b}
\ar "1,3" ^{\varepsilon}
*=[o][F=]{3}
\rloop{0,1} ^{a}
}$$
Легко убедиться, что $$L ( M ) = \{ a b^m a^n \mid m \geqslant 0, n \geqslant 0 \}$$.
Тот же язык распознается конечным автоматом $$\langle Q , \Sigma , \Delta' , I , F' \rangle$$,
где F' = {2,3}
и$$\Delta' = \{
\langle 1 , a , 2 \rangle ,\
\langle 2 , b , 2 \rangle ,\
\langle 2 , a , 3 \rangle ,\
\langle 3 , a , 3 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" ^{a}
*=[o][F=]{2}
\rloop{0,1} ^{b}
\ar "1,3" ^{a}
*=[o][F=]{3}
\rloop{0,1} ^{a}
}$$
Упражнение 2.3.5. Найти конечный автомат с однобуквенными переходами, распознающий язык $$\{ a^n b^m \mid n \geqslant 3 ,\ m \geqslant 3 \}$$
Упражнение 2.3.6. Найти конечный автомат с однобуквенными переходами, распознающий язык $$\{ a^n b^m c^k d \mid n \geq 0 ,\ m \geqslant 0 ,\ k \geqslant 0 \}$$
Упражнение 2.3.7. Существуют ли автоматный язык, который не распознается никаким конечным автоматом, содержащим только переходы с метками длины единица и имеющим ровно одно начальное состояние и ровно одно заключительное состояние?
Теорема 2.4.1. Каждый автоматный язык является праволинейным.
Без ограничения общности можно предположить,
что исходный язык задан конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$,
где $$Q \cap \Sigma = \varnothing$$
и I = {q0}.
Положим N = Q, S = q0
и$$P = \{ p \to x q \mid \langle p , x , q \rangle \in \Delta \} \cup
\{ p \to \varepsilon \mid p \in F \} .$$
Пример 2.4.2. Язык, распознаваемый конечным автоматом из примера 2.1.2, порождается грамматикой$$\begin{align*} K_1 \; {\to} \; aaa K_1 , \\ K_1 \; {\to} \; ab K_2 , \\ K_1 \; {\to} \; b K_2 , \\ K_2 \; {\to} \; K_1 , \\ K_2 \; {\to} \; \varepsilon . \end{align*}$$
Теорема 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 \}$$.
Пример 2.4.4.
Пусть $$\Sigma = \{ a , b \}$$.
Рассмотрим грамматику$$\begin{align*}
S \; {\to} \; aa , \\
S \; {\to} \; T , \\
T \; {\to} \; baT , \\
T \; {\to} \; a .
\end{align*}$$
Она эквивалентна грамматике$$\begin{align*}
S \; {\to} \; aaE , \\
S \; {\to} \; T , \\
T \; {\to} \; baT , \\
T \; {\to} \; aE , \\
E \; {\to} \; \varepsilon .
\end{align*}$$
Язык, порождаемый этими грамматиками,
распознается конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {S,T,E}, I = {S}, F = {E}
и$$\Delta = \{
\langle S , aa , E \rangle ,\
\langle S , \varepsilon , T \rangle ,\
\langle T , ba , T \rangle ,\
\langle T , a , E \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{S}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" ^{\varepsilon}
\ar "2,2" _{aa}
*=[o][F-]{T}
\rloop{0,1} ^{ba}
\ar "2,2" ^{a}
\\
%
*=[o][F=]{E}
}$$
Упражнение 2.4.5. Найти праволинейную грамматику, порождающую язык $$\{ w \in \{a,b\}^* \mid | w |_a \ \vdots \ 2 ,\ | w |_b\ \vdots \ 2\} $$
Упражнение 2.4.6. Существует ли такая праволинейная грамматика G,
что язык L(G)R
не порождается ни одной праволинейной грамматикой,
имеющей столько же правил, сколько грамматика G?
Упражнение 2.4.7. Существует ли такая праволинейная грамматика G,
что язык L(G)R
не порождается ни одной праволинейной грамматикой с количеством правил n + 1,
где n - количество правил в грамматике G?
Упражнение 2.4.8. Существует ли такая праволинейная грамматика G
с тремя вспомогательными символами,
что язык L(G)R
не порождается ни одной праволинейной грамматикой
с тремя вспомогательными символами?
Определение 2.5.1. Праволинейная грамматика в нормальной форме
( автоматная грамматика, регулярная грамматика,
Теорема 2.5.2. Каждая праволинейная грамматика эквивалентна некоторой праволинейной грамматике в нормальной форме.
Доказательство. Применим последовательно теорему 2.4.3, лемму 2.3.3 и воспользуемся конструкцией из доказательства теоремы 2.4.1.
Теорема 2.5.3. Если праволинейный язык не содержит пустого слова, то он порождается некоторой праволинейной грамматикой в нормальной форме без $$\varepsilon$$ -правил.
Упражнение 2.5.4. Найти праволинейную грамматику, эквивалентную грамматике$$\begin{align*} S \; {\to} \; E, E \; {\to} \; a, \\ S \; {\to} \; b E, E \; {\to} \; b S . \\ S \; {\to} \; ca E, \end{align*}$$
Упражнение 2.5.5. Найти праволинейную грамматику в нормальной форме без $$\varepsilon$$ -правил, порождающую язык$$\{ a^k b^m c^n \mid k \geq 0 ,\ m \geqslant 1 ,\ n \geqslant 0 \} .$$
Упражнение 2.5.6. Найти праволинейную грамматику в нормальной форме без $$\varepsilon$$ -правил, порождающую язык$$\{a,b\}^* - (\{ a^n \mid n \geqslant 0 \} \cup \{ b^n \mid n \geqslant 0 \}) .$$
Определение 2.6.1.
Конечный автомат $$\langle Q , \Sigma , \Delta , I , F \rangle$$
называется детерминированным
(
I
содержит ровно один элемент;|x| = 1 ;Пример 2.6.2. Конечный автомат из примера 2.1.14 является детерминированным.
Определение 2.6.3. Детерминированный конечный автомат $$M = \langle Q , \Sigma , \Delta , I , F \rangle$$ называется полным (complete), если для каждого состояния $$p \in Q$$ и для каждого символа $$a \in \Sigma$$ найдется такое состояние $$q \in Q$$, что $$\langle p , a , q \rangle \in \Delta$$.
Пример 2.6.4.
Конечный автомат из примера 2.1.14
эквивалентен полному детерминированному конечному автомату $$\langle Q , \Sigma , \Delta , I , F \rangle$$,
где Q = {1,2,3}, $$\Sigma = \{ a , b \}$$, I = {1}, F = {1,2},$$\Delta = \{
\langle 1 , a , 2 \rangle ,\
\langle 1 , b , 3 \rangle ,\
\langle 2 , a , 3 \rangle ,\
\langle 2 , b , 1 \rangle ,\
\langle 3 , a , 3 \rangle ,\
\langle 3 , b , 3 \rangle
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F=]{1}
\ar @`{+/l16mm/} [] ^{}
\ar "1,2" <0.6mm> ^{a}
\ar "2,2" _{b}
*=[o][F=]{2}
\ar "1,1" <0.6mm> ^{b}
\ar "2,2" ^{a}
\\
%
*=[o][F-]{3}
\rloop{1,0} ^{a}
\rloop{0,-1} ^{b}
}$$
Замечание 2.6.5. Некоторые авторы используют в определении полного детерминированного конечного автомата вместо отношения $$\Delta$$ функцию $$\delta \colon Q \times \Sigma \to Q$$. От функции $$\delta$$ можно перейти к отношению $$\Delta$$, положив$$\Delta = \{ \langle p , a , \delta ( p , a ) \rangle \mid p \in Q , \; a \in \Sigma \} .$$
Упражнение 2.6.6. Является ли детерминированным следующий конечный автомат?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=1mm{ % *=[o][F-]{2} \ar "2,5" ^{b} \rloop{0,1} ^{a} \rloop{0,-1} _{b} \\ *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,3" ^{a} \ar "3,3" ^{b} *=[o][F=]{4} \\ % *=[o][F-]{3} \rloop{0,1} _{a} \rloop{0,-1} ^{b} \ar "2,5" ^{a} }$$
Упражнение 2.6.7. Является ли полным следующий детерминированный конечный автомат с алфавитом $$\Sigma = \{a,b,c\}$$?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \ar "1,2" ^{c} *=[o][F-]{2} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \ar "1,3" ^{c} *=[o][F=]{3} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \rloop{1,0} ^{c} }$$
Теорема 2.7.1 Каждый автоматный язык распознается некоторым полным детерминированным конечным автоматом.
Доказательство. Без ограничения общности можно предположить, что исходный язык задан конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$, содержащим только переходы с метками длины единица. Для любых $$a \in \Sigma$$ и $$H \subseteq Q$$ обозначим$$\Delta _ a ( H ) \rightleftharpoons \{ q \in Q \mid \langle p , a , q \rangle \in \Delta \mathspace\text{для некоторого}\mathspace p \in H \} .$$
Обозначим через $$\mathcal{P} ({ Q })$$
множество всех подмножеств множества Q.
Построим искомый полный детерминированный конечный автомат $$\langle Q' , \Sigma , \Delta' , I' , F' \rangle$$,
положив $$Q' = \mathcal{P} ({ Q })$$,$$\Delta' = \{ \langle H , a , \Delta _ a ( H ) \rangle \mid
H \subseteq Q ,\; a \in \Sigma \} ,$$
$$I' = {I}$$
и $$F' = \{ H \subseteq Q \mid H \cap F \neq \varnothing \}$$.
Пример 2.7.2. Пусть $$\Sigma = \{ a , b \}$$. Рассмотрим конечный автомат $$M = \langle \{ 1 , 2 , 3 \} , \Sigma , \Delta , \{ 1 \} , \{ 3 \} \rangle$$, где$$\Delta = \{ \langle 1 , a , 1 \rangle ,\ \langle 1 , b , 1 \rangle ,\ \langle 1 , a , 2 \rangle ,\ \langle 2 , b , 3 \rangle \} .$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a} \rloop{0,-1} ^{b} \ar "1,2" ^{a} *=[o][F-]{2} \ar "1,3" ^{b} *=[o][F=]{3} }$$ Если применить конструкцию из доказательства теоремы 2.7.1. и затем удалить состояния, не достижимые из начального состояния, то получится полный детерминированный конечный автомат$$M' = \langle \{ \{ 1 \} , \{ 1 , 2 \} , \{ 1 , 3 \} \} , \Sigma , \Delta' , \{ \{ 1 \} \} , \{ \{ 1 , 3 \} \} \rangle ,$$ где$$\begin{multiline*} \Delta' = \{ \langle \{ 1 \} , a , \{ 1 , 2 \} \rangle ,\ \langle \{ 1 \} , b , \{ 1 \} \rangle ,\ \langle \{ 1 , 2 \} , a , \{ 1 , 2 \} \rangle ,\ \\ \langle \{ 1 , 2 \} , b , \{ 1 , 3 \} \rangle ,\ \langle \{ 1 , 3 \} , a , \{ 1 , 2 \} \rangle ,\ \langle \{ 1 , 3 \} , b , \{ 1 \} \rangle \} . \end{multiline*}$$ $$\objectwidth={7.5mm} \objectheight={7.5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{b} \ar "1,2" ^{a} *=[o][F-]{1,2} \rloop{0,1} ^{a} \ar "2,2" <0.6mm> ^{b} \\ % *=[o][F=]{1,3} \ar "1,2" <0.6mm> ^{a} \ar "1,1" ^{b} }$$
Упражнение 2.7.3. Найти полный детерминированный конечный автомат, эквивалентный автомату, изображенному на диаграмме.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "2,1" ^{ab} \\ *=[o][F=]{2} \ar @`{+/l16mm/} [] ^{} \rloop{1,0} ^{a} }$$
Упражнение 2.7.4. Найти детерминированный конечный автомат для языка, порождаемого грамматикой$$\begin{align*} S \; {\to} \; a T , \\ S \; {\to} \; a R , \\ T \; {\to} \; b T , \\ T \; {\to} \; \varepsilon , \\ R \; {\to} \; a R , \\ R \; {\to} \; \varepsilon . \end{align*}$$
Упражнение 2.7.5. Найти детерминированный конечный автомат, распознающий язык $$\{ a u b \mid u \in \{a,b\}^* \} \cup \{ b u a \mid u \in \{a,b\}^* \} $$
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.