Подобно тому, как праволинейным грамматикам соответствуют
конечные автоматы,
Для наглядности стек обычно изображают вертикально,
так, что доступный элемент данных (вершина)
находится наверху.
Но при формальном определении конфигурации
(мгновенного состояния) МП-автомата
удобно считать все содержимое стека
конечной последовательностью символов,
то есть словом
(в алфавите, в котором перечислены все возможные
данные, "умещающиеся" в одной ячейке стека).
Прежде чем определить конфигурацию,
придется принять произвольное соглашение о том,
в каком порядке записывать содержимое стека в этом слове.
В этой книге считается, что вершина стека находится в начале
слова (то есть слева).
В разделе 10.1
даются необходимые определения.
В разделе 10.2 доказывается, что
МП-автоматы
распознают в точности
Определение 10.1.1. Автомат с магазинной памятью
( МП-автомат, магазинный автомат, стековый автомат,
pushdown Q - множество состояний, $$\Sigma$$ - входной алфавит, $$\Gamma$$ - алфавит магазинной памяти
(stack I
называются начальными состояниями,
элементы F - заключительными
или допускающими
состояниями.
Пример 10.1.2.
Пусть Q = {1,2}, $$\Sigma = \{ a , b \}$$, $$\Gamma = \{ A , B \}$$,$$\begin{align*}
\Delta = \{
\langle \langle 1 , a , \varepsilon \rangle ,
\langle 1 , A \rangle \rangle ,\
\langle \langle 1 , b , \varepsilon \rangle ,
\langle 1 , B \rangle \rangle ,\
\langle \langle 1 , \varepsilon , \varepsilon \rangle ,
\langle 2 , \varepsilon \rangle \rangle ,\
\\
\langle \langle 2 , a , A \rangle ,
\langle 2 , \varepsilon \rangle \rangle ,\
\langle \langle 2 , b , B \rangle ,
\langle 2 , \varepsilon \rangle \rangle
\} ,
\end{align*}$$
$$I = {1}$$, $$F = {2}$$.
Тогда $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$ -
МП-автомат.
Замечание 10.1.3.
МП-автоматы можно изображать в виде диаграмм состояний.
На диаграмме каждое состояние обозначается кружком,
а переход - стрелкой.
Каждое начальное состояние распознается
по ведущей в него короткой стрелке.
Каждое допускающее состояние отмечается на диаграмме
двойным кружком.
Стрелка с пометкой $$x , \beta : \gamma$$,
ведущая из p в q,
показывает, что $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp$$
является переходом данного МП-автомата.
Пример 10.1.4. Ниже приведена диаграмма МП-автомата из примера 10.1.2.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \rloop{0,-1} ^{b,\varepsilon:B} \ar "1,2" ^{\varepsilon,\varepsilon:\varepsilon} *=[o][F=]{2} \rloop{0,1} ^{a,A:\varepsilon} \rloop{0,-1} ^{b,B:\varepsilon} }$$
Определение 10.1.5. Конфигурацией МП-автомата называется любая тройка $$\lp q , w , \alpha \rp$$, где $$q \in Q$$, $$w \in \Sigma ^*$$, $$\alpha \in \Gamma ^*$$.
Определение 10.1.6. Определим на множестве всех конфигураций МП-автомата $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$ бинарное отношение $$\myunderset{ M }{\vdash}$$ ( такт работы ) следующим образом. Если $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta$$, $$w \in \Sigma ^*$$ и $$\alpha \in \Gamma ^*$$, то $$\lp p , xw , \beta \alpha \rp \myunderset{ M }{\vdash} \lp q , w , \gamma \alpha \rp$$.
Замечание 10.1.7 Обычно из контекста ясно, о каком МП-автомате идет речь. Тогда вместо $$\myunderset{ M }{\vdash}$$ будем писать $$\vdash$$.
Пример 10.1.8. Для МП-автомата из примера 10.1.2 выполняется $$\lp 1 , abba , \varepsilon \rp \vdash \lp 1 , bba , A \rp$$ и $$\lp 1 , abba , \varepsilon \rp \vdash \lp 2 , abba , \varepsilon \rp$$.
Определение 10.1.9.
Бинарное отношение $$\overstar{\vdash}$$
определяется как рефлексивное,
Пример 10.1.10. Для МП-автомата из примера 10.1.2 выполняется $$\lp 1 , abba , \varepsilon \rp \overstar{\vdash} \lp 1 , ba , BA \rp$$ и $$\lp 1 , abba , \varepsilon \rp \overstar{\vdash} \lp 2 , \varepsilon , \varepsilon \rp$$.
Лемма 10.1.11. Если $$\lp p , x , \alpha_1 \rp \overstar{\vdash} \lp q , \varepsilon , \alpha_2 \rp$$ и $$\lp q , y , \alpha_2 \alpha_3 \rp \mymathrel{\overstar{\vdash}} \lp r , \varepsilon , \alpha_4 \rp$$, то $$\lp p , xy , \alpha_1 \alpha_3 \rp \overstar{\vdash} \lp r , \varepsilon , \alpha_4 \rp$$.
Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации $$\lp p , x , \alpha_1 \rp$$ в конфигурацию $$\lp q , \varepsilon , \alpha_2 \rp$$.
Определение 10.1.12. Слово $$w \in \Sigma^*$$ допускается МП-автоматом $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, если найдутся такие состояния $$s \in I$$ и $$q \in F$$, что $$\lp s , w , \varepsilon \rp \overstar{\vdash} \lp q , \varepsilon , \varepsilon \rp$$.
Определение 10.1.13.
Язык, распознаваемый
МП-автоматом, -
множество всех слов, допускаемых этим МП-автоматом.
Язык, распознаваемый МП-автоматом M,
обозначается L(M).
Замечание 10.1.14. Обычно в учебниках используется более узкое определение МП-автомата, но это не меняет класса языков, распознаваемых МП-автоматами.
Пример 10.1.15. Пусть $$M$$ - МП-автомат из примера 10.1.2. Тогда $$L ( M ) = \{ u u \reverse \mid u \in \{ a , b \}^* \}$$.
Пример 10.1.16.
Пусть $$\Sigma = \{ a , b , c \}$$.
Рассмотрим МП-автомат $$M \peq
\lalg Q \sqzcm \Sigma \sqzcm \Gamma \sqzcm \Delta \sqzcm I \sqzcm F
\ralg$$,
где $$Q = \{ 1 , 2 , 3 , 4 , 5 \}$$, $$\Gamma = \{ A , B \}$$, I = {1}, F = {4,5}
и$$\begin{align*}
\Delta=\{
\lp\lp1,a,\emptyword\rp,
\lp1,A\rp\rp,\
\lp\lp1,b,\emptyword\rp,
\lp1,B\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp1,c,\emptyword\rp,
\lp2,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp2,a,A\rp,
\lp2,\emptyword\rp\rp,\
\lp\lp2,b,B\rp,
\lp2,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp2,a,B\rp,
\lp3,\emptyword\rp\rp,\
\lp\lp2,b,A\rp,
\lp3,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp2,\emptyword,A\rp,
\lp4,\emptyword\rp\rp,\
\lp\lp2,\emptyword,B\rp,
\lp4,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp2,b,\emptyword\rp,
\lp5,\emptyword\rp\rp,\
\lp\lp2,a,\emptyword\rp,
\lp5,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp3,a,\emptyword\rp,
\lp3,\emptyword\rp\rp,\
\lp\lp3,b,\emptyword\rp,
\lp3,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp3,\emptyword,\emptyword\rp,
\lp4,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp4,\emptyword,A\rp,
\lp4,\emptyword\rp\rp,\
\lp\lp4,\emptyword,B\rp,
\lp4,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp5,a,\emptyword\rp,
\lp5,\emptyword\rp\rp,\
\lp\lp5,b,\emptyword\rp,
\lp5,\emptyword\rp\rp
\}.
\end{align*}$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix @=11mm{
%
*=[o][F-]{3}
\rloop{0,1} ^{a,\varepsilon:\varepsilon}
\rloop{0,-1} ^{b,\varepsilon:\varepsilon}
\ar "2,5" ^-(.2){\varepsilon,\varepsilon:\varepsilon}
\\
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\rloop{0,1} ^{a,\varepsilon:A}
\rloop{0,-1} ^{b,\varepsilon:B}
\ar "2,2" ^{c,\varepsilon:\varepsilon}
*=[o][F-]{2}
\rloop{0,1} ^{a,A:\varepsilon}
\rloop{0,-1} ^{b,B:\varepsilon}
\ar "1,4" <0.6mm> ^{a,B:\varepsilon}
\ar "1,4" <-0.6mm> _{b,A:\varepsilon}
\ar "2,5" <0.6mm> ^{\varepsilon,A:\varepsilon}
\ar "2,5" <-0.6mm> _{\varepsilon,B:\varepsilon}
\ar "3,4" <0.6mm> ^{a,\varepsilon:\varepsilon}
\ar "3,4" <-0.6mm> _{b,\varepsilon:\varepsilon}
*=[o][F=]{4}
\rloop{0,1} ^{\varepsilon,A:\varepsilon}
\rloop{0,-1} ^{\varepsilon,B:\varepsilon}
\\
%
*=[o][F=]{5}
\rloop{0,1} ^{a,\varepsilon:\varepsilon}
\rloop{0,-1} ^{b,\varepsilon:\varepsilon}
}$$
Тогда $$L ( M ) = \{ u c v \mid
u \in \{ a , b \}^* ,\ v \in \{ a , b \}^* \commaand u \neq v \reverse
\}$$.
Определение 10.1.17. Два МП-автомата эквивалентны, если они распознают один и тот же язык.
Замечание 10.1.18.
В данном пособии не рассматриваются преобразователи с магазинной памятью
(pushdown
Замечание 10.1.19.
Некоторые авторы
изменяют определение допускаемых слов следующим образом:
слово w допускается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$,
если найдутся такие состояния $$s \in I$$
и $$q \in F$$
и последовательность $$\alpha \in \Gamma ^*$$,
что $$\lp s , w , \varepsilon \rp \overstar{\vdash}
\lp q , \varepsilon , \alpha \rp$$.
Такое определение
не изменяет класса языков, распознаваемых
МП-автоматами.
Замечание 10.1.20.
Некоторые авторы
добавляют в определение МП-автомата
седьмую компоненту - Z0, называемую маркером магазинной памяти
(start pushdown symbol),
и изменяют определение допускаемых слов следующим образом:
слово w допускается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , F , Z_0 \ralg$$,
если найдутся такие состояния $$s \in I$$
и $$q \in F$$,
что $$\lp s , w , Z_0 \rp \overstar{\vdash}
\lp q , \varepsilon , \varepsilon \rp$$.
Такое определение
не изменяет класса языков, распознаваемых МП-автоматами.
Замечание 10.1.21.
Класс языков, распознаваемых МП-автоматами,
не изменится также, если использовать следующую естественную комбинацию
двух предыдущих определений:
слово w допускается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , F , Z_0 \ralg$$,
если найдутся такие состояния $$s \in I$$
и $$q \in F$$
и последовательность $$\alpha \in \Gamma ^*$$,
что $$\lp s , w , Z_0 \rp \overstar{\vdash}
\lp q , \varepsilon , \alpha \rp$$.
Замечание 10.1.22.
Некоторые авторы
добавляют в определение МП-автомата
маркер магазинной памяти Z0,
отбрасывают множество F
и изменяют определение допускаемых слов следующим образом:
слово w допускается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , Z_0 \ralg$$,
если
найдутся такие состояния $$s \in I$$
и $$q \in Q$$,
что $$\lp s , w , Z_0 \rp \overstar{\vdash}
\lp q , \varepsilon , \varepsilon \rp$$.
Это также не изменяет класса языков, распознаваемых
МП-автоматами.
Упражнение 10.1.23. Найти МП-автомат, распознающий язык $$\{ a^n b^n \mid n \geq 0 \}$$
Упражнение 10.1.24. Найти МП-автомат, распознающий язык $$\{ a^i b^j c^k \mid i = j \rusor j = k \}$$
Упражнение 10.1.25. Найти МП-автомат, распознающий язык $$\{ w \in \{a,b\}^* \mid | w |_a = | w |_b \}$$
Теорема 10.2.1. Если язык L является контекстно-свободным,
то существует МП-автомат, распознающий этот язык.
Доказательство.
Пусть язык L порождается
Пример 10.2.2. Пусть $$\Sigma = \{ a , b , c , d \}$$. Контекстно-свободная грамматика$$\begin{align*} S \; {\to} \; SS , \\ S \; {\to} \; a , \\ S \; {\to} \; bcTS , \\ T \; {\to} \; cSS , \\ T \; {\to} \; dTT \end{align*}$$ и МП-автомат $$\lalg \{ 1 , 2 \} , \Sigma , \{ S , T \} , \Delta , \{ 1 \} , \{ 2 \} \ralg$$, где$$\begin{multiline*} \Delta = \{ \lp \lp 1 , \varepsilon , \varepsilon \rp , \lp 2 , S \rp \rp ,\ \lp \lp 2 , \varepsilon , S \rp , \lp 2 , SS \rp \rp ,\ \lp \lp 2 , a , S \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \lp \lp 2 , bc , S \rp , \lp 2 , TS \rp \rp ,\ \lp \lp 2 , c , T \rp , \lp 2 , SS \rp \rp ,\ \lp \lp 2 , d , T \rp , \lp 2 , TT \rp \rp \} , \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,3" ^{\varepsilon,\varepsilon:S} *=[o][F=]{2} \rloop{-1,1} ^*!/r4mm/{\varepsilon,S:SS} \rloop{3,7} ^{a,S:\varepsilon} \rloop{1,0} ^{bc,S:TS} \rloop{3,-7} ^{c,T:SS} \rloop{-1,-1} ^*!/r4mm/{d,T:TT} }$$ задают один и тот же язык.
Лемма 10.2.3. Каждый МП-автомат эквивалентен некоторому МП-автомату $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где |I| = 1, |F| = 1 и каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет требованиям $$| x | \leq 1$$ и $$| \beta | + | \gamma | = 1$$.
Пример 10.2.4. Рассмотрим МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где $$Q \peq I \peq F \peq \{ 1 \}$$, $$\Sigma \peq \{ a , b , c , d \}$$, $$\Gamma \peq \{ A , B \}$$,$$\begin{multiline*} \Delta \peq \{ \lp \lp 1 , a , A \rp , \lp 1 , \varepsilon \rp \rp ,\ \lp \lp 1 , b , B \rp , \lp 1 , \varepsilon \rp \rp ,\ \\ \lp \lp 1 , c , \varepsilon \rp , \lp 1 , A \rp \rp ,\ \lp \lp 1 , d , A \rp , \lp 1 , AB \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{-1,-1} ^*!/r3mm/{a,A:\varepsilon} \rloop{-1,1} ^*!/r3mm/{b,B:\varepsilon} \rloop{1,1} ^*!/l3mm/{c,\varepsilon:A} \rloop{1,-1} ^*!/l3mm/{d,A:AB} }$$ Он эквивалентен МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma , \Delta' , I , F \ralg$$, где $$Q' \peq \{ 1 , 2 , 3 \}$$ и$$\begin{multiline*} \Delta' = \{ \lp \lp 1 , a , A \rp , \lp 1 , \varepsilon \rp \rp ,\ \lp \lp 1 , b , B \rp , \lp 1 , \varepsilon \rp \rp ,\ \lp \lp 1 , c , \varepsilon \rp , \lp 1 , A \rp \rp ,\ \\ \lp \lp 1 , d , A \rp , \lp 2 , \varepsilon \rp \rp ,\ \lp \lp 2 , \varepsilon , \varepsilon \rp , \lp 3 , B \rp \rp ,\ \lp \lp 3 , \varepsilon , \varepsilon \rp , \lp 1 , A \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{-1,-1} ^*!/r3mm/{a,A:\varepsilon} \rloop{-1,1} ^*!/r3mm/{b,B:\varepsilon} \rloop{1,1} ^*!/l3mm/{c,\varepsilon:A} \ar "1,3" ^{d,A:\varepsilon} *=[o][F-]{2} \ar "2,2" ^{\varepsilon,\varepsilon:B} \\ % *=[o][F-]{3} \ar "1,1" ^{\varepsilon,\varepsilon:A} }$$
Пример 10.2.5. Рассмотрим МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где $$Q \peq I \peq F \peq \{ 1 \}$$, $$\Sigma \peq \{ a , b , c \}$$, $$\Gamma \peq \{ A \}$$,$$\Delta \peq \{ \lp \lp 1 , a , \varepsilon \rp , \lp 1 , A \rp \rp ,\ \lp \lp 1 , b , A \rp , \lp 1 , \varepsilon \rp \rp ,\ \lp \lp 1 , c , \varepsilon \rp , \lp 1 , \varepsilon \rp \rp \} .$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \rloop{1,0} ^{b,A:\varepsilon} \rloop{0,-1} ^{c,\varepsilon:\varepsilon} }$$ Он эквивалентен МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I , F \ralg$$, где $$Q' \peq \{ 1 , 2 \}$$, $$\Gamma' \peq \{ A , T \}$$ и$$\begin{multiline*} \Delta' \peq \{ \lp \lp 1 , a , \varepsilon \rp , \lp 1 , A \rp \rp ,\ \lp \lp 1 , b , A \rp , \lp 1 , \varepsilon \rp \rp ,\ \\ \lp \lp 1 , c , \varepsilon \rp , \lp 2 , T \rp \rp ,\ \lp \lp 2 , \varepsilon , T \rp , \lp 1 , \varepsilon \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \rloop{1,0} ^{b,A:\varepsilon} \ar "2,1" <0.6mm> ^{c,\varepsilon:T} \\ *=[o][F-]{2} \ar "1,1" <0.6mm> ^{\varepsilon,T:\varepsilon} }$$
Пример 10.2.6. Рассмотрим МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где $$Q \peq I \peq F \peq \{ 1 , 2 \}$$, $$\Sigma \peq \{ a , b \}$$, $$\Gamma \peq \{ C \}$$,$$\begin{multiline*} \Delta \peq \{ \lp \lp 1 , a , \varepsilon \rp , \lp 1 , C \rp \rp ,\ \lp \lp 1 , b , C \rp , \lp 1 , \varepsilon \rp \rp ,\ \\ \lp \lp 2 , b , \varepsilon \rp , \lp 2 , C \rp \rp ,\ \lp \lp 2 , a , C \rp , \lp 2 , \varepsilon \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:C} \rloop{0,-1} ^{b,C:\varepsilon} \\ % *=[o][F=]{2} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:C} \rloop{0,-1} ^{a,C:\varepsilon} }$$ Он эквивалентен МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg$$, где $$Q' \peq \{ 0 , 1 , 2 , 3 \}$$, $$\Gamma' \peq \{ A , T \}$$, $$I' \peq \{ 0 \}$$, $$F' \peq \{ 3 \}$$,$$\begin{multiline*} \Delta' \peq \Delta \cup \{ \lp \lp 0 , \varepsilon , \varepsilon \rp , \lp 1 , T \rp \rp ,\ \lp \lp 0 , \varepsilon , \varepsilon \rp , \lp 2 , T \rp \rp ,\ \\ \lp \lp 1 , \varepsilon , T \rp , \lp 3 , \varepsilon \rp \rp ,\ \lp \lp 2 , \varepsilon , T \rp , \lp 3 , \varepsilon \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { % *=[o][F-]{1} \rloop{0,1} ^{a,\varepsilon:C} \rloop{0,-1} ^{b,C:\varepsilon} \ar "1,4" ^{\varepsilon,T:\varepsilon} *=[o][F=]{3} \\ *=[o][F-]{0} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{\varepsilon,\varepsilon:T} \ar "2,3" _{\varepsilon,\varepsilon:T} *=[o][F-]{2} \rloop{0,1} ^{a,\varepsilon:C} \rloop{0,-1} ^{a,C:\varepsilon} \ar "1,4" _{\varepsilon,T:\varepsilon} }$$
Теорема 10.2.7. Если
язык L распознается
некоторым МП-автоматом,
то L является контекстно-свободным.
Доказательство.
Пусть язык L распознается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$.
Без ограничения общности можно считать,
что $$I = \{ \qinitial \}$$, $$F = \{ \qaccept \}$$
и каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$
удовлетворяет требованию $$| \beta | + | \gamma | = 1$$.
Построим искомую
Пример 10.2.8.
МП-автомат $$M =
\lalg \{ 1 , 2 \} , \Sigma , \Gamma , \Delta ,
\{ 1 \} , \{ 2 \} \ralg$$,
где $$\Sigma = \{ a , b \}$$, $$\Gamma = \{ D , E \}$$,$$\begin{multiline*}
\Delta = \{
\lp \lp 1 , ab , \varepsilon \rp ,
\lp 1 , E \rp \rp ,\
\lp \lp 1 , aa , E \rp ,
\lp 1 , \varepsilon \rp \rp ,\
\lp \lp 1 , b , \varepsilon \rp ,
\lp 2 , D \rp \rp ,\
\\
\lp \lp 2 , a , \varepsilon \rp ,
\lp 1 , D \rp \rp ,\
\lp \lp 2 , \varepsilon , D \rp ,
\lp 2 , \varepsilon \rp \rp ,\
\lp \lp 2 , b , E \rp ,
\lp 2 , \varepsilon \rp \rp
\} ,
\end{multiline*}$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix @=11mm{
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\rloop{0,1} ^{ab,\varepsilon:E}
\rloop{0,-1} ^{aa,E:\varepsilon}
\ar "1,2" <0.6mm> ^{b,\varepsilon:D}
*=[o][F=]{2}
\ar "1,1" <0.6mm> ^{a,\varepsilon:D}
\rloop{0,1} ^{\varepsilon,D:\varepsilon}
\rloop{0,-1} ^{b,E:\varepsilon}
}$$
и контекстно-свободная грамматика$$\begin{align*}
S \; {\to} \; abTaaS , T \; {\to} \; abTaaT , \\
S \; {\to} \; abSbU , T \; {\to} \; \varepsilon , \\
S \; {\to} \; bUU , U \; {\to} \; aSU , \\
U \; {\to} \; \varepsilon
\end{align*}$$
задают один и тот же язык.
Здесь S, T и U
соответствуют символам A1,2, A1,1
и A2,2
из доказательства теоремы 10.2.7.
Упражнение 10.2.9. Найти МП-автомат, распознающий язык, порождаемый грамматикой$$\begin{align*} F \; {\to} \; a F b , \\ F \; {\to} \; a F a , \\ F \; {\to} \; a . \end{align*}$$
Упражнение 10.2.10. Найти
Упражнение 10.2.10. Найти
Упражнение 10.2.10. Найти
Теорема 10.3.1. Каждый МП-автомат эквивалентен некоторому МП-автомату $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где |Q| = 2 и каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет требованиям |x| = 1, $$| \beta | \leq 1$$
и $$| \gamma | \leq 2$$.
Доказательство.
Пусть исходным МП-автоматом распознается
контекстно-свободный
язык $$L \subseteq \Sigma ^*$$.
Согласно теореме 8.4.6
язык $$L \sminus \{ \varepsilon \}$$
порождается некоторой
Q = {1,2}, I = {1},$$\begin{gathered*}
F =
\begin{cases}
\{ 1 , 2 \}, \; \text{если}\; \varepsilon \in L ,\\
\{ 2 \}, \; \text{если}\; \varepsilon \notin L ,
\end{cases}
\\
\Delta =
\{ \langle \langle 2 , a ,\! A \rangle ,\! \langle 2 ,\! \gamma \rangle \rangle
\mid
( A \to a \gamma ) \in P \}
\cup
\{ \langle \langle 1 , a ,\! \varepsilon \rangle ,\!
\langle 2 ,\! \gamma \rangle \rangle
\mid
( S \to a \gamma ) \in P \} .
\end{gathered*}$$
Теорема 10.3.2. Каждый МП-автомат эквивалентен некоторому МП-автомату $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, в котором каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет требованиям |x| = 1, $$| \beta | \leq 1$$ и $$| \gamma | \leq 1$$.
Доказательство.
Пусть исходным МП-автоматом распознается
контекстно-вободный язык $$L \subseteq \Sigma ^*$$.
Согласно теореме 8.4.6
язык $$L \sminus \{ \varepsilon \}$$
порождается некоторой
контекстно-вободной грамматикой $$G = \lalg N , \Sigma , P , S \ralg$$,
в которой
каждое правило имеет один из следующих трех видов: $$A \tto a$$, $$A \tto a B$$, $$A \tto a B C$$,
где $$A \in N$$, $$B \in N$$, $$C \in N$$, $$a \in \Sigma$$.
Легко добиться того, чтобы
в правилах грамматики G
вспомогательные символы в правой части
(то есть символы B и C )
были отличны от начального символа S.
Положим $$Q = N \cup \{ \bot \}$$, где $$\bot \notin N$$. Далее, положим $$\Gamma = N$$,$$I = \{ S \} ,\qquad F = \begin{cases} \{ S , \bot \}, \mathspace\text{если}\mathspace \varepsilon \in L ,\\ \{ \bot \}, \mathspace\text{если}\mathspace \varepsilon \notin L , \end{cases}$$ $$\begin{align*} \Delta = \{ \lp \lp A , a , \varepsilon \rp , \lp B , C \rp \rp \mid ( A \tto a B C ) \in P \} \cup {} \\ \myqquad \cup \{ \lp \lp A , a , \varepsilon \rp , \lp B , \varepsilon \rp \rp \mid ( A \tto a B ) \in P \} \cup {} \\ \myqquad \cup \{ \lp \lp A , a , D \rp , \lp D , \varepsilon \rp \rp \mid ( A \tto a ) \in P \commaand D \in N \sminus \{ S \} \} \cup {} \\ \myqquad \cup \{ \lp \lp A , a , \varepsilon \rp , \lp \bot , \varepsilon \rp \rp \mid ( A \tto a ) \in P \} . \end{align*}$$
Упражнение 10.3.3. Найти для языка, порождаемого грамматикой$$\begin{align*}
S \; {\to} \; a T T , \\
S \; {\to} \; \varepsilon , \\
T \; {\to} \; b T U , \\
T \; {\to} \; c , \\
U \; {\to} \; a T ,
\end{align*}$$
МП-автомат,
в котором
каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$
удовлетворяет требованиям |x| = 1, $$| \beta | \leq 1$$
и $$| \gamma | \leq 1$$.
Упражнение 10.3.4. Найти для языка, порождаемого грамматикой$$\begin{align*} S \; {\to} \; a T U , \\ T \; {\to} \; a U T , \\ T \; {\to} \; b , \\ U \; {\to} \; b T , \\ U \; {\to} \; a , \end{align*}$$ МП-автомат, в котором каждый переход $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет требованиям $$| x | = 1$$, $$| \beta | \leq 1$$ и $$| \gamma | \leq 1$$.
Подобно тому, как праволинейным грамматикам соответствуют
конечные автоматы,
Для наглядности стек обычно изображают вертикально,
так, что доступный элемент данных (вершина)
находится наверху.
Но при формальном определении конфигурации
(мгновенного состояния) МП-автомата
удобно считать все содержимое стека
конечной последовательностью символов,
то есть словом
(в алфавите, в котором перечислены все возможные
данные, "умещающиеся" в одной ячейке стека).
Прежде чем определить конфигурацию,
придется принять произвольное соглашение о том,
в каком порядке записывать содержимое стека в этом слове.
В этой книге считается, что вершина стека находится в начале
слова (то есть слева).
В разделе 10.1
даются необходимые определения.
В разделе 10.2 доказывается, что
МП-автоматы
распознают в точности
Определение 10.1.1. Автомат с магазинной памятью
( МП-автомат, магазинный автомат, стековый автомат,
pushdown Q - множество состояний, $$\Sigma$$ - входной алфавит, $$\Gamma$$ - алфавит магазинной памяти
(stack I
называются начальными состояниями,
элементы F - заключительными
или допускающими
состояниями.
Пример 10.1.2.
Пусть Q = {1,2}, $$\Sigma = \{ a , b \}$$, $$\Gamma = \{ A , B \}$$,$$\begin{align*}
\Delta = \{
\langle \langle 1 , a , \varepsilon \rangle ,
\langle 1 , A \rangle \rangle ,\
\langle \langle 1 , b , \varepsilon \rangle ,
\langle 1 , B \rangle \rangle ,\
\langle \langle 1 , \varepsilon , \varepsilon \rangle ,
\langle 2 , \varepsilon \rangle \rangle ,\
\\
\langle \langle 2 , a , A \rangle ,
\langle 2 , \varepsilon \rangle \rangle ,\
\langle \langle 2 , b , B \rangle ,
\langle 2 , \varepsilon \rangle \rangle
\} ,
\end{align*}$$
$$I = {1}$$, $$F = {2}$$.
Тогда $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$ -
МП-автомат.
Замечание 10.1.3.
МП-автоматы можно изображать в виде диаграмм состояний.
На диаграмме каждое состояние обозначается кружком,
а переход - стрелкой.
Каждое начальное состояние распознается
по ведущей в него короткой стрелке.
Каждое допускающее состояние отмечается на диаграмме
двойным кружком.
Стрелка с пометкой $$x , \beta : \gamma$$,
ведущая из p в q,
показывает, что $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp$$
является переходом данного МП-автомата.
Пример 10.1.4. Ниже приведена диаграмма МП-автомата из примера 10.1.2.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \rloop{0,-1} ^{b,\varepsilon:B} \ar "1,2" ^{\varepsilon,\varepsilon:\varepsilon} *=[o][F=]{2} \rloop{0,1} ^{a,A:\varepsilon} \rloop{0,-1} ^{b,B:\varepsilon} }$$
Определение 10.1.5. Конфигурацией МП-автомата называется любая тройка $$\lp q , w , \alpha \rp$$, где $$q \in Q$$, $$w \in \Sigma ^*$$, $$\alpha \in \Gamma ^*$$.
Определение 10.1.6. Определим на множестве всех конфигураций МП-автомата $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$ бинарное отношение $$\myunderset{ M }{\vdash}$$ ( такт работы ) следующим образом. Если $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta$$, $$w \in \Sigma ^*$$ и $$\alpha \in \Gamma ^*$$, то $$\lp p , xw , \beta \alpha \rp \myunderset{ M }{\vdash} \lp q , w , \gamma \alpha \rp$$.
Замечание 10.1.7 Обычно из контекста ясно, о каком МП-автомате идет речь. Тогда вместо $$\myunderset{ M }{\vdash}$$ будем писать $$\vdash$$.
Пример 10.1.8. Для МП-автомата из примера 10.1.2 выполняется $$\lp 1 , abba , \varepsilon \rp \vdash \lp 1 , bba , A \rp$$ и $$\lp 1 , abba , \varepsilon \rp \vdash \lp 2 , abba , \varepsilon \rp$$.
Определение 10.1.9.
Бинарное отношение $$\overstar{\vdash}$$
определяется как рефлексивное,
Пример 10.1.10. Для МП-автомата из примера 10.1.2 выполняется $$\lp 1 , abba , \varepsilon \rp \overstar{\vdash} \lp 1 , ba , BA \rp$$ и $$\lp 1 , abba , \varepsilon \rp \overstar{\vdash} \lp 2 , \varepsilon , \varepsilon \rp$$.
Лемма 10.1.11. Если $$\lp p , x , \alpha_1 \rp \overstar{\vdash} \lp q , \varepsilon , \alpha_2 \rp$$ и $$\lp q , y , \alpha_2 \alpha_3 \rp \mymathrel{\overstar{\vdash}} \lp r , \varepsilon , \alpha_4 \rp$$, то $$\lp p , xy , \alpha_1 \alpha_3 \rp \overstar{\vdash} \lp r , \varepsilon , \alpha_4 \rp$$.
Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации $$\lp p , x , \alpha_1 \rp$$ в конфигурацию $$\lp q , \varepsilon , \alpha_2 \rp$$.
Определение 10.1.12. Слово $$w \in \Sigma^*$$ допускается МП-автоматом $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, если найдутся такие состояния $$s \in I$$ и $$q \in F$$, что $$\lp s , w , \varepsilon \rp \overstar{\vdash} \lp q , \varepsilon , \varepsilon \rp$$.
Определение 10.1.13.
Язык, распознаваемый
МП-автоматом, -
множество всех слов, допускаемых этим МП-автоматом.
Язык, распознаваемый МП-автоматом M,
обозначается L(M).
Замечание 10.1.14. Обычно в учебниках используется более узкое определение МП-автомата, но это не меняет класса языков, распознаваемых МП-автоматами.
Пример 10.1.15. Пусть $$M$$ - МП-автомат из примера 10.1.2. Тогда $$L ( M ) = \{ u u \reverse \mid u \in \{ a , b \}^* \}$$.
Пример 10.1.16.
Пусть $$\Sigma = \{ a , b , c \}$$.
Рассмотрим МП-автомат $$M \peq
\lalg Q \sqzcm \Sigma \sqzcm \Gamma \sqzcm \Delta \sqzcm I \sqzcm F
\ralg$$,
где $$Q = \{ 1 , 2 , 3 , 4 , 5 \}$$, $$\Gamma = \{ A , B \}$$, I = {1}, F = {4,5}
и$$\begin{align*}
\Delta=\{
\lp\lp1,a,\emptyword\rp,
\lp1,A\rp\rp,\
\lp\lp1,b,\emptyword\rp,
\lp1,B\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp1,c,\emptyword\rp,
\lp2,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp2,a,A\rp,
\lp2,\emptyword\rp\rp,\
\lp\lp2,b,B\rp,
\lp2,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp2,a,B\rp,
\lp3,\emptyword\rp\rp,\
\lp\lp2,b,A\rp,
\lp3,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp2,\emptyword,A\rp,
\lp4,\emptyword\rp\rp,\
\lp\lp2,\emptyword,B\rp,
\lp4,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp2,b,\emptyword\rp,
\lp5,\emptyword\rp\rp,\
\lp\lp2,a,\emptyword\rp,
\lp5,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp3,a,\emptyword\rp,
\lp3,\emptyword\rp\rp,\
\lp\lp3,b,\emptyword\rp,
\lp3,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp3,\emptyword,\emptyword\rp,
\lp4,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp4,\emptyword,A\rp,
\lp4,\emptyword\rp\rp,\
\lp\lp4,\emptyword,B\rp,
\lp4,\emptyword\rp\rp,\
\\\hphantom{{}={}\{}
\lp\lp5,a,\emptyword\rp,
\lp5,\emptyword\rp\rp,\
\lp\lp5,b,\emptyword\rp,
\lp5,\emptyword\rp\rp
\}.
\end{align*}$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix @=11mm{
%
*=[o][F-]{3}
\rloop{0,1} ^{a,\varepsilon:\varepsilon}
\rloop{0,-1} ^{b,\varepsilon:\varepsilon}
\ar "2,5" ^-(.2){\varepsilon,\varepsilon:\varepsilon}
\\
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\rloop{0,1} ^{a,\varepsilon:A}
\rloop{0,-1} ^{b,\varepsilon:B}
\ar "2,2" ^{c,\varepsilon:\varepsilon}
*=[o][F-]{2}
\rloop{0,1} ^{a,A:\varepsilon}
\rloop{0,-1} ^{b,B:\varepsilon}
\ar "1,4" <0.6mm> ^{a,B:\varepsilon}
\ar "1,4" <-0.6mm> _{b,A:\varepsilon}
\ar "2,5" <0.6mm> ^{\varepsilon,A:\varepsilon}
\ar "2,5" <-0.6mm> _{\varepsilon,B:\varepsilon}
\ar "3,4" <0.6mm> ^{a,\varepsilon:\varepsilon}
\ar "3,4" <-0.6mm> _{b,\varepsilon:\varepsilon}
*=[o][F=]{4}
\rloop{0,1} ^{\varepsilon,A:\varepsilon}
\rloop{0,-1} ^{\varepsilon,B:\varepsilon}
\\
%
*=[o][F=]{5}
\rloop{0,1} ^{a,\varepsilon:\varepsilon}
\rloop{0,-1} ^{b,\varepsilon:\varepsilon}
}$$
Тогда $$L ( M ) = \{ u c v \mid
u \in \{ a , b \}^* ,\ v \in \{ a , b \}^* \commaand u \neq v \reverse
\}$$.
Определение 10.1.17. Два МП-автомата эквивалентны, если они распознают один и тот же язык.
Замечание 10.1.18.
В данном пособии не рассматриваются преобразователи с магазинной памятью
(pushdown
Замечание 10.1.19.
Некоторые авторы
изменяют определение допускаемых слов следующим образом:
слово w допускается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$,
если найдутся такие состояния $$s \in I$$
и $$q \in F$$
и последовательность $$\alpha \in \Gamma ^*$$,
что $$\lp s , w , \varepsilon \rp \overstar{\vdash}
\lp q , \varepsilon , \alpha \rp$$.
Такое определение
не изменяет класса языков, распознаваемых
МП-автоматами.
Замечание 10.1.20.
Некоторые авторы
добавляют в определение МП-автомата
седьмую компоненту - Z0, называемую маркером магазинной памяти
(start pushdown symbol),
и изменяют определение допускаемых слов следующим образом:
слово w допускается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , F , Z_0 \ralg$$,
если найдутся такие состояния $$s \in I$$
и $$q \in F$$,
что $$\lp s , w , Z_0 \rp \overstar{\vdash}
\lp q , \varepsilon , \varepsilon \rp$$.
Такое определение
не изменяет класса языков, распознаваемых МП-автоматами.
Замечание 10.1.21.
Класс языков, распознаваемых МП-автоматами,
не изменится также, если использовать следующую естественную комбинацию
двух предыдущих определений:
слово w допускается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , F , Z_0 \ralg$$,
если найдутся такие состояния $$s \in I$$
и $$q \in F$$
и последовательность $$\alpha \in \Gamma ^*$$,
что $$\lp s , w , Z_0 \rp \overstar{\vdash}
\lp q , \varepsilon , \alpha \rp$$.
Замечание 10.1.22.
Некоторые авторы
добавляют в определение МП-автомата
маркер магазинной памяти Z0,
отбрасывают множество F
и изменяют определение допускаемых слов следующим образом:
слово w допускается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , Z_0 \ralg$$,
если
найдутся такие состояния $$s \in I$$
и $$q \in Q$$,
что $$\lp s , w , Z_0 \rp \overstar{\vdash}
\lp q , \varepsilon , \varepsilon \rp$$.
Это также не изменяет класса языков, распознаваемых
МП-автоматами.
Упражнение 10.1.23. Найти МП-автомат, распознающий язык $$\{ a^n b^n \mid n \geq 0 \}$$
Упражнение 10.1.24. Найти МП-автомат, распознающий язык $$\{ a^i b^j c^k \mid i = j \rusor j = k \}$$
Упражнение 10.1.25. Найти МП-автомат, распознающий язык $$\{ w \in \{a,b\}^* \mid | w |_a = | w |_b \}$$
Теорема 10.2.1. Если язык L является контекстно-свободным,
то существует МП-автомат, распознающий этот язык.
Доказательство.
Пусть язык L порождается
Пример 10.2.2. Пусть $$\Sigma = \{ a , b , c , d \}$$. Контекстно-свободная грамматика$$\begin{align*} S \; {\to} \; SS , \\ S \; {\to} \; a , \\ S \; {\to} \; bcTS , \\ T \; {\to} \; cSS , \\ T \; {\to} \; dTT \end{align*}$$ и МП-автомат $$\lalg \{ 1 , 2 \} , \Sigma , \{ S , T \} , \Delta , \{ 1 \} , \{ 2 \} \ralg$$, где$$\begin{multiline*} \Delta = \{ \lp \lp 1 , \varepsilon , \varepsilon \rp , \lp 2 , S \rp \rp ,\ \lp \lp 2 , \varepsilon , S \rp , \lp 2 , SS \rp \rp ,\ \lp \lp 2 , a , S \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \lp \lp 2 , bc , S \rp , \lp 2 , TS \rp \rp ,\ \lp \lp 2 , c , T \rp , \lp 2 , SS \rp \rp ,\ \lp \lp 2 , d , T \rp , \lp 2 , TT \rp \rp \} , \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,3" ^{\varepsilon,\varepsilon:S} *=[o][F=]{2} \rloop{-1,1} ^*!/r4mm/{\varepsilon,S:SS} \rloop{3,7} ^{a,S:\varepsilon} \rloop{1,0} ^{bc,S:TS} \rloop{3,-7} ^{c,T:SS} \rloop{-1,-1} ^*!/r4mm/{d,T:TT} }$$ задают один и тот же язык.
Лемма 10.2.3. Каждый МП-автомат эквивалентен некоторому МП-автомату $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где |I| = 1, |F| = 1 и каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет требованиям $$| x | \leq 1$$ и $$| \beta | + | \gamma | = 1$$.
Пример 10.2.4. Рассмотрим МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где $$Q \peq I \peq F \peq \{ 1 \}$$, $$\Sigma \peq \{ a , b , c , d \}$$, $$\Gamma \peq \{ A , B \}$$,$$\begin{multiline*} \Delta \peq \{ \lp \lp 1 , a , A \rp , \lp 1 , \varepsilon \rp \rp ,\ \lp \lp 1 , b , B \rp , \lp 1 , \varepsilon \rp \rp ,\ \\ \lp \lp 1 , c , \varepsilon \rp , \lp 1 , A \rp \rp ,\ \lp \lp 1 , d , A \rp , \lp 1 , AB \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{-1,-1} ^*!/r3mm/{a,A:\varepsilon} \rloop{-1,1} ^*!/r3mm/{b,B:\varepsilon} \rloop{1,1} ^*!/l3mm/{c,\varepsilon:A} \rloop{1,-1} ^*!/l3mm/{d,A:AB} }$$ Он эквивалентен МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma , \Delta' , I , F \ralg$$, где $$Q' \peq \{ 1 , 2 , 3 \}$$ и$$\begin{multiline*} \Delta' = \{ \lp \lp 1 , a , A \rp , \lp 1 , \varepsilon \rp \rp ,\ \lp \lp 1 , b , B \rp , \lp 1 , \varepsilon \rp \rp ,\ \lp \lp 1 , c , \varepsilon \rp , \lp 1 , A \rp \rp ,\ \\ \lp \lp 1 , d , A \rp , \lp 2 , \varepsilon \rp \rp ,\ \lp \lp 2 , \varepsilon , \varepsilon \rp , \lp 3 , B \rp \rp ,\ \lp \lp 3 , \varepsilon , \varepsilon \rp , \lp 1 , A \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{-1,-1} ^*!/r3mm/{a,A:\varepsilon} \rloop{-1,1} ^*!/r3mm/{b,B:\varepsilon} \rloop{1,1} ^*!/l3mm/{c,\varepsilon:A} \ar "1,3" ^{d,A:\varepsilon} *=[o][F-]{2} \ar "2,2" ^{\varepsilon,\varepsilon:B} \\ % *=[o][F-]{3} \ar "1,1" ^{\varepsilon,\varepsilon:A} }$$
Пример 10.2.5. Рассмотрим МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где $$Q \peq I \peq F \peq \{ 1 \}$$, $$\Sigma \peq \{ a , b , c \}$$, $$\Gamma \peq \{ A \}$$,$$\Delta \peq \{ \lp \lp 1 , a , \varepsilon \rp , \lp 1 , A \rp \rp ,\ \lp \lp 1 , b , A \rp , \lp 1 , \varepsilon \rp \rp ,\ \lp \lp 1 , c , \varepsilon \rp , \lp 1 , \varepsilon \rp \rp \} .$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \rloop{1,0} ^{b,A:\varepsilon} \rloop{0,-1} ^{c,\varepsilon:\varepsilon} }$$ Он эквивалентен МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I , F \ralg$$, где $$Q' \peq \{ 1 , 2 \}$$, $$\Gamma' \peq \{ A , T \}$$ и$$\begin{multiline*} \Delta' \peq \{ \lp \lp 1 , a , \varepsilon \rp , \lp 1 , A \rp \rp ,\ \lp \lp 1 , b , A \rp , \lp 1 , \varepsilon \rp \rp ,\ \\ \lp \lp 1 , c , \varepsilon \rp , \lp 2 , T \rp \rp ,\ \lp \lp 2 , \varepsilon , T \rp , \lp 1 , \varepsilon \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \rloop{1,0} ^{b,A:\varepsilon} \ar "2,1" <0.6mm> ^{c,\varepsilon:T} \\ *=[o][F-]{2} \ar "1,1" <0.6mm> ^{\varepsilon,T:\varepsilon} }$$
Пример 10.2.6. Рассмотрим МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где $$Q \peq I \peq F \peq \{ 1 , 2 \}$$, $$\Sigma \peq \{ a , b \}$$, $$\Gamma \peq \{ C \}$$,$$\begin{multiline*} \Delta \peq \{ \lp \lp 1 , a , \varepsilon \rp , \lp 1 , C \rp \rp ,\ \lp \lp 1 , b , C \rp , \lp 1 , \varepsilon \rp \rp ,\ \\ \lp \lp 2 , b , \varepsilon \rp , \lp 2 , C \rp \rp ,\ \lp \lp 2 , a , C \rp , \lp 2 , \varepsilon \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:C} \rloop{0,-1} ^{b,C:\varepsilon} \\ % *=[o][F=]{2} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:C} \rloop{0,-1} ^{a,C:\varepsilon} }$$ Он эквивалентен МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg$$, где $$Q' \peq \{ 0 , 1 , 2 , 3 \}$$, $$\Gamma' \peq \{ A , T \}$$, $$I' \peq \{ 0 \}$$, $$F' \peq \{ 3 \}$$,$$\begin{multiline*} \Delta' \peq \Delta \cup \{ \lp \lp 0 , \varepsilon , \varepsilon \rp , \lp 1 , T \rp \rp ,\ \lp \lp 0 , \varepsilon , \varepsilon \rp , \lp 2 , T \rp \rp ,\ \\ \lp \lp 1 , \varepsilon , T \rp , \lp 3 , \varepsilon \rp \rp ,\ \lp \lp 2 , \varepsilon , T \rp , \lp 3 , \varepsilon \rp \rp \} . \end{multiline*}$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { % *=[o][F-]{1} \rloop{0,1} ^{a,\varepsilon:C} \rloop{0,-1} ^{b,C:\varepsilon} \ar "1,4" ^{\varepsilon,T:\varepsilon} *=[o][F=]{3} \\ *=[o][F-]{0} \ar @`{+/l16mm/} [] ^{} \ar "1,2" ^{\varepsilon,\varepsilon:T} \ar "2,3" _{\varepsilon,\varepsilon:T} *=[o][F-]{2} \rloop{0,1} ^{a,\varepsilon:C} \rloop{0,-1} ^{a,C:\varepsilon} \ar "1,4" _{\varepsilon,T:\varepsilon} }$$
Теорема 10.2.7. Если
язык L распознается
некоторым МП-автоматом,
то L является контекстно-свободным.
Доказательство.
Пусть язык L распознается МП-автоматом $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$.
Без ограничения общности можно считать,
что $$I = \{ \qinitial \}$$, $$F = \{ \qaccept \}$$
и каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$
удовлетворяет требованию $$| \beta | + | \gamma | = 1$$.
Построим искомую
Пример 10.2.8.
МП-автомат $$M =
\lalg \{ 1 , 2 \} , \Sigma , \Gamma , \Delta ,
\{ 1 \} , \{ 2 \} \ralg$$,
где $$\Sigma = \{ a , b \}$$, $$\Gamma = \{ D , E \}$$,$$\begin{multiline*}
\Delta = \{
\lp \lp 1 , ab , \varepsilon \rp ,
\lp 1 , E \rp \rp ,\
\lp \lp 1 , aa , E \rp ,
\lp 1 , \varepsilon \rp \rp ,\
\lp \lp 1 , b , \varepsilon \rp ,
\lp 2 , D \rp \rp ,\
\\
\lp \lp 2 , a , \varepsilon \rp ,
\lp 1 , D \rp \rp ,\
\lp \lp 2 , \varepsilon , D \rp ,
\lp 2 , \varepsilon \rp \rp ,\
\lp \lp 2 , b , E \rp ,
\lp 2 , \varepsilon \rp \rp
\} ,
\end{multiline*}$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix @=11mm{
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\rloop{0,1} ^{ab,\varepsilon:E}
\rloop{0,-1} ^{aa,E:\varepsilon}
\ar "1,2" <0.6mm> ^{b,\varepsilon:D}
*=[o][F=]{2}
\ar "1,1" <0.6mm> ^{a,\varepsilon:D}
\rloop{0,1} ^{\varepsilon,D:\varepsilon}
\rloop{0,-1} ^{b,E:\varepsilon}
}$$
и контекстно-свободная грамматика$$\begin{align*}
S \; {\to} \; abTaaS , T \; {\to} \; abTaaT , \\
S \; {\to} \; abSbU , T \; {\to} \; \varepsilon , \\
S \; {\to} \; bUU , U \; {\to} \; aSU , \\
U \; {\to} \; \varepsilon
\end{align*}$$
задают один и тот же язык.
Здесь S, T и U
соответствуют символам A1,2, A1,1
и A2,2
из доказательства теоремы 10.2.7.
Упражнение 10.2.9. Найти МП-автомат, распознающий язык, порождаемый грамматикой$$\begin{align*} F \; {\to} \; a F b , \\ F \; {\to} \; a F a , \\ F \; {\to} \; a . \end{align*}$$
Упражнение 10.2.10. Найти
Упражнение 10.2.10. Найти
Упражнение 10.2.10. Найти
Теорема 10.3.1. Каждый МП-автомат эквивалентен некоторому МП-автомату $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, где |Q| = 2 и каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет требованиям |x| = 1, $$| \beta | \leq 1$$
и $$| \gamma | \leq 2$$.
Доказательство.
Пусть исходным МП-автоматом распознается
контекстно-свободный
язык $$L \subseteq \Sigma ^*$$.
Согласно теореме 8.4.6
язык $$L \sminus \{ \varepsilon \}$$
порождается некоторой
Q = {1,2}, I = {1},$$\begin{gathered*}
F =
\begin{cases}
\{ 1 , 2 \}, \; \text{если}\; \varepsilon \in L ,\\
\{ 2 \}, \; \text{если}\; \varepsilon \notin L ,
\end{cases}
\\
\Delta =
\{ \langle \langle 2 , a ,\! A \rangle ,\! \langle 2 ,\! \gamma \rangle \rangle
\mid
( A \to a \gamma ) \in P \}
\cup
\{ \langle \langle 1 , a ,\! \varepsilon \rangle ,\!
\langle 2 ,\! \gamma \rangle \rangle
\mid
( S \to a \gamma ) \in P \} .
\end{gathered*}$$
Теорема 10.3.2. Каждый МП-автомат эквивалентен некоторому МП-автомату $$\lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg$$, в котором каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет требованиям |x| = 1, $$| \beta | \leq 1$$ и $$| \gamma | \leq 1$$.
Доказательство.
Пусть исходным МП-автоматом распознается
контекстно-вободный язык $$L \subseteq \Sigma ^*$$.
Согласно теореме 8.4.6
язык $$L \sminus \{ \varepsilon \}$$
порождается некоторой
контекстно-вободной грамматикой $$G = \lalg N , \Sigma , P , S \ralg$$,
в которой
каждое правило имеет один из следующих трех видов: $$A \tto a$$, $$A \tto a B$$, $$A \tto a B C$$,
где $$A \in N$$, $$B \in N$$, $$C \in N$$, $$a \in \Sigma$$.
Легко добиться того, чтобы
в правилах грамматики G
вспомогательные символы в правой части
(то есть символы B и C )
были отличны от начального символа S.
Положим $$Q = N \cup \{ \bot \}$$, где $$\bot \notin N$$. Далее, положим $$\Gamma = N$$,$$I = \{ S \} ,\qquad F = \begin{cases} \{ S , \bot \}, \mathspace\text{если}\mathspace \varepsilon \in L ,\\ \{ \bot \}, \mathspace\text{если}\mathspace \varepsilon \notin L , \end{cases}$$ $$\begin{align*} \Delta = \{ \lp \lp A , a , \varepsilon \rp , \lp B , C \rp \rp \mid ( A \tto a B C ) \in P \} \cup {} \\ \myqquad \cup \{ \lp \lp A , a , \varepsilon \rp , \lp B , \varepsilon \rp \rp \mid ( A \tto a B ) \in P \} \cup {} \\ \myqquad \cup \{ \lp \lp A , a , D \rp , \lp D , \varepsilon \rp \rp \mid ( A \tto a ) \in P \commaand D \in N \sminus \{ S \} \} \cup {} \\ \myqquad \cup \{ \lp \lp A , a , \varepsilon \rp , \lp \bot , \varepsilon \rp \rp \mid ( A \tto a ) \in P \} . \end{align*}$$
Упражнение 10.3.3. Найти для языка, порождаемого грамматикой$$\begin{align*}
S \; {\to} \; a T T , \\
S \; {\to} \; \varepsilon , \\
T \; {\to} \; b T U , \\
T \; {\to} \; c , \\
U \; {\to} \; a T ,
\end{align*}$$
МП-автомат,
в котором
каждый переход $$\lp \lp p , x , \beta \rp ,
\lp q , \gamma \rp \rp \in \Delta$$
удовлетворяет требованиям |x| = 1, $$| \beta | \leq 1$$
и $$| \gamma | \leq 1$$.
Упражнение 10.3.4. Найти для языка, порождаемого грамматикой$$\begin{align*} S \; {\to} \; a T U , \\ T \; {\to} \; a U T , \\ T \; {\to} \; b , \\ U \; {\to} \; b T , \\ U \; {\to} \; a , \end{align*}$$ МП-автомат, в котором каждый переход $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет требованиям $$| x | = 1$$, $$| \beta | \leq 1$$ и $$| \gamma | \leq 1$$.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.