К сожалению, теорема о детерминизации не переносится с конечных автоматов на автоматы с магазинной памятью. Возникает важный для практических приложений класс языков, распознаваемых детерминированными автоматами с магазинной памятью (то есть такими автоматами с магазинной памятью, которые ни в какой конфигурации не могут выбирать между несколькими очередными тактами). Точные определения этого класса автоматов и соответствующего класса языков даны в разделе 12.1. Чтобы получить полезный и естественный с точки зрения практики класс, нужно добавить в конец каждого слова специальный символ, называемый маркером конца слова. Языки из выделенного таким образом класса называются детерминированными контекстно-свободными языками. Во втором разделе лекции формулируется ряд свойств этого класса языков. Важность детерминированных контекстно-свободных языков для теоретической информатики обусловлена тем, что для каждого такого языка можно указать быстрый алгоритм, распознающий принадлежность слова этому языку.
Определение 12.1.1. Будем говорить, что два перехода МП-автомата $$\lp \lp p_1 , x_1 , \beta_1 \rp , \lp q_1 , \gamma_1 \rp \rp$$ и $$\lp \lp p_2 , x_2 , \beta_2 \rp , \lp q_2 , \gamma_2 \rp \rp$$ являются совместными, если
p1 = p2 ;Определение 12.1.2.
МП-автомат
называется детерминированным (
Пример 12.1.3.
МП-автомат M из примера 10.2.8
не является детерминированным, так как переходы $$\lp \lp 2 , a , \varepsilon \rp ,
\lp 1 , D \rp \rp$$
и $$\lp \lp 2 , \varepsilon , D \rp ,
\lp 2 , \varepsilon \rp \rp$$
совместны.
Определение 12.1.4.
Язык L
над алфавитом $$\Sigma$$
называется детерминированным контекстно-свободным языком,
если существует детерминированный МП-автомат, распознающий язык $$L \cdot \{ \eos \}$$
над алфавитом $$\Sigma \cup \{ \eos \}$$,
где $$\eos$$ -
дополнительный символ, не принадлежащий множеству $$\Sigma$$.
Символ $$\eos$$
называется маркером конца строки.
Пример 12.1.5.
Рассмотрим алфавит $$\Sigma = \{ a , b \}$$.
Язык $$L \peq \{ a^m b^n \mid m = n \rusor n = 0 \}$$ -
детерминированный L
не порождается никаким детерминированным МП-автоматом).
Пример 12.1.6.
Язык L,
распознаваемый МП-автоматом M
из примера 10.2.8,
является детерминированным
Упражнение 12.1.7. Является ли детерминированным
Теорема 12.2.1. Каждый автоматный язык является детерминированным контекстно-свободным языком.
Доказательство. Утверждение следует из теоремы 2.7.1.
Лемма 12.2.2. Каждый детерминированный МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$ эквивалентен некоторому детерминированному МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg $$, где для каждого перехода $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' $$ выполняется неравенство $$| x | + | \beta | \leq 1 $$.
Доказательство. Пусть дан детерминированный МП-автомат $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$. Назовем избытком перехода$$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta$$ натуральное число $$\max (0 , | x | + | \beta | - 1 ) $$. Докажем лемму индукцией по сумме избытков всех переходов.
Случай 1. $$\Delta \cap (( \{ p_0 \} \times \{ \varepsilon \} \times
\Gamma ^* ) \times ( Q \times \Gamma ^* )) = \varnothing $$.
Обозначим первый символ слова x0 через a0.
Преобразуем МП-автомат M в эквивалентный ему
детерминированный МП-автомат
с меньшей суммой избытков всех переходов.
Для этого добавим новое состояние r и переход $$\lp \lp p_0 , a_0 , \varepsilon \rp ,
\lp r , \varepsilon \rp \rp $$.
Каждый переход вида $$\lp \lp p_0 , a_0 x , \beta \rp ,
\lp q , \gamma \rp \rp $$ заменим на переход $$\lp \lp r , x , \beta
\rp , \lp q , \gamma \rp \rp $$.
К полученному таким образом
детерминированному МП-автомату
применимо предположение индукции.
Случай 2. $$\Delta \cap (( \{ p_0 \} \times \Sigma ^* \times \{
\varepsilon \} ) \times ( Q \times \Gamma ^* )) = \varnothing $$.
Обозначим первый символ слова $$\beta_0 $$
через C0.
Преобразуем МП-автомат M
в эквивалентный ему
детерминированный МП-автомат
с меньшей суммой избытков всех переходов.
Для этого добавим новое состояние r
и переход $$\lp \lp p_0 , \varepsilon , C_0 \rp ,
\lp r , \varepsilon \rp \rp $$.
Каждый переход вида $$\lp \lp p_0 , x , C_0 \beta \rp ,
\lp q , \gamma \rp \rp $$
заменим на переход $$\lp \lp r , x , \beta
\rp , \lp q , \gamma \rp \rp $$.
К полученному таким образом
детерминированному МП-автомату
применимо предположение индукции.
Случай 3. Существует переход $$\lp \lp p_0 , \varepsilon , \varepsilon \rp , \lp q_1 , \gamma_1 \rp \rp \in \Delta $$. Тогда переходы $$\lp \lp p_0 , x_0 , \beta_0 \rp , \lp q_0 , \gamma_0 \rp \rp $$ и $$\lp \lp p_0 , \varepsilon , \varepsilon \rp , \lp q_1 , \gamma_1 \rp \rp $$ совместны. Противоречие.
Случай 4. Существуют переход $$\lp \lp p_0 , \varepsilon , \beta_1 \rp , \lp q_1 , \gamma_1 \rp \rp \in \Delta $$ и переход $$\lp \lp p_0 , x_2 , \varepsilon \rp , \lp q_2 , \gamma_2 \rp \rp \in \Delta $$, где $$\beta_1 \neq \varepsilon $$ и $$x_2 \neq \varepsilon$$. Тогда переходы $$\lp \lp p_0 , \varepsilon , \beta_1 \rp , \lp q_1 , \gamma_1 \rp \rp $$ и $$\lp \lp p_0 , x_2 , \varepsilon \rp , \lp q_2 , \gamma_2 \rp \rp $$ совместны. Противоречие.
Лемма 12.2.3. Каждый детерминированный МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$ эквивалентен некоторому детерминированному МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg $$, где каждый переход $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' $$ удовлетворяет условиям $$| x | + | \beta | \leq 1 $$ и $$| \beta | + | \gamma | = 1 $$.
Доказательство. Сначала применим лемму 12.2.2, затем преобразуем МП-автомат так, чтобы для каждого перехода $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp $$ выполнялось неравенство $$| x | + | \beta | + | \gamma | \leq 1 $$ (см. пример 10.2.4), и в заключение заменим каждый переход вида $$\lp \lp p , x , \varepsilon \rp , \lp q , \varepsilon \rp \rp $$ на два последовательных перехода (см. пример 10.2.5).
Лемма 12.2.4. Пусть $$\eos \notin \Sigma $$, $$L \subseteq \Sigma ^* $$ и язык $$L \cdot \{ \eos \} $$ порождается некоторым детерминированным МП-автоматом. Тогда этот язык порождается также некоторым детерминированным МП-автоматом $$\lalg Q , \Sigma \cup \{ \eos \} , \Gamma , \Delta , I , F \ralg $$, где $$Q = Q_1 \cup Q_2 $$, $$Q_1 \cap Q_2 = \varnothing $$,$$\begin{align*} \Delta = \Delta_{11} \cup \Delta_{12} \cup \Delta_{22} ,\\ \Delta_{11} \subseteq ( Q_1 \times \Sigma ^* \times \Gamma^* ) \times ( Q_1 \times \Gamma^* ) ,\\ \Delta_{12} \subseteq ( Q_1 \times \{ \eos \} \times \Gamma^* ) \times ( Q_2 \times \Gamma^* ) ,\\ \Delta_{22} \subseteq ( Q_2 \times \{ \varepsilon \} \times \Gamma^* ) \times ( Q_2 \times \Gamma^* ) , \end{align*}$$ $$I \subseteq Q_1 $$, $$F \subseteq Q_2 $$ и каждый переход$$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет условиям $$| x | + | \beta | \leq 1 $$ и $$| \beta | + | \gamma | = 1 $$.
Доказательство. Применив лемму 12.2.3, получим детерминированный МП-автомат $$\lalg Q' , \Sigma \cup \{ \eos \} , \Gamma' , \Delta' , I' , F' \ralg $$. Построим искомый МП-автомат $$\lalg Q , \Sigma \cup \{ \eos \} , \Gamma , \Delta , I , F \ralg $$, положив $$Q = Q' \times \{ 1 , 2 \} $$, $$Q_1 = Q' \times \{ 1 \} $$, $$Q_2 = Q' \times \{ 2 \} $$, $$\Gamma = \Gamma' $$, $$I = I' \times \{ 1 \} $$, $$F = F' \times \{ 2 \} $$,$$\begin{align*} {} \Delta_{11} = \{ \lp \lp \lp p , 1 \rp , x , \beta \rp , \lp \lp q , 1 \rp , \gamma \rp \rp \mid \lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' \commaand x \in \Sigma ^* \} , \\ \Delta_{12} = \{ \lp \lp \lp p , 1 \rp , \eos , \beta \rp , \lp \lp q , 2 \rp , \gamma \rp \rp \mid \lp \lp p , \eos , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' \} , \\ \Delta_{22} = \{ \lp \lp \lp p , 2 \rp , \varepsilon , \beta \rp , \lp \lp q , 2 \rp , \gamma \rp \rp \mid \lp \lp p , \varepsilon , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' \} . \end{align*}$$
Теорема 12.2.5. Язык $$L \subseteq \Sigma ^* $$ является детерминированным контекстно-свободным языком тогда и только тогда, когда найдется такой детерминированный МП-автомат $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg $$, что$$L \squeeze{=} \{ w \squeeze{\in} \Sigma^* \squeeze{\mid} \lp s ,\! w ,\! \varepsilon \rp \squeeze{\overstar{\vdash}} \lp q ,\! \varepsilon ,\! \alpha \rp \mathspace\text{для некоторых}\mathspace s \squeeze{\in} I' ,\ \! q \squeeze{\in} F' \commaand \! \alpha \squeeze{\in} \Gamma ^{\prime *} \} .$$
Доказательство. Достаточность проверяется легко. Докажем необходимость. Рассмотрим МП-автомат$$M = \lalg Q_1 \cup Q_2 , \Sigma \cup \{ \eos \} , \Gamma , \Delta_{11} \cup \Delta_{12} \cup \Delta_{22} , \{ \qinitial \} , F \ralg ,$$ о котором говорится в лемме 12.2.4.
Для любых $$\alpha \in \Gamma ^* $$ и $$H \subseteq Q_2 $$ введем обозначение$$\Delta_{22} ^{-1} ( \alpha , H ) = \{ p \in Q_2 \mid \lp p , \varepsilon , \alpha \rp \overstar{\vdash} \lp q , \varepsilon , \varepsilon \rp \mathspace\text{для некоторого}\mathspace q \in H \} .$$ Очевидно, что $$\Delta_{22} ^{-1} ( \gamma , \Delta_{22} ^{-1} ( \alpha , H )) = \Delta_{22} ^{-1} ( \gamma \alpha , H ) $$ для любых $$\alpha \in \Gamma ^* $$, $$\gamma \in \Gamma ^* $$ и $$H \subseteq Q_2 $$.
Построим искомый МП-автомат $$\lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg $$,
положив$$\begin{align*}
Q' = Q_1 \times \powerset{ Q_2 } ,\\
\Gamma' = \Gamma \times \powerset{ Q_2 } ,\\
I' = \{ \qnew{ \qinitial }{ \Delta_{22} ^{-1} ( \varepsilon , F ) } \} ,\\
F' = \{ \qnew{ p }{ H }
\mid
\lp \lp p , \eos , \varepsilon \rp , \lp q , C \rp \rp \in \Delta_{12}
,\
H \subseteq Q_2
\commaand
q \in \Delta_{22} ^{-1} ( C , H )
\} ,\\
\Delta' = \{ \lp \lp \qnew{ p }{ H } , x , \gamnew{ C }{ K } \rp ,
\lp \qnew{ q }{ K } , \varepsilon \rp \rp
\mid
\\ \myqquad \hphantom{ {} \cup{} \{ } %\}
\lp \lp p , x , C \rp , \lp q , \varepsilon \rp \rp \in \Delta_{11} ,\
H \subseteq Q_2 \commaand K \subseteq Q_2
\} \cup
{}\\ \myqquad \cup
\{ \lp \lp \qnew{ p }{ H } , x , \varepsilon \rp ,
\lp \qnew{ q }{ \Delta_{22} ^{-1} ( C , H ) } , \gamnew{ C }{ H } \rp \rp
\mid
\\ \myqquad \hphantom{ {} \cup{} \{ } %\}
\lp \lp p , x , \varepsilon \rp , \lp q , C \rp \rp \in \Delta_{11}
\commaand H \subseteq Q_2 \} .
\end{align*}$$
(Напоминаем, что через $$\powerset{ Q_2 } $$
обозначается
множество всех подмножеств множества Q2.)
Индукцией по количеству тактов работы можно доказать, что$$\lp \qnew{ \qinitial }{ \Delta_{22} ^{-1} ( \varepsilon , F ) } , w , \varepsilon \rp \overstar{\myunderset{ M' }{\vdash}} \lp \qnew{ q }{ H_0 } , \varepsilon , \gamnew{ C_1 }{ H_1 } \gamnew{ C_2 }{ H_2 } \ldots \gamnew{ C_n }{ H_n } \rp$$ тогда и только тогда, когда$$\lp \qinitial , w , \varepsilon \rp \overstar{\myunderset{ M }{\vdash}} \lp q , \varepsilon , C_1 C_2 \ldots C_n \rp$$ и$$H_k = \Delta_{22} ^{-1} ( C_{k+1} C_{k+2} \ldots C_n , F )$$ для каждого $$k \leq n $$.
Теорема 12.2.6. Пусть L - детерминированный контекстно-свободный язык.
Тогда язык L не является существенно неоднозначным.
Доказательство.
Пусть дан детерминированный L.
Рассмотрим МП-автомат$$M = \lalg Q_1 \cup Q_2 , \Sigma \cup \{ \eos \} , \Gamma ,
\Delta_{11} \cup \Delta_{12} \cup \Delta_{22} ,
\{ \qinitial \} , F \ralg ,$$
о котором говорится в лемме 12.2.4.
Применив к этому МП-автомату конструкцию из доказательства
теоремы 10.2.7,
получим однозначную G,
порождающую язык $$L \cdot \{ \eos \} $$.
Стирая в этой грамматике все вхождения символа $$\eos $$,
получим G',
порождающую язык L.
Так как
МП-автомат M
не содержит переходов,
ведущих из Q2
в Q1,
а символ $$\eos $$
встречается только на переходах,
ведущих из Q1
в Q2,
то в каждом G' -выводе однозначно определяется правило,
которому в G
соответствует правило, содержащее $$\eos $$.
Поэтому существует естественное однозначное соответствие между
деревьями вывода в грамматике G'
и деревьями вывода в грамматике G
(при этом кроны соответствующих друг другу деревьев различаются только
символом $$\eos $$ ).
Следовательно, грамматика G' тоже является однозначной.
Теорема 12.2.7. Дополнение каждого детерминированного контекстно-свободного языка является детерминированным контекстно-свободным языком.
Доказательство можно найти в [7, c. 110-116] или [2, c. 212-217].
Пример 12.2.8.
Язык $$L = \{ a^k b^m c^n \mid k \neq m \rusor m \neq n \} $$
над алфавитом {a,b,c}
не является детерминированным
Теорема 12.2.9. Неверно, что для любых детерминированных контекстно-свободных языков L1 и L2 язык $$L_1 \cap L_2$$ тоже является детерминированным контекстно-свободным языком.
Доказательство.
Достаточно рассмотреть
детерминированные L1
и L2
из доказательства теоремы 9.5.1.
Теорема 12.2.10. Неверно, что для любых детерминированных контекстно-свободных языков L1 и L2 язык $$L_1 \cup L_2 $$ тоже является детерминированным контекстно-свободным языком.
Доказательство. Утверждение следует из теорем 12.2.7 и 12.2.9 и закона де Моргана.
Упражнение 12.2.11. Является ли детерминированным
К сожалению, теорема о детерминизации не переносится с конечных автоматов на автоматы с магазинной памятью. Возникает важный для практических приложений класс языков, распознаваемых детерминированными автоматами с магазинной памятью (то есть такими автоматами с магазинной памятью, которые ни в какой конфигурации не могут выбирать между несколькими очередными тактами). Точные определения этого класса автоматов и соответствующего класса языков даны в разделе 12.1. Чтобы получить полезный и естественный с точки зрения практики класс, нужно добавить в конец каждого слова специальный символ, называемый маркером конца слова. Языки из выделенного таким образом класса называются детерминированными контекстно-свободными языками. Во втором разделе лекции формулируется ряд свойств этого класса языков. Важность детерминированных контекстно-свободных языков для теоретической информатики обусловлена тем, что для каждого такого языка можно указать быстрый алгоритм, распознающий принадлежность слова этому языку.
Определение 12.1.1. Будем говорить, что два перехода МП-автомата $$\lp \lp p_1 , x_1 , \beta_1 \rp , \lp q_1 , \gamma_1 \rp \rp$$ и $$\lp \lp p_2 , x_2 , \beta_2 \rp , \lp q_2 , \gamma_2 \rp \rp$$ являются совместными, если
p1 = p2 ;Определение 12.1.2.
МП-автомат
называется детерминированным (
Пример 12.1.3.
МП-автомат M из примера 10.2.8
не является детерминированным, так как переходы $$\lp \lp 2 , a , \varepsilon \rp ,
\lp 1 , D \rp \rp$$
и $$\lp \lp 2 , \varepsilon , D \rp ,
\lp 2 , \varepsilon \rp \rp$$
совместны.
Определение 12.1.4.
Язык L
над алфавитом $$\Sigma$$
называется детерминированным контекстно-свободным языком,
если существует детерминированный МП-автомат, распознающий язык $$L \cdot \{ \eos \}$$
над алфавитом $$\Sigma \cup \{ \eos \}$$,
где $$\eos$$ -
дополнительный символ, не принадлежащий множеству $$\Sigma$$.
Символ $$\eos$$
называется маркером конца строки.
Пример 12.1.5.
Рассмотрим алфавит $$\Sigma = \{ a , b \}$$.
Язык $$L \peq \{ a^m b^n \mid m = n \rusor n = 0 \}$$ -
детерминированный L
не порождается никаким детерминированным МП-автоматом).
Пример 12.1.6.
Язык L,
распознаваемый МП-автоматом M
из примера 10.2.8,
является детерминированным
Упражнение 12.1.7. Является ли детерминированным
Теорема 12.2.1. Каждый автоматный язык является детерминированным контекстно-свободным языком.
Доказательство. Утверждение следует из теоремы 2.7.1.
Лемма 12.2.2. Каждый детерминированный МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$ эквивалентен некоторому детерминированному МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg $$, где для каждого перехода $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' $$ выполняется неравенство $$| x | + | \beta | \leq 1 $$.
Доказательство. Пусть дан детерминированный МП-автомат $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$. Назовем избытком перехода$$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta$$ натуральное число $$\max (0 , | x | + | \beta | - 1 ) $$. Докажем лемму индукцией по сумме избытков всех переходов.
Случай 1. $$\Delta \cap (( \{ p_0 \} \times \{ \varepsilon \} \times
\Gamma ^* ) \times ( Q \times \Gamma ^* )) = \varnothing $$.
Обозначим первый символ слова x0 через a0.
Преобразуем МП-автомат M в эквивалентный ему
детерминированный МП-автомат
с меньшей суммой избытков всех переходов.
Для этого добавим новое состояние r и переход $$\lp \lp p_0 , a_0 , \varepsilon \rp ,
\lp r , \varepsilon \rp \rp $$.
Каждый переход вида $$\lp \lp p_0 , a_0 x , \beta \rp ,
\lp q , \gamma \rp \rp $$ заменим на переход $$\lp \lp r , x , \beta
\rp , \lp q , \gamma \rp \rp $$.
К полученному таким образом
детерминированному МП-автомату
применимо предположение индукции.
Случай 2. $$\Delta \cap (( \{ p_0 \} \times \Sigma ^* \times \{
\varepsilon \} ) \times ( Q \times \Gamma ^* )) = \varnothing $$.
Обозначим первый символ слова $$\beta_0 $$
через C0.
Преобразуем МП-автомат M
в эквивалентный ему
детерминированный МП-автомат
с меньшей суммой избытков всех переходов.
Для этого добавим новое состояние r
и переход $$\lp \lp p_0 , \varepsilon , C_0 \rp ,
\lp r , \varepsilon \rp \rp $$.
Каждый переход вида $$\lp \lp p_0 , x , C_0 \beta \rp ,
\lp q , \gamma \rp \rp $$
заменим на переход $$\lp \lp r , x , \beta
\rp , \lp q , \gamma \rp \rp $$.
К полученному таким образом
детерминированному МП-автомату
применимо предположение индукции.
Случай 3. Существует переход $$\lp \lp p_0 , \varepsilon , \varepsilon \rp , \lp q_1 , \gamma_1 \rp \rp \in \Delta $$. Тогда переходы $$\lp \lp p_0 , x_0 , \beta_0 \rp , \lp q_0 , \gamma_0 \rp \rp $$ и $$\lp \lp p_0 , \varepsilon , \varepsilon \rp , \lp q_1 , \gamma_1 \rp \rp $$ совместны. Противоречие.
Случай 4. Существуют переход $$\lp \lp p_0 , \varepsilon , \beta_1 \rp , \lp q_1 , \gamma_1 \rp \rp \in \Delta $$ и переход $$\lp \lp p_0 , x_2 , \varepsilon \rp , \lp q_2 , \gamma_2 \rp \rp \in \Delta $$, где $$\beta_1 \neq \varepsilon $$ и $$x_2 \neq \varepsilon$$. Тогда переходы $$\lp \lp p_0 , \varepsilon , \beta_1 \rp , \lp q_1 , \gamma_1 \rp \rp $$ и $$\lp \lp p_0 , x_2 , \varepsilon \rp , \lp q_2 , \gamma_2 \rp \rp $$ совместны. Противоречие.
Лемма 12.2.3. Каждый детерминированный МП-автомат $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$ эквивалентен некоторому детерминированному МП-автомату $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg $$, где каждый переход $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' $$ удовлетворяет условиям $$| x | + | \beta | \leq 1 $$ и $$| \beta | + | \gamma | = 1 $$.
Доказательство. Сначала применим лемму 12.2.2, затем преобразуем МП-автомат так, чтобы для каждого перехода $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp $$ выполнялось неравенство $$| x | + | \beta | + | \gamma | \leq 1 $$ (см. пример 10.2.4), и в заключение заменим каждый переход вида $$\lp \lp p , x , \varepsilon \rp , \lp q , \varepsilon \rp \rp $$ на два последовательных перехода (см. пример 10.2.5).
Лемма 12.2.4. Пусть $$\eos \notin \Sigma $$, $$L \subseteq \Sigma ^* $$ и язык $$L \cdot \{ \eos \} $$ порождается некоторым детерминированным МП-автоматом. Тогда этот язык порождается также некоторым детерминированным МП-автоматом $$\lalg Q , \Sigma \cup \{ \eos \} , \Gamma , \Delta , I , F \ralg $$, где $$Q = Q_1 \cup Q_2 $$, $$Q_1 \cap Q_2 = \varnothing $$,$$\begin{align*} \Delta = \Delta_{11} \cup \Delta_{12} \cup \Delta_{22} ,\\ \Delta_{11} \subseteq ( Q_1 \times \Sigma ^* \times \Gamma^* ) \times ( Q_1 \times \Gamma^* ) ,\\ \Delta_{12} \subseteq ( Q_1 \times \{ \eos \} \times \Gamma^* ) \times ( Q_2 \times \Gamma^* ) ,\\ \Delta_{22} \subseteq ( Q_2 \times \{ \varepsilon \} \times \Gamma^* ) \times ( Q_2 \times \Gamma^* ) , \end{align*}$$ $$I \subseteq Q_1 $$, $$F \subseteq Q_2 $$ и каждый переход$$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta$$ удовлетворяет условиям $$| x | + | \beta | \leq 1 $$ и $$| \beta | + | \gamma | = 1 $$.
Доказательство. Применив лемму 12.2.3, получим детерминированный МП-автомат $$\lalg Q' , \Sigma \cup \{ \eos \} , \Gamma' , \Delta' , I' , F' \ralg $$. Построим искомый МП-автомат $$\lalg Q , \Sigma \cup \{ \eos \} , \Gamma , \Delta , I , F \ralg $$, положив $$Q = Q' \times \{ 1 , 2 \} $$, $$Q_1 = Q' \times \{ 1 \} $$, $$Q_2 = Q' \times \{ 2 \} $$, $$\Gamma = \Gamma' $$, $$I = I' \times \{ 1 \} $$, $$F = F' \times \{ 2 \} $$,$$\begin{align*} {} \Delta_{11} = \{ \lp \lp \lp p , 1 \rp , x , \beta \rp , \lp \lp q , 1 \rp , \gamma \rp \rp \mid \lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' \commaand x \in \Sigma ^* \} , \\ \Delta_{12} = \{ \lp \lp \lp p , 1 \rp , \eos , \beta \rp , \lp \lp q , 2 \rp , \gamma \rp \rp \mid \lp \lp p , \eos , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' \} , \\ \Delta_{22} = \{ \lp \lp \lp p , 2 \rp , \varepsilon , \beta \rp , \lp \lp q , 2 \rp , \gamma \rp \rp \mid \lp \lp p , \varepsilon , \beta \rp , \lp q , \gamma \rp \rp \in \Delta' \} . \end{align*}$$
Теорема 12.2.5. Язык $$L \subseteq \Sigma ^* $$ является детерминированным контекстно-свободным языком тогда и только тогда, когда найдется такой детерминированный МП-автомат $$M' \peq \lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg $$, что$$L \squeeze{=} \{ w \squeeze{\in} \Sigma^* \squeeze{\mid} \lp s ,\! w ,\! \varepsilon \rp \squeeze{\overstar{\vdash}} \lp q ,\! \varepsilon ,\! \alpha \rp \mathspace\text{для некоторых}\mathspace s \squeeze{\in} I' ,\ \! q \squeeze{\in} F' \commaand \! \alpha \squeeze{\in} \Gamma ^{\prime *} \} .$$
Доказательство. Достаточность проверяется легко. Докажем необходимость. Рассмотрим МП-автомат$$M = \lalg Q_1 \cup Q_2 , \Sigma \cup \{ \eos \} , \Gamma , \Delta_{11} \cup \Delta_{12} \cup \Delta_{22} , \{ \qinitial \} , F \ralg ,$$ о котором говорится в лемме 12.2.4.
Для любых $$\alpha \in \Gamma ^* $$ и $$H \subseteq Q_2 $$ введем обозначение$$\Delta_{22} ^{-1} ( \alpha , H ) = \{ p \in Q_2 \mid \lp p , \varepsilon , \alpha \rp \overstar{\vdash} \lp q , \varepsilon , \varepsilon \rp \mathspace\text{для некоторого}\mathspace q \in H \} .$$ Очевидно, что $$\Delta_{22} ^{-1} ( \gamma , \Delta_{22} ^{-1} ( \alpha , H )) = \Delta_{22} ^{-1} ( \gamma \alpha , H ) $$ для любых $$\alpha \in \Gamma ^* $$, $$\gamma \in \Gamma ^* $$ и $$H \subseteq Q_2 $$.
Построим искомый МП-автомат $$\lalg Q' , \Sigma , \Gamma' , \Delta' , I' , F' \ralg $$,
положив$$\begin{align*}
Q' = Q_1 \times \powerset{ Q_2 } ,\\
\Gamma' = \Gamma \times \powerset{ Q_2 } ,\\
I' = \{ \qnew{ \qinitial }{ \Delta_{22} ^{-1} ( \varepsilon , F ) } \} ,\\
F' = \{ \qnew{ p }{ H }
\mid
\lp \lp p , \eos , \varepsilon \rp , \lp q , C \rp \rp \in \Delta_{12}
,\
H \subseteq Q_2
\commaand
q \in \Delta_{22} ^{-1} ( C , H )
\} ,\\
\Delta' = \{ \lp \lp \qnew{ p }{ H } , x , \gamnew{ C }{ K } \rp ,
\lp \qnew{ q }{ K } , \varepsilon \rp \rp
\mid
\\ \myqquad \hphantom{ {} \cup{} \{ } %\}
\lp \lp p , x , C \rp , \lp q , \varepsilon \rp \rp \in \Delta_{11} ,\
H \subseteq Q_2 \commaand K \subseteq Q_2
\} \cup
{}\\ \myqquad \cup
\{ \lp \lp \qnew{ p }{ H } , x , \varepsilon \rp ,
\lp \qnew{ q }{ \Delta_{22} ^{-1} ( C , H ) } , \gamnew{ C }{ H } \rp \rp
\mid
\\ \myqquad \hphantom{ {} \cup{} \{ } %\}
\lp \lp p , x , \varepsilon \rp , \lp q , C \rp \rp \in \Delta_{11}
\commaand H \subseteq Q_2 \} .
\end{align*}$$
(Напоминаем, что через $$\powerset{ Q_2 } $$
обозначается
множество всех подмножеств множества Q2.)
Индукцией по количеству тактов работы можно доказать, что$$\lp \qnew{ \qinitial }{ \Delta_{22} ^{-1} ( \varepsilon , F ) } , w , \varepsilon \rp \overstar{\myunderset{ M' }{\vdash}} \lp \qnew{ q }{ H_0 } , \varepsilon , \gamnew{ C_1 }{ H_1 } \gamnew{ C_2 }{ H_2 } \ldots \gamnew{ C_n }{ H_n } \rp$$ тогда и только тогда, когда$$\lp \qinitial , w , \varepsilon \rp \overstar{\myunderset{ M }{\vdash}} \lp q , \varepsilon , C_1 C_2 \ldots C_n \rp$$ и$$H_k = \Delta_{22} ^{-1} ( C_{k+1} C_{k+2} \ldots C_n , F )$$ для каждого $$k \leq n $$.
Теорема 12.2.6. Пусть L - детерминированный контекстно-свободный язык.
Тогда язык L не является существенно неоднозначным.
Доказательство.
Пусть дан детерминированный L.
Рассмотрим МП-автомат$$M = \lalg Q_1 \cup Q_2 , \Sigma \cup \{ \eos \} , \Gamma ,
\Delta_{11} \cup \Delta_{12} \cup \Delta_{22} ,
\{ \qinitial \} , F \ralg ,$$
о котором говорится в лемме 12.2.4.
Применив к этому МП-автомату конструкцию из доказательства
теоремы 10.2.7,
получим однозначную G,
порождающую язык $$L \cdot \{ \eos \} $$.
Стирая в этой грамматике все вхождения символа $$\eos $$,
получим G',
порождающую язык L.
Так как
МП-автомат M
не содержит переходов,
ведущих из Q2
в Q1,
а символ $$\eos $$
встречается только на переходах,
ведущих из Q1
в Q2,
то в каждом G' -выводе однозначно определяется правило,
которому в G
соответствует правило, содержащее $$\eos $$.
Поэтому существует естественное однозначное соответствие между
деревьями вывода в грамматике G'
и деревьями вывода в грамматике G
(при этом кроны соответствующих друг другу деревьев различаются только
символом $$\eos $$ ).
Следовательно, грамматика G' тоже является однозначной.
Теорема 12.2.7. Дополнение каждого детерминированного контекстно-свободного языка является детерминированным контекстно-свободным языком.
Доказательство можно найти в [7, c. 110-116] или [2, c. 212-217].
Пример 12.2.8.
Язык $$L = \{ a^k b^m c^n \mid k \neq m \rusor m \neq n \} $$
над алфавитом {a,b,c}
не является детерминированным
Теорема 12.2.9. Неверно, что для любых детерминированных контекстно-свободных языков L1 и L2 язык $$L_1 \cap L_2$$ тоже является детерминированным контекстно-свободным языком.
Доказательство.
Достаточно рассмотреть
детерминированные L1
и L2
из доказательства теоремы 9.5.1.
Теорема 12.2.10. Неверно, что для любых детерминированных контекстно-свободных языков L1 и L2 язык $$L_1 \cup L_2 $$ тоже является детерминированным контекстно-свободным языком.
Доказательство. Утверждение следует из теорем 12.2.7 и 12.2.9 и закона де Моргана.
Упражнение 12.2.11. Является ли детерминированным
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.