В лекции 2 были доказаны лемма
о разрастании и свойства замкнутости класса автоматных языков.
Некоторые из этих теорем имеют аналоги для класса
Лемма о разрастании для
В разделе 9.6 доказывается, что пересечение контекстно-свободного языка с автоматным языком является контекстно-свободным. В сочетании с леммой о разрастании этот факт дает удобное средство, позволяющее во многих задачах доказать, что заданный язык не является контекстно-свободным. Еще одно необходимое условие контекстной свободности сформулировано в разделе 9.7*.
Лемма 9.1.1 (pumping lemma, лемма о разрастании, лемма о накачке,
лемма-насос) Пусть L - контекстно-свободный язык над
алфавитом $$\Sigma$$. Тогда найдется такое положительное целое число p, что для любого слова $$w \in L$$ длины не меньше p можно подобрать слова $$u , v , x , y , z \in \Sigma ^*$$, для которых верно uvxyz = w, $$v y \neq \varepsilon$$
( то есть $$v \neq \varepsilon$$ или $$y \neq
\varepsilon$$ ), $$| v x y | \leq p$$ и $$u v ^i x y ^i z \in L$$ для всех $$i \in \mathbb{N}$$.
Доказательство.
Пусть язык $$L$$
порождается грамматикой в нормальной форме Хомского $$G = \lalg N , \Sigma , P , S \ralg$$.
Индукцией по k
легко доказать, что для любого G
длина 2k-2,
где k - количество вершин в самом длинном пути,
начинающемся в корне дерева и заканчивающемся в некоторой вершине,
помеченной символом из $$\Sigma$$.
Положим p = 2|N|.
Пусть $$w \in L$$
и $$| w | \geq p$$.
Зафиксируем некоторое w
в грамматике G.
Рассмотрим самый длинный путь в этом дереве.
Этот путь содержит не менее |N| + 2
вершин.
Среди них найдутся две вершины
с одинаковыми метками, причем их можно выбрать
среди последних |N| + 2
вершин рассматриваемого пути.
Выберем слова u, v, x, y и z
так, что uvxyz = w,
поддерево с корнем в одной из найденных вершин имеет крону x
и поддерево с корнем в другой найденной вершине имеет крону vxy.
Из того что G -
грамматика в нормальной форме Хомского,
заключаем, что $$v x y \neq x$$.
Неравенство $$| v x y | \leq 2^{ | N | }$$
следует из того, что
самый длинный путь в соответствующем слову vxy
поддереве содержит не более |N| + 2
вершин. Для каждого $$i \in \mathbb{N}$$
можно построить uvixyiz,
комбинируя части исходного
Пример 9.1.2.
Рассмотрим язык $$L = \{ a^n b^n c^n \mid n \geq 0 \}$$
над алфавитом {a,b,c}.
Утверждение леммы 9.1.1
не выполняется ни для какого натурального числа p.
Действительно,
если uvxyz = apbpcp, |vy| > 0
и $$| v x y | \leq p$$,
то |vy|a = 0
или |vy|c = 0.
Следовательно, |uvvxyyz|a = p
или |uvvxyyz|c = p.
Так как |uvvxyyz| > 3p,
то $$u v v x y y z \notin L$$.
Из этого можно заключить, что язык L
не является контекстно-свободным.
Теорема 9.1.3. Каждый контекстно-свободный язык над однобуквенным алфавитом является автоматным.
Доказательство.
Пусть дан L
над алфавитом {a}.
Согласно лемме 9.1.1
найдется такое натуральное число p,
что множество $$\{ k \in \mathbb{N} \mid a^k \in L \}$$
является объединением некоторого семейства
арифметических прогрессий,
причем у каждой прогрессии первый член и шаг не больше числа p.
Так как существует лишь конечное число прогрессий натуральных чисел
с таким ограничением,
рассматриваемое семейство конечно.
Следовательно, язык L
является автоматным
(используем пример 2.1.18).
Упражнение 9.1.4. Является ли
Упражнение 9.1.5. Является ли
Упражнение 9.1.6. Является ли
Упражнение 9.1.7. Является ли {am | m простое}?
Упражнение 9.1.8. Является ли
Упражнение 9.1.9. Является ли
Упражнение 9.1.10. Является ли
Упражнение 9.1.11. Является ли
Упражнение 9.1.12. Является ли
Упражнение 9.1.13. Является ли {akbmcn | k < max(m,n)}?
Упражнение 9.1.14. Является ли {akbmcn | k > max(m,n)}?
Упражнение 9.1.15. Является ли
Упражнение 9.1.16. Какому классу принадлежит язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; T c V , \\ T \; {\to} \; b V , \\ V \; {\to} \; a V a , \\ V \; {\to} \; \varepsilon , \\ ac \; {\to} \; a ? \end{align*}$$
Упражнение 9.1.17. Существуют ли такие
Определение 9.2.1. Линейная грамматика в нормальной форме - это такая линейная грамматика, в которой каждое правило имеет вид $$A \tto \varepsilon$$, $$A \tto a$$, $$A \tto a B$$ или $$A \tto B a$$, где $$A \in N$$, $$B \in N$$, $$a \in \Sigma$$.
Теорема 9.2.2. Каждая линейная грамматика эквивалентна некоторой линейной грамматике в нормальной форме.
Теорема 9.2.3. Если линейный язык не содержит пустого слова, то он порождается некоторой линейной грамматикой в нормальной форме без $$\varepsilon$$ - правил.
Теорема 9.2.4. Язык L является линейным
тогда и только тогда, когда
язык $$L \sminus \{ \varepsilon \}$$ является линейным.
Лемма 9.2.5. Пусть L - линейный язык над алфавитом $$\Sigma$$. Тогда найдется такое положительное целое число p, что для любого слова $$w \in L$$ длины не меньше p можно подобрать слова $$u , v , x , y , z \in \Sigma ^*$$, для которых верно uvxyz = w, $$v y \neq \varepsilon$$
( то есть $$v \neq \varepsilon$$ или $$y \neq
\varepsilon$$ ), $$| u v | + | y z | \leq p$$ и $$u v ^i x y ^i z \in L$$ для всех $$i \in \mathbb{N}$$.
Доказательство.
Пусть язык $$L \sminus \{ \varepsilon \}$$
порождается линейной грамматикой в нормальной форме $$G = \lalg N , \Sigma , P , S \ralg$$
без $$\varepsilon$$ -правил.
Положим p = |N| + 1.
Пусть $$w \in L$$
и $$| w | \geq p$$.
Зафиксируем некоторое w
в грамматике G.
Рассмотрим самый длинный путь в этом дереве
(он начинается с корня и заканчивается некоторым листом,
помеченным символом из $$\Sigma$$ ).
Этот путь содержит не менее |N| + 1
вершин, помеченных элементами N.
Среди первых |N| + 1
вершин рассматриваемого пути
найдутся две вершины
с одинаковыми метками.
Выберем слова u, v, x, y и z
так, что uvxyz = w,
поддерево с корнем в одной из найденных вершин имеет крону x
и поддерево с корнем в другой найденной вершине имеет крону vxy.
Пример 9.2.6.
Рассмотрим язык $$L = \{ a^m b^m a^n b^n \mid m \geq 0 \commaand n \geq 0 \}$$
над алфавитом {a,b}.
Утверждение леммы 9.2.5
не выполняется ни для какого натурального числа p.
Следовательно, язык L
не является линейным.
Упражнение 9.2.7. Какому классу принадлежит язык$$\{ a^n b^n (cd)^m \mid n \geq 1 ,\ m \geq 1 \} ?$$
Упражнение 9.2.8. Какому классу принадлежит язык$$\{ a^k b^l c^m d^n \mid k < n ,\ l > m \} ?$$
Упражнение 9.2.9. Какому классу принадлежит язык$$\{ a^k b^l c^m a^n b^n c^k \mid k \geq 1 ,\ l < m ,\ n \geq 3 \} ?$$
Пример 9.3.1. Пусть $$\Sigma = \{ a , b , c \}$$. Язык $$\{ u c u \reverse \mid u \in \{ a , b \}^* \}$$ является линейным, так как он порождается грамматикой$$\begin{align*} S \; {\to} \; a S a , \\ S \; {\to} \; b S b , \\ S \; {\to} \; c . \end{align*}$$
Пример 9.3.2. Рассмотрим алфавит $$\Sigma = \{ a , b , c \}$$. Язык$$\{ a^m b^n c^k \mid 0 \leq m < n \commaand k \geq 0 \}$$ является линейным, так как он порождается грамматикой$$\begin{align*} S \; {\to} \; S c , T \; {\to} \; a T b , \\ S \; {\to} \; T , T \; {\to} \; T b , \\ T \; {\to} \; b . \end{align*}$$
Теорема 9.3.3. Если L1 и L2 - линейные языки над алфавитом $$\Sigma$$, то $$L_1 \cup L_2$$ тоже линейный язык.
Доказательство.
Пусть язык L1
порождается линейной грамматикой $$\lalg N_1 , \Sigma , P_1 , S_1 \ralg$$
и L2
порождается линейной грамматикой $$\lalg N_2 , \Sigma , P_2 , S_2 \ralg$$,
где $$N_1 \cap N_2 = \varnothing$$.
Тогда $$L_1 \cup L_2$$
порождается грамматикой$$\lalg N_1 \cup N_2 \cup \{ T \},
\Sigma,
P_1 \cup P_2 \cup \{ T \tto S_1 ,\ T \tto S_2 \} ,
T \ralg ,$$
где $$T \notin N_1 \cup N_2 \cup \Sigma$$.
Пример 9.3.4. Рассмотрим алфавит $$\Sigma = \{ a , b , c \}$$. Язык$$L \peq \Sigma ^* \sminus \{ a^n b^n c^n \mid n \geq 0 \}$$ является линейным, поскольку$$L \peq L_1 \cup L_2 \cup ( \Sigma ^* \sminus L_3 ) ,$$ где языки$$L_1 \peq \{ a^m b^n c^k \mid m \neq n \commaand k \geq 0 \} ,\quad L_2 \peq \{ a^m b^n c^k \mid n \neq k \commaand m \geq 0 \}$$ являются линейными, а язык$$L_3 \peq \{ a^m b^n c^k \mid m \geq 0 ,\ n \geq 0 \commaand k \geq 0 \}$$ является автоматным, и можно применить теоремы 9.3.3, 3.2.1, 2.4.1 и лемму 1.5.13.
Упражнение 9.3.5. Пусть $$\Sigma = \{ a , b , c \}$$. Является ли линейным язык $$\Sigma ^* \sminus \{ u c u \mid u \in \{ a , b \}^* \}$$?
Упражнение 9.3.6. Пусть $$\Sigma = \{ a , b , c \}$$. Является ли линейным язык $$\Sigma ^* \sminus \{ u c u \reverse \mid u \in \{ a , b \}^* \}$$?
Упражнение 9.3.7. Найти линейную грамматику, порождающую язык $$\{a,b,c\}^* \sminus L_1$$,
где L1
порождается грамматикой$$\begin{align*}
F \; {\to} \; ba F aaa , \\
F \; {\to} \; baa F b , \\
F \; {\to} \; ba c aaa , \\
F \; {\to} \; baa c b .
\end{align*}$$
Теорема 9.4.1. Если L - контекстно-свободный язык, то L* тоже контекстно-свободный язык.
Доказательство.
Пусть язык L
порождается L*
порождается грамматикой$$\lalg N \cup \{ T \} , \Sigma ,
P \cup \{ T \tto S T ,\ T \tto \varepsilon \} ,
T \ralg ,$$
где $$T \notin N \cup \Sigma$$.
Теорема 9.4.2. Если L1
и L2 - контекстно-свободные языки над алфавитом $$\Sigma$$,
то $$L_1 \cdot L_2$$ тоже контекстно-свободный язык.
Доказательство.
Пусть язык L1
порождается L2
порождается
Теорема 9.4.3. Если L1 и L2 - контекстно-свободные языки над алфавитом $$\Sigma$$, то $$L_1 \cup L_2$$ тоже контекстно-свободный язык.
Доказательство.
Пусть язык L1
порождается L2
порождается
Теорема 9.4.4. Если L - контекстно-свободный язык, то $$L \reverse$$ тоже контекстно-свободный язык.
Упражнение 9.4.5. Является ли
Упражнение 9.4.6.
Найти L1
порождается грамматикой$$\begin{align*}
F \; {\to} \; a , \\
F \; {\to} \; b F , \\
F \; {\to} \; c F F ,
\end{align*}$$
а язык L2
порождается грамматикой$$\begin{align*}
F \; {\to} \; a M , M \; {\to} \; a F , \\
F \; {\to} \; c M , M \; {\to} \; b F , \\
M \; {\to} \; \varepsilon .
\end{align*}$$
Теорема 9.5.1. Неверно, что для любых контекстно-свободных языков L1 и L2 язык $$L_1 \cap L_2$$ тоже контекстно-свободный.
Доказательство. Положим $$L_1 = \{ a^m b^m c^n \mid m \geq 0 \commaand n \geq 0 \}$$ и $$L_2 = \{ a^m b^n c^n \mid m \geq 0 \commaand n \geq 0 \}$$. В примере 9.2.1 было доказано, что язык $$L_1 \cap L_2$$ не является контекстно-свободным.
Теорема 9.5.2. Неверно, что для любого контекстно-свободного языка $$L \subseteq \Sigma ^*$$ язык $$\Sigma ^* \sminus L$$ тоже контекстно-свободный.
Доказательство.
Положим $$L = \Sigma ^* \sminus \{ a^n b^n c^n \mid n \geq 0 \}$$,
где $$\Sigma = \{ a , b , c \}$$.
В примере 9.3.4
было доказано, что язык L
является линейным
(и следовательно, контекстно-свободным).
Упражнение 9.5.3. Является ли
Упражнение 9.5.4. Является ли
Упражнение 9.5.5. Существует ли такой
линейный язык L
над алфавитом {a,b},
что язык $$L \reverse \cap L$$
не является контекстно-свободным?
Теорема 9.6.1. Если L1 - контекстно-свободный язык и L2 - автоматный язык, то язык $$L_1 \cap L_2$$ является контекстно-свободным.
Доказательство.
Пусть $$\lalg N , \Sigma , P , S \ralg$$ -
контекстно-свободная грамматика, порождающая язык L1.
Без ограничения общности можно считать, что множество P
содержит только правила вида $$A \tto a$$
и $$A \tto \alpha$$,
где $$A \in N$$, $$a \in \Sigma$$
и $$\alpha \in N ^*$$
(см. теорему 8.3.3).
Пусть $$\lalg Q , \Sigma , \Delta , I , F \ralg$$ -
конечный автомат,
распознающий язык L_2.
Без ограничения общности можно считать, что
для каждого перехода $$\lp p , x , q \rp \in \Delta$$
выполняется равенство |x| = 1
(см. лемму 2.3.3).
Построим
Пример 9.6.2.
Пусть $$\Sigma = \{ a , b , c \}$$.
Рассмотрим
L1,
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; a , \\
S \; {\to} \; b S , \\
S \; {\to} \; c S S ,
\end{align*}$$
и автоматный язык L2,
распознаваемый конечным автоматом $$M \peq \lalg Q , \Sigma , \Delta , I , F \ralg$$,
где Q = {1,2}, I = {1}, F = {2},$$\Delta = \{
\lp 1 , a , 2 \rp ,\
\lp 1 , c , 2 \rp ,\
\lp 2 , a , 1 \rp ,\
\lp 2 , b , 1 \rp
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\ar `ur_r{+/u7mm/}`r_dr{[0,2]}^{c} "1,3"
\ar "1,3" <0.6mm> ^{a}
*=[o][F=]{2}
\ar "1,1" <0.6mm> ^{a}
\ar `dl_l{+/d7mm/}`l_ul{[0,-2]}^{b} "1,1"
}$$
Тогда язык $$L_1 \cap L_2$$
порождается S11, S12, S21
и S22
соответствуют символам $$\lp 1 , S , 1 \rp$$, $$\lp 1 , S , 2 \rp$$, $$\lp 2 , S , 1 \rp$$
и $$\lp 2 , S , 2 \rp$$
из доказательства теоремы 9.6.1.
Теорема 9.6.3*. Если L1 - линейный язык и L2 - автоматный язык, то язык $$L_1 \cap L_2$$ является линейным.
Пример 9.6.4*.
Пусть $$\Sigma = \{ a , b \}$$.
Рассмотрим
линейный язык L1,
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; aaSaa , \\
S \; {\to} \; bSb , \\
S \; {\to} \; \varepsilon ,
\end{align*}$$
и
автоматный язык L2,
распознаваемый конечным автоматом $$M \peq \lalg Q , \Sigma , \Delta , I , F \ralg$$,
где Q = {1,2,3}, I = {1}, F = {3},$$\Delta = \{
\lp 1 , a , 1 \rp ,\
\lp 1 , b , 1 \rp ,\
\lp 1 , a , 2 \rp ,\
\lp 2 , b , 3 \rp ,\
\lp 3 , a , 3 \rp ,\
\lp 3 , b , 3 \rp
\} .$$
$$\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}
\rloop{0,1} ^{a}
\rloop{0,-1} ^{b}
}$$
Тогда язык $$L_1 \cap L_2$$
порождается S11 и S33
на один символ.
Упражнение 9.6.5. Найти L1
порождается грамматикой$$\begin{align*}
F \; {\to} \; a F a , \\
F \; {\to} \; b F b , \\
F \; {\to} \; \varepsilon ,
\end{align*}$$
а язык L2
порождается грамматикой$$\begin{align*}
K \; {\to} \; a M , M \; {\to} \; a K , \\
K \; {\to} \; b K , M \; {\to} \; b K , \\
M \; {\to} \; \varepsilon .
\end{align*}$$
Упражнение 9.6.6. Найти L1
порождается грамматикой$$\begin{align*}
F \; {\to} \; a F a , \\
F \; {\to} \; b F b , \\
F \; {\to} \; \varepsilon ,
\end{align*}$$
а язык L2
порождается грамматикой$$\begin{align*}
K \; {\to} \; a M , M \; {\to} \; a K , \\
K \; {\to} \; b M , K \; {\to} \; \varepsilon . \\
K \; {\to} \; b K ,
\end{align*}$$
Упражнение 9.6.7. Является ли
Упражнение 9.6.8. Является ли
Упражнение 9.6.9.
Существует ли над алфавитом {a,b}
такой линейный
язык L,
что язык $$\{ ubv \mid u \in L ,\ uv \in L \}$$
не является контекстно-свободным?
Замечание 9.1.7. В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите $$\Sigma$$. Пусть $$\Sigma \peq \{ a_1 , \ldots , a_n \}$$.
Определение 9.7.2. Через $$\cou$$ будем обозначать функцию из $$\Sigma ^*$$ в $$\mathbb{N} ^n$$, определенную следующим образом: $$\cou ( w ) \mymathrel{\bydef} \lp | w |_{a_1} , \ldots , | w |_{a_n} \rp$$. Аналогично, каждому языку $$L \subseteq \Sigma ^*$$ ставится в соответствие множество $$\cou ( L ) \subseteq \mathbb{N} ^n$$, определенное следующим образом:$$\cou ( L ) \bydef \{ \cou ( w ) \mid w \in L \} .$$
Пример 9.7.3.
Пусть $$\Sigma = \{ a_1 , a_2 \}$$
и L = {a1,a1a2a2,a2a2a1}.
Тогда $$\cou ( L ) = \{ \lp 1 , 0 \rp , \lp 1 , 2 \rp \}$$.
Определение 9.7.4.
Пусть $$B \subseteq \mathbb{N} ^n$$
и $$P \subseteq \mathbb{N} ^n$$.
Тогда через $$\linear ( B , P )$$
обозначается множество$$\{ b + p_1 + \ldots + p_k \mid b \in B ,\ k \geq 0 ,\
p_1 , \ldots , p_k \in P \} .$$
При этом множество B
называется системой предпериодов
множества L(B,P).
Множество P
называется системой периодов
множества L(B,P).
Определение 9.7.5.
Множество $$A \subseteq \mathbb{N} ^n$$
называется линейным
(linear),
если A = L(B,P)
для некоторых конечных множеств B и P.
Определение 9.7.6. Множество $$A \subseteq \mathbb{N} ^n$$ называется полулинейным (semilinear), если оно является объединением конечного числа линейных множеств.
Теорема 9.7.7 (Теорема Парика). Если язык $$L \subseteq \Sigma ^*$$ является контекстно-свободным, то множество $$\cou ( L )$$ является полулинейным.
Доказательство можно найти в [Гин, с. 207-211].
Пример 9.7.8.
Пусть $$\Sigma = \{ a , b \}$$.
Рассмотрим язык $$L \peq \{ a^m b^n \mid m > n \rusor m \mathspace\text{простое}
\}$$.
Можно проверить, что множество $$\cou ( L )$$
не является полулинейным.
Следовательно, язык L
не является контекстно-свободным.
Теорема 9.7.9. Если множество $$A \subseteq \mathbb{N} ^n$$ является полулинейным,
то существует такой автоматный язык L, что $$A = \cou ( L )$$.
Доказательство.
Докажем это для произвольного линейного множества A = L(B,P)
(на полулинейные множества утверждение распространяется
по теореме 3.1.1).
Рассмотрим конечный автомат $$M = \lalg Q , \Sigma , \Delta , I , F \ralg$$,
где Q = {1,2}, I = {1}, F = {2}
и$$\begin{multiline*}
\Delta =
\{ \lp 1 , a_1 ^{k_1} \ldots a_n ^{k_n} , 2 \rp
\mid \lp k_1 , \ldots , k_n \rp \in B \} \cup
\\ \cup
\{ \lp 2 , a_1 ^{k_1} \ldots a_n ^{k_n} , 2 \rp
\mid \lp k_1 , \ldots , k_n \rp \in P \} .
\end{multiline*}$$
Очевидно,
что $$\cou ( L ( M ) ) = \linear ( B , P )$$.
Замечание 9.7.10. Теорема 9.3.1 является следствием теорем 9.7.7 и 9.7.9.
Упражнение 9.7.11. Является ли
В лекции 2 были доказаны лемма
о разрастании и свойства замкнутости класса автоматных языков.
Некоторые из этих теорем имеют аналоги для класса
Лемма о разрастании для
В разделе 9.6 доказывается, что пересечение контекстно-свободного языка с автоматным языком является контекстно-свободным. В сочетании с леммой о разрастании этот факт дает удобное средство, позволяющее во многих задачах доказать, что заданный язык не является контекстно-свободным. Еще одно необходимое условие контекстной свободности сформулировано в разделе 9.7*.
Лемма 9.1.1 (pumping lemma, лемма о разрастании, лемма о накачке,
лемма-насос) Пусть L - контекстно-свободный язык над
алфавитом $$\Sigma$$. Тогда найдется такое положительное целое число p, что для любого слова $$w \in L$$ длины не меньше p можно подобрать слова $$u , v , x , y , z \in \Sigma ^*$$, для которых верно uvxyz = w, $$v y \neq \varepsilon$$
( то есть $$v \neq \varepsilon$$ или $$y \neq
\varepsilon$$ ), $$| v x y | \leq p$$ и $$u v ^i x y ^i z \in L$$ для всех $$i \in \mathbb{N}$$.
Доказательство.
Пусть язык $$L$$
порождается грамматикой в нормальной форме Хомского $$G = \lalg N , \Sigma , P , S \ralg$$.
Индукцией по k
легко доказать, что для любого G
длина 2k-2,
где k - количество вершин в самом длинном пути,
начинающемся в корне дерева и заканчивающемся в некоторой вершине,
помеченной символом из $$\Sigma$$.
Положим p = 2|N|.
Пусть $$w \in L$$
и $$| w | \geq p$$.
Зафиксируем некоторое w
в грамматике G.
Рассмотрим самый длинный путь в этом дереве.
Этот путь содержит не менее |N| + 2
вершин.
Среди них найдутся две вершины
с одинаковыми метками, причем их можно выбрать
среди последних |N| + 2
вершин рассматриваемого пути.
Выберем слова u, v, x, y и z
так, что uvxyz = w,
поддерево с корнем в одной из найденных вершин имеет крону x
и поддерево с корнем в другой найденной вершине имеет крону vxy.
Из того что G -
грамматика в нормальной форме Хомского,
заключаем, что $$v x y \neq x$$.
Неравенство $$| v x y | \leq 2^{ | N | }$$
следует из того, что
самый длинный путь в соответствующем слову vxy
поддереве содержит не более |N| + 2
вершин. Для каждого $$i \in \mathbb{N}$$
можно построить uvixyiz,
комбинируя части исходного
Пример 9.1.2.
Рассмотрим язык $$L = \{ a^n b^n c^n \mid n \geq 0 \}$$
над алфавитом {a,b,c}.
Утверждение леммы 9.1.1
не выполняется ни для какого натурального числа p.
Действительно,
если uvxyz = apbpcp, |vy| > 0
и $$| v x y | \leq p$$,
то |vy|a = 0
или |vy|c = 0.
Следовательно, |uvvxyyz|a = p
или |uvvxyyz|c = p.
Так как |uvvxyyz| > 3p,
то $$u v v x y y z \notin L$$.
Из этого можно заключить, что язык L
не является контекстно-свободным.
Теорема 9.1.3. Каждый контекстно-свободный язык над однобуквенным алфавитом является автоматным.
Доказательство.
Пусть дан L
над алфавитом {a}.
Согласно лемме 9.1.1
найдется такое натуральное число p,
что множество $$\{ k \in \mathbb{N} \mid a^k \in L \}$$
является объединением некоторого семейства
арифметических прогрессий,
причем у каждой прогрессии первый член и шаг не больше числа p.
Так как существует лишь конечное число прогрессий натуральных чисел
с таким ограничением,
рассматриваемое семейство конечно.
Следовательно, язык L
является автоматным
(используем пример 2.1.18).
Упражнение 9.1.4. Является ли
Упражнение 9.1.5. Является ли
Упражнение 9.1.6. Является ли
Упражнение 9.1.7. Является ли {am | m простое}?
Упражнение 9.1.8. Является ли
Упражнение 9.1.9. Является ли
Упражнение 9.1.10. Является ли
Упражнение 9.1.11. Является ли
Упражнение 9.1.12. Является ли
Упражнение 9.1.13. Является ли {akbmcn | k < max(m,n)}?
Упражнение 9.1.14. Является ли {akbmcn | k > max(m,n)}?
Упражнение 9.1.15. Является ли
Упражнение 9.1.16. Какому классу принадлежит язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; T c V , \\ T \; {\to} \; b V , \\ V \; {\to} \; a V a , \\ V \; {\to} \; \varepsilon , \\ ac \; {\to} \; a ? \end{align*}$$
Упражнение 9.1.17. Существуют ли такие
Определение 9.2.1. Линейная грамматика в нормальной форме - это такая линейная грамматика, в которой каждое правило имеет вид $$A \tto \varepsilon$$, $$A \tto a$$, $$A \tto a B$$ или $$A \tto B a$$, где $$A \in N$$, $$B \in N$$, $$a \in \Sigma$$.
Теорема 9.2.2. Каждая линейная грамматика эквивалентна некоторой линейной грамматике в нормальной форме.
Теорема 9.2.3. Если линейный язык не содержит пустого слова, то он порождается некоторой линейной грамматикой в нормальной форме без $$\varepsilon$$ - правил.
Теорема 9.2.4. Язык L является линейным
тогда и только тогда, когда
язык $$L \sminus \{ \varepsilon \}$$ является линейным.
Лемма 9.2.5. Пусть L - линейный язык над алфавитом $$\Sigma$$. Тогда найдется такое положительное целое число p, что для любого слова $$w \in L$$ длины не меньше p можно подобрать слова $$u , v , x , y , z \in \Sigma ^*$$, для которых верно uvxyz = w, $$v y \neq \varepsilon$$
( то есть $$v \neq \varepsilon$$ или $$y \neq
\varepsilon$$ ), $$| u v | + | y z | \leq p$$ и $$u v ^i x y ^i z \in L$$ для всех $$i \in \mathbb{N}$$.
Доказательство.
Пусть язык $$L \sminus \{ \varepsilon \}$$
порождается линейной грамматикой в нормальной форме $$G = \lalg N , \Sigma , P , S \ralg$$
без $$\varepsilon$$ -правил.
Положим p = |N| + 1.
Пусть $$w \in L$$
и $$| w | \geq p$$.
Зафиксируем некоторое w
в грамматике G.
Рассмотрим самый длинный путь в этом дереве
(он начинается с корня и заканчивается некоторым листом,
помеченным символом из $$\Sigma$$ ).
Этот путь содержит не менее |N| + 1
вершин, помеченных элементами N.
Среди первых |N| + 1
вершин рассматриваемого пути
найдутся две вершины
с одинаковыми метками.
Выберем слова u, v, x, y и z
так, что uvxyz = w,
поддерево с корнем в одной из найденных вершин имеет крону x
и поддерево с корнем в другой найденной вершине имеет крону vxy.
Пример 9.2.6.
Рассмотрим язык $$L = \{ a^m b^m a^n b^n \mid m \geq 0 \commaand n \geq 0 \}$$
над алфавитом {a,b}.
Утверждение леммы 9.2.5
не выполняется ни для какого натурального числа p.
Следовательно, язык L
не является линейным.
Упражнение 9.2.7. Какому классу принадлежит язык$$\{ a^n b^n (cd)^m \mid n \geq 1 ,\ m \geq 1 \} ?$$
Упражнение 9.2.8. Какому классу принадлежит язык$$\{ a^k b^l c^m d^n \mid k < n ,\ l > m \} ?$$
Упражнение 9.2.9. Какому классу принадлежит язык$$\{ a^k b^l c^m a^n b^n c^k \mid k \geq 1 ,\ l < m ,\ n \geq 3 \} ?$$
Пример 9.3.1. Пусть $$\Sigma = \{ a , b , c \}$$. Язык $$\{ u c u \reverse \mid u \in \{ a , b \}^* \}$$ является линейным, так как он порождается грамматикой$$\begin{align*} S \; {\to} \; a S a , \\ S \; {\to} \; b S b , \\ S \; {\to} \; c . \end{align*}$$
Пример 9.3.2. Рассмотрим алфавит $$\Sigma = \{ a , b , c \}$$. Язык$$\{ a^m b^n c^k \mid 0 \leq m < n \commaand k \geq 0 \}$$ является линейным, так как он порождается грамматикой$$\begin{align*} S \; {\to} \; S c , T \; {\to} \; a T b , \\ S \; {\to} \; T , T \; {\to} \; T b , \\ T \; {\to} \; b . \end{align*}$$
Теорема 9.3.3. Если L1 и L2 - линейные языки над алфавитом $$\Sigma$$, то $$L_1 \cup L_2$$ тоже линейный язык.
Доказательство.
Пусть язык L1
порождается линейной грамматикой $$\lalg N_1 , \Sigma , P_1 , S_1 \ralg$$
и L2
порождается линейной грамматикой $$\lalg N_2 , \Sigma , P_2 , S_2 \ralg$$,
где $$N_1 \cap N_2 = \varnothing$$.
Тогда $$L_1 \cup L_2$$
порождается грамматикой$$\lalg N_1 \cup N_2 \cup \{ T \},
\Sigma,
P_1 \cup P_2 \cup \{ T \tto S_1 ,\ T \tto S_2 \} ,
T \ralg ,$$
где $$T \notin N_1 \cup N_2 \cup \Sigma$$.
Пример 9.3.4. Рассмотрим алфавит $$\Sigma = \{ a , b , c \}$$. Язык$$L \peq \Sigma ^* \sminus \{ a^n b^n c^n \mid n \geq 0 \}$$ является линейным, поскольку$$L \peq L_1 \cup L_2 \cup ( \Sigma ^* \sminus L_3 ) ,$$ где языки$$L_1 \peq \{ a^m b^n c^k \mid m \neq n \commaand k \geq 0 \} ,\quad L_2 \peq \{ a^m b^n c^k \mid n \neq k \commaand m \geq 0 \}$$ являются линейными, а язык$$L_3 \peq \{ a^m b^n c^k \mid m \geq 0 ,\ n \geq 0 \commaand k \geq 0 \}$$ является автоматным, и можно применить теоремы 9.3.3, 3.2.1, 2.4.1 и лемму 1.5.13.
Упражнение 9.3.5. Пусть $$\Sigma = \{ a , b , c \}$$. Является ли линейным язык $$\Sigma ^* \sminus \{ u c u \mid u \in \{ a , b \}^* \}$$?
Упражнение 9.3.6. Пусть $$\Sigma = \{ a , b , c \}$$. Является ли линейным язык $$\Sigma ^* \sminus \{ u c u \reverse \mid u \in \{ a , b \}^* \}$$?
Упражнение 9.3.7. Найти линейную грамматику, порождающую язык $$\{a,b,c\}^* \sminus L_1$$,
где L1
порождается грамматикой$$\begin{align*}
F \; {\to} \; ba F aaa , \\
F \; {\to} \; baa F b , \\
F \; {\to} \; ba c aaa , \\
F \; {\to} \; baa c b .
\end{align*}$$
Теорема 9.4.1. Если L - контекстно-свободный язык, то L* тоже контекстно-свободный язык.
Доказательство.
Пусть язык L
порождается L*
порождается грамматикой$$\lalg N \cup \{ T \} , \Sigma ,
P \cup \{ T \tto S T ,\ T \tto \varepsilon \} ,
T \ralg ,$$
где $$T \notin N \cup \Sigma$$.
Теорема 9.4.2. Если L1
и L2 - контекстно-свободные языки над алфавитом $$\Sigma$$,
то $$L_1 \cdot L_2$$ тоже контекстно-свободный язык.
Доказательство.
Пусть язык L1
порождается L2
порождается
Теорема 9.4.3. Если L1 и L2 - контекстно-свободные языки над алфавитом $$\Sigma$$, то $$L_1 \cup L_2$$ тоже контекстно-свободный язык.
Доказательство.
Пусть язык L1
порождается L2
порождается
Теорема 9.4.4. Если L - контекстно-свободный язык, то $$L \reverse$$ тоже контекстно-свободный язык.
Упражнение 9.4.5. Является ли
Упражнение 9.4.6.
Найти L1
порождается грамматикой$$\begin{align*}
F \; {\to} \; a , \\
F \; {\to} \; b F , \\
F \; {\to} \; c F F ,
\end{align*}$$
а язык L2
порождается грамматикой$$\begin{align*}
F \; {\to} \; a M , M \; {\to} \; a F , \\
F \; {\to} \; c M , M \; {\to} \; b F , \\
M \; {\to} \; \varepsilon .
\end{align*}$$
Теорема 9.5.1. Неверно, что для любых контекстно-свободных языков L1 и L2 язык $$L_1 \cap L_2$$ тоже контекстно-свободный.
Доказательство. Положим $$L_1 = \{ a^m b^m c^n \mid m \geq 0 \commaand n \geq 0 \}$$ и $$L_2 = \{ a^m b^n c^n \mid m \geq 0 \commaand n \geq 0 \}$$. В примере 9.2.1 было доказано, что язык $$L_1 \cap L_2$$ не является контекстно-свободным.
Теорема 9.5.2. Неверно, что для любого контекстно-свободного языка $$L \subseteq \Sigma ^*$$ язык $$\Sigma ^* \sminus L$$ тоже контекстно-свободный.
Доказательство.
Положим $$L = \Sigma ^* \sminus \{ a^n b^n c^n \mid n \geq 0 \}$$,
где $$\Sigma = \{ a , b , c \}$$.
В примере 9.3.4
было доказано, что язык L
является линейным
(и следовательно, контекстно-свободным).
Упражнение 9.5.3. Является ли
Упражнение 9.5.4. Является ли
Упражнение 9.5.5. Существует ли такой
линейный язык L
над алфавитом {a,b},
что язык $$L \reverse \cap L$$
не является контекстно-свободным?
Теорема 9.6.1. Если L1 - контекстно-свободный язык и L2 - автоматный язык, то язык $$L_1 \cap L_2$$ является контекстно-свободным.
Доказательство.
Пусть $$\lalg N , \Sigma , P , S \ralg$$ -
контекстно-свободная грамматика, порождающая язык L1.
Без ограничения общности можно считать, что множество P
содержит только правила вида $$A \tto a$$
и $$A \tto \alpha$$,
где $$A \in N$$, $$a \in \Sigma$$
и $$\alpha \in N ^*$$
(см. теорему 8.3.3).
Пусть $$\lalg Q , \Sigma , \Delta , I , F \ralg$$ -
конечный автомат,
распознающий язык L_2.
Без ограничения общности можно считать, что
для каждого перехода $$\lp p , x , q \rp \in \Delta$$
выполняется равенство |x| = 1
(см. лемму 2.3.3).
Построим
Пример 9.6.2.
Пусть $$\Sigma = \{ a , b , c \}$$.
Рассмотрим
L1,
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; a , \\
S \; {\to} \; b S , \\
S \; {\to} \; c S S ,
\end{align*}$$
и автоматный язык L2,
распознаваемый конечным автоматом $$M \peq \lalg Q , \Sigma , \Delta , I , F \ralg$$,
где Q = {1,2}, I = {1}, F = {2},$$\Delta = \{
\lp 1 , a , 2 \rp ,\
\lp 1 , c , 2 \rp ,\
\lp 2 , a , 1 \rp ,\
\lp 2 , b , 1 \rp
\} .$$
$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle
\xymatrix {
*=[o][F-]{1}
\ar @`{+/l16mm/} [] ^{}
\ar `ur_r{+/u7mm/}`r_dr{[0,2]}^{c} "1,3"
\ar "1,3" <0.6mm> ^{a}
*=[o][F=]{2}
\ar "1,1" <0.6mm> ^{a}
\ar `dl_l{+/d7mm/}`l_ul{[0,-2]}^{b} "1,1"
}$$
Тогда язык $$L_1 \cap L_2$$
порождается S11, S12, S21
и S22
соответствуют символам $$\lp 1 , S , 1 \rp$$, $$\lp 1 , S , 2 \rp$$, $$\lp 2 , S , 1 \rp$$
и $$\lp 2 , S , 2 \rp$$
из доказательства теоремы 9.6.1.
Теорема 9.6.3*. Если L1 - линейный язык и L2 - автоматный язык, то язык $$L_1 \cap L_2$$ является линейным.
Пример 9.6.4*.
Пусть $$\Sigma = \{ a , b \}$$.
Рассмотрим
линейный язык L1,
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; aaSaa , \\
S \; {\to} \; bSb , \\
S \; {\to} \; \varepsilon ,
\end{align*}$$
и
автоматный язык L2,
распознаваемый конечным автоматом $$M \peq \lalg Q , \Sigma , \Delta , I , F \ralg$$,
где Q = {1,2,3}, I = {1}, F = {3},$$\Delta = \{
\lp 1 , a , 1 \rp ,\
\lp 1 , b , 1 \rp ,\
\lp 1 , a , 2 \rp ,\
\lp 2 , b , 3 \rp ,\
\lp 3 , a , 3 \rp ,\
\lp 3 , b , 3 \rp
\} .$$
$$\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}
\rloop{0,1} ^{a}
\rloop{0,-1} ^{b}
}$$
Тогда язык $$L_1 \cap L_2$$
порождается S11 и S33
на один символ.
Упражнение 9.6.5. Найти L1
порождается грамматикой$$\begin{align*}
F \; {\to} \; a F a , \\
F \; {\to} \; b F b , \\
F \; {\to} \; \varepsilon ,
\end{align*}$$
а язык L2
порождается грамматикой$$\begin{align*}
K \; {\to} \; a M , M \; {\to} \; a K , \\
K \; {\to} \; b K , M \; {\to} \; b K , \\
M \; {\to} \; \varepsilon .
\end{align*}$$
Упражнение 9.6.6. Найти L1
порождается грамматикой$$\begin{align*}
F \; {\to} \; a F a , \\
F \; {\to} \; b F b , \\
F \; {\to} \; \varepsilon ,
\end{align*}$$
а язык L2
порождается грамматикой$$\begin{align*}
K \; {\to} \; a M , M \; {\to} \; a K , \\
K \; {\to} \; b M , K \; {\to} \; \varepsilon . \\
K \; {\to} \; b K ,
\end{align*}$$
Упражнение 9.6.7. Является ли
Упражнение 9.6.8. Является ли
Упражнение 9.6.9.
Существует ли над алфавитом {a,b}
такой линейный
язык L,
что язык $$\{ ubv \mid u \in L ,\ uv \in L \}$$
не является контекстно-свободным?
Замечание 9.1.7. В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите $$\Sigma$$. Пусть $$\Sigma \peq \{ a_1 , \ldots , a_n \}$$.
Определение 9.7.2. Через $$\cou$$ будем обозначать функцию из $$\Sigma ^*$$ в $$\mathbb{N} ^n$$, определенную следующим образом: $$\cou ( w ) \mymathrel{\bydef} \lp | w |_{a_1} , \ldots , | w |_{a_n} \rp$$. Аналогично, каждому языку $$L \subseteq \Sigma ^*$$ ставится в соответствие множество $$\cou ( L ) \subseteq \mathbb{N} ^n$$, определенное следующим образом:$$\cou ( L ) \bydef \{ \cou ( w ) \mid w \in L \} .$$
Пример 9.7.3.
Пусть $$\Sigma = \{ a_1 , a_2 \}$$
и L = {a1,a1a2a2,a2a2a1}.
Тогда $$\cou ( L ) = \{ \lp 1 , 0 \rp , \lp 1 , 2 \rp \}$$.
Определение 9.7.4.
Пусть $$B \subseteq \mathbb{N} ^n$$
и $$P \subseteq \mathbb{N} ^n$$.
Тогда через $$\linear ( B , P )$$
обозначается множество$$\{ b + p_1 + \ldots + p_k \mid b \in B ,\ k \geq 0 ,\
p_1 , \ldots , p_k \in P \} .$$
При этом множество B
называется системой предпериодов
множества L(B,P).
Множество P
называется системой периодов
множества L(B,P).
Определение 9.7.5.
Множество $$A \subseteq \mathbb{N} ^n$$
называется линейным
(linear),
если A = L(B,P)
для некоторых конечных множеств B и P.
Определение 9.7.6. Множество $$A \subseteq \mathbb{N} ^n$$ называется полулинейным (semilinear), если оно является объединением конечного числа линейных множеств.
Теорема 9.7.7 (Теорема Парика). Если язык $$L \subseteq \Sigma ^*$$ является контекстно-свободным, то множество $$\cou ( L )$$ является полулинейным.
Доказательство можно найти в [Гин, с. 207-211].
Пример 9.7.8.
Пусть $$\Sigma = \{ a , b \}$$.
Рассмотрим язык $$L \peq \{ a^m b^n \mid m > n \rusor m \mathspace\text{простое}
\}$$.
Можно проверить, что множество $$\cou ( L )$$
не является полулинейным.
Следовательно, язык L
не является контекстно-свободным.
Теорема 9.7.9. Если множество $$A \subseteq \mathbb{N} ^n$$ является полулинейным,
то существует такой автоматный язык L, что $$A = \cou ( L )$$.
Доказательство.
Докажем это для произвольного линейного множества A = L(B,P)
(на полулинейные множества утверждение распространяется
по теореме 3.1.1).
Рассмотрим конечный автомат $$M = \lalg Q , \Sigma , \Delta , I , F \ralg$$,
где Q = {1,2}, I = {1}, F = {2}
и$$\begin{multiline*}
\Delta =
\{ \lp 1 , a_1 ^{k_1} \ldots a_n ^{k_n} , 2 \rp
\mid \lp k_1 , \ldots , k_n \rp \in B \} \cup
\\ \cup
\{ \lp 2 , a_1 ^{k_1} \ldots a_n ^{k_n} , 2 \rp
\mid \lp k_1 , \ldots , k_n \rp \in P \} .
\end{multiline*}$$
Очевидно,
что $$\cou ( L ( M ) ) = \linear ( B , P )$$.
Замечание 9.7.10. Теорема 9.3.1 является следствием теорем 9.7.7 и 9.7.9.
Упражнение 9.7.11. Является ли
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.