Основная цель этой лекции - доказать, что каждая
В конце лекции доказывается, что каждую
Определение 8.1.1. Пусть дана порождающая грамматика $$G \peq \lalg N , \Sigma , P , S \ralg$$. Символ $$A \in N$$ называется полезным (useful), если существуют такие слова $$\alpha \in \ns ^*$$, $$\beta \in \ns ^*$$ и $$w \in \Sigma ^*$$, что $$S \overstar{\Rightarrow} \alpha A \beta$$ и $$\alpha A \beta \overstar{\Rightarrow} w$$. Символ $$A \in N$$ называется бесполезным (useless), если он не является полезным. Символ $$A \in N$$ называется порождающим (generating), если существует такое слово $$w \in \Sigma ^*$$, что $$A \overstar{\Rightarrow} w$$. Символ $$A \in N$$ называется достижимым если существуют такие слова $$\alpha \in \ns ^*$$ и $$\beta \in \ns ^*$$, что $$S \overstar{\Rightarrow} \alpha A \beta$$.
Лемма 8.1.2. Пусть дана
контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg$$, в которой все символы из N являются порождающими.
Пусть N' - множество всех достижимых символов грамматики G, а P' - множество тех правил из P, которые не содержат ни одного символа из множества $$N \sminus N'$$. Тогда
в контекстно-свободной грамматике $$\lalg N' , \Sigma , P' , S \ralg$$ все символы из N' являются порождающими.
\end{
Теорема 8.1.3. Пусть дана контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg$$ и $$L ( G ) \neq \varnothing$$. Тогда существуют такие множества $$N' \subseteq N$$ и $$P' \subseteq P$$, что в контекстно-свободной грамматике $$\lalg N' , \Sigma , P' , S \ralg$$ нет бесполезных символов и она эквивалентна исходной грамматике.
Доказательство. На первом этапе удалим все непорождающие символы (удалим также каждое правило, содержащее хотя бы один такой символ). На втором этапе из полученной грамматики удалим все недостижимые символы (и правила, их содержащие). Согласно 8.1.2 на втором этапе ни один порождающий символ не может стать непорождающим.
Пример 8.1.4.
Рассмотрим
G
с правилами$$\begin{align*}
S \; {\to} \; U X , W \; {\to} \; Y Z Y , Y \; {\to} \; Y Y \\
S \; {\to} \; V Z , W \; {\to} \; aab , Y \; {\to} \; a U \\
T \; {\to} \; aa , X \; {\to} \; X a , Y \; {\to} \; \varepsilon \\
T \; {\to} \; bb , X \; {\to} \; X b , Z \; {\to} \; W \\
U \; {\to} \; a U a , X \; {\to} \; \varepsilon , Z \; {\to} \; b .\\
U \; {\to} \; b U b , \\
V \; {\to} \; a T b , \\
V \; {\to} \; b T a ,
\end{align*}$$
Удалив четыре правила, содержащие непорождающий символ U,
получим грамматику G1.
В ней символ X
является недостижимым.
Удалив три правила, содержащие X,
получим грамматику G2
с правилами$$\begin{align*}
S \; {\to} \; V Z , W \; {\to} \; Y Z Y , Y \; {\to} \; Y Y , \\
T \; {\to} \; aa , W \; {\to} \; aab , Y \; {\to} \; \varepsilon , \\
T \; {\to} \; bb , Z \; {\to} \; W , \\
V \; {\to} \; a T b , Z \; {\to} \; b .\\
V \; {\to} \; b T a ,
\end{align*}$$
Очевидно,
что L(G) = L(G2)
и грамматика G2
не содержит бесполезных символов.
Упражнение 8.1.5. Найти
Теорема 8.2.1. Пусть язык $$L$$ является контекстно-свободным. Тогда язык $$L \sminus \{ \varepsilon \}$$ порождается некоторой контекстно-свободной грамматикой без $$\varepsilon$$ - правил.
Доказательство.
Пусть дана L.
Проведем серию преобразований множества P.
Если для каких-то $$A \in N$$, $$B \in N$$, $$\alpha \in \ns ^*$$
и $$\beta \in \ns ^*$$
множество P содержит правила $$B \tto \alpha A \beta$$
и $$A \tto \varepsilon$$,
но не содержит правила $$B \tto \alpha \beta$$,
то добавим это правило в P.
Повторяем эту процедуру, пока возможно.
Теперь исключим из множества P
все правила вида $$A \tto \varepsilon$$.
Полученная грамматика порождает язык $$L \sminus \{ \varepsilon \}$$.
Пример 8.2.2.
Рассмотрим язык L,
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; \varepsilon , \\
S \; {\to} \; aSbS .
\end{align*}$$
Язык $$L \sminus \{ \varepsilon \}$$
порождается грамматикой$$\begin{align*}
S \; {\to} \; aSbS , \\
S \; {\to} \; abS , \\
S \; {\to} \; aSb , \\
S \; {\to} \; ab .
\end{align*}$$
Упражнение 8.2.3. Найти
Определение 8.3.1. Грамматика в нормальной форме Хомского
( грамматика в бинарной нормальной форме,
квадратичная грамматика,
Пример 8.3.2. Грамматика$$\begin{align*} S \; {\to} \; RR , A \; {\to} \; a , \\ S \; {\to} \; AB , B \; {\to} \; RB , \\ R \; {\to} \; RR , B \; {\to} \; b \\ R \; {\to} \; AB , \end{align*}$$ является грамматикой в нормальной форме Хомского.
Теорема 8.3.3. Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Хомского.
Доказательство.
Пусть дана
Если правая часть какого-нибудь правила содержит символ S,
то заменим грамматику $$\lalg N , \Sigma , P , S \ralg$$
на грамматику$$\lalg N \cup \{ S_0 \} , \Sigma , P \cup \{ S_0 \tto S \} , S_0 \ralg ,$$
где S0 -
новый символ, не принадлежащий множеству $$N \cup \Sigma$$.
Заменим во всех правилах каждый терминальный символ a
на новый Ta
и добавим к множеству P
правила $$T_a \tto a$$
для всех $$a \in \Sigma$$.
Устраним правила вида $$A \tto \alpha$$,
где $$| \alpha | > 2$$,
заменив каждое из них на ряд более коротких правил
(при этом добавляются новые
Теперь устраним все правила вида $$A \tto \varepsilon$$,
где A не является начальным символом.
Это можно сделать так же, как в доказательстве
теоремы 8.2.1.
Если для каких-то $$A \in N$$, $$B \in N$$
и $$\alpha \in \ns ^*$$
множество P содержит правила $$A \tto B$$
и $$B \tto \alpha$$,
но не содержит правила $$A \tto \alpha$$,
то добавим это правило в P.
Повторяем эту процедуру, пока возможно.
После этого исключим из множества P
все правила вида $$A \tto B$$.
Пример 8.3.4. Грамматика$$\begin{align*} S \; {\to} \; \varepsilon , \\ S \; {\to} \; aUbU , \\ U \; {\to} \; S , \\ U \; {\to} \; ba \end{align*}$$ эквивалентна следующей грамматике в нормальной форме Хомского:$$\begin{align*} S_0 \; {\to} \; \varepsilon , C \; {\to} \; BU , \\ S_0 \; {\to} \; AD , C \; {\to} \; b , \\ D \; {\to} \; UC , U \; {\to} \; BA , \\ D \; {\to} \; BU , U \; {\to} \; AD , \\ D \; {\to} \; b , A \; {\to} \; a , \\ B \; {\to} \; b . \end{align*}$$
Теорема 8.3.5. Если контекстно-свободный язык не содержит пустого слова, то он порождается некоторой грамматикой, в которой каждое правило имеет один из следующих двух видов: $$A \tto a$$, $$A \tto B C$$, где $$A \in N$$, $$B \in N \sminus \{ S \}$$, $$C \in N \sminus \{ S \}$$, $$a \in \Sigma$$.
Упражнение 8.3.6. Найти
Определение 8.4.1. Грамматика в нормальной форме Грейбах
(
Пример 8.4.2. Грамматика$$\begin{align*} S \; {\to} \; aST , \\ S \; {\to} \; aT , \\ T \; {\to} \; bS , \\ T \; {\to} \; b \end{align*}$$ является грамматикой в нормальной форме Грейбах.
Замечание 8.4.3. Некоторые авторы разрешают в грамматиках в нормальной форме Грейбах использовать также правила вида $$A \tto a \beta$$, где $$A \in N$$, $$a \in \Sigma$$, $$\beta \in N^*$$ (в определении 8.4.1 разрешены, только если $$| \beta | \leq 2$$ ).
Теорема 8.4.4. Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Грейбах.
Доказательство.
Докажем теорему для
Введем |N|2
новых вспомогательных символов, соответствующих упорядоченным парам
из множества $$N \times N$$.
Новый символ, соответствующий паре $$\lp A , B \rp$$,
будем обозначать (A\B).
Построим грамматику "почти в нормальной форме Грейбах" $$\gdd{ G } = \lalg \gdd{ N } , \Sigma , \gdd{ P } , S \ralg$$,
положив $$\gdd{ N } = N \cup \{ ( A \li B ) \mid A \in N \commaand B \in N \}$$
и$$\begin{align*}
\gdd{ P } = \{ ( A \li A ) \tto \varepsilon \mid A \in N \} \cup {} \\
\myqquad \cup
\{ ( C \li E ) \squeeze{\tto} A ( A \li D ) ( B \li E ) \squeeze{\mid}
( B \squeeze{\tto} C D ) \squeeze{\in} P ,\ A \squeeze{\in} N
\commaand E \squeeze{\in} N \} \cup {} \\
\myqquad \cup
\{ A \tto a \mid
( A \tto a ) \in P
\} \cup {} \\
\myqquad \cup
\{ S \tto a ( A \li S ) \mid
( A \tto a ) \in P \}
.
\end{align*}$$
Если в этой грамматике заменить$$\begin{multiline*}
\{ ( C \li E ) \tto A ( A \li D ) ( B \li E ) \mid
( B \tto C D ) \in P ,\ A \in N \commaand E \in N \} \cup {} \\
\cup
\{ A \tto a \mid
( A \tto a ) \in P \}
\end{multiline*}$$
на$$\{ ( C \li E ) \tto a ( A \li D ) ( B \li E ) \mid
( B \squeeze{\tto} C D ) \in P ,\
( A \squeeze{\tto} a ) \in P \commaand
E \in N \} ,$$
получим эквивалентную ей грамматику в нормальной форме Грейбах.
Осталось лишь доказать, что $$L ( G ) = L ( \gdd{ G } )$$.
Сначала проверим индукцией по длине слова $$\gamma \in N ^*$$,
что если $$F \overstar{\myunderset{ G }{ \Rightarrow }} C \gamma$$,
то $$( C \li E ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }}
\gamma ( F \li E )$$
для любого $$E \in N$$.
Чтобы провести
Докажем теперь, что для любого $$\gamma \in N ^*$$
равносильны утверждения $$F \overstar{\myunderset{ G }{ \Rightarrow }} C \gamma$$
и $$( C \li F ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }}
\gamma$$.
В одну сторону это следует из только что доказанного.
Доказательство того,
что если $$( C \li F ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }}
\gamma$$,
то $$F \overstar{\myunderset{ G }{ \Rightarrow }} C \gamma$$,
проведем
индукцией по длине слова $$\gamma \in N ^*$$.
Чтобы провести
Теперь убедимся, что $$L ( G ) = L ( \gdd{ G } )$$. Рассмотрим произвольное слово $$a_0 a_1 \ldots a_m$$, где $$m \geq 0$$ и $$a_i \in \Sigma$$ для всех $$i \leq m$$. Пусть$$S \overstar{\myunderset{ G }{ \Rightarrow }} A_0 A_1 \ldots A_m \overstar{\myunderset{ G }{ \Rightarrow }} a_0 a_1 \ldots a_m ,$$ где $$A_i \in N$$ для всех $$i \leq m$$. Тогда$$S \myunderset{\gdd{ G }}{ \Rightarrow } a_0 ( A_0 \li S ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }} a_0 A_1 \ldots A_m \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }} a_0 a_1 \ldots a_m .$$ Обратно, пусть$$S \myunderset{\gdd{ G }}{ \Rightarrow } a_0 ( A_0 \li S ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }} a_0 A_1 \ldots A_m \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }} a_0 a_1 \ldots a_m ,$$ где $$A_i \in N$$ для всех $$i \leq m$$. Тогда$$S \overstar{\myunderset{ G }{ \Rightarrow }} A_0 A_1 \ldots A_m \overstar{\myunderset{ G }{ \Rightarrow }} a_0 a_1 \ldots a_m .$$
Пример 8.4.5.
Грамматика$$\begin{align*}
S \; {\to} \; RT , U \; {\to} \; VT , \\
T \; {\to} \; b , V \; {\to} \; RT , \\
T \; {\to} \; UR , R \; {\to} \; a
\end{align*}$$
эквивалентна следующей грамматике в нормальной форме Грейбах:$$\begin{align*}
S \; {\to} \; aC , E \; {\to} \; aDF , \\
C \; {\to} \; aD , E \; {\to} \; bF , \\
C \; {\to} \; b , F \; {\to} \; a . \\
D \; {\to} \; aDE , \\
D \; {\to} \; bE ,
\end{align*}$$
Здесь C, D, E и F
соответствуют символам (A\S), (A\T), (V\T)
и (U\T)
из доказательства теоремы 8.4.4
(удален 21 бесполезный символ).
Теорема 8.4.6. Пусть язык L контекстно-свободный. Тогда язык $$L \sminus \{ \varepsilon \}$$ порождается некоторой грамматикой в нормальной форме Грейбах без $$\varepsilon$$ - правил.
Пример 8.4.7. Грамматика$$\begin{align*} S \; {\to} \; aR , \\ R \; {\to} \; bRT , \\ R \; {\to} \; \varepsilon , \\ T \; {\to} \; cSR , \\ T \; {\to} \; \varepsilon \end{align*}$$ эквивалентна следующей грамматике в нормальной форме Грейбах без $$\varepsilon$$ -правил:$$\begin{align*} S \; {\to} \; aR , R \; {\to} \; bRT , T \; {\to} \; cSR , \\ S \; {\to} \; a , R \; {\to} \; bT , T \; {\to} \; cS . \\ R \; {\to} \; bR , \\ R \; {\to} \; b , \end{align*}$$
Упражнение 8.4.8. Найти
Упражнение 8.4.9. Найти
Упражнение 8.4.10. Найти
Упражнение 8.4.11. Найти
Основная цель этой лекции - доказать, что каждая
В конце лекции доказывается, что каждую
Определение 8.1.1. Пусть дана порождающая грамматика $$G \peq \lalg N , \Sigma , P , S \ralg$$. Символ $$A \in N$$ называется полезным (useful), если существуют такие слова $$\alpha \in \ns ^*$$, $$\beta \in \ns ^*$$ и $$w \in \Sigma ^*$$, что $$S \overstar{\Rightarrow} \alpha A \beta$$ и $$\alpha A \beta \overstar{\Rightarrow} w$$. Символ $$A \in N$$ называется бесполезным (useless), если он не является полезным. Символ $$A \in N$$ называется порождающим (generating), если существует такое слово $$w \in \Sigma ^*$$, что $$A \overstar{\Rightarrow} w$$. Символ $$A \in N$$ называется достижимым если существуют такие слова $$\alpha \in \ns ^*$$ и $$\beta \in \ns ^*$$, что $$S \overstar{\Rightarrow} \alpha A \beta$$.
Лемма 8.1.2. Пусть дана
контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg$$, в которой все символы из N являются порождающими.
Пусть N' - множество всех достижимых символов грамматики G, а P' - множество тех правил из P, которые не содержат ни одного символа из множества $$N \sminus N'$$. Тогда
в контекстно-свободной грамматике $$\lalg N' , \Sigma , P' , S \ralg$$ все символы из N' являются порождающими.
\end{
Теорема 8.1.3. Пусть дана контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg$$ и $$L ( G ) \neq \varnothing$$. Тогда существуют такие множества $$N' \subseteq N$$ и $$P' \subseteq P$$, что в контекстно-свободной грамматике $$\lalg N' , \Sigma , P' , S \ralg$$ нет бесполезных символов и она эквивалентна исходной грамматике.
Доказательство. На первом этапе удалим все непорождающие символы (удалим также каждое правило, содержащее хотя бы один такой символ). На втором этапе из полученной грамматики удалим все недостижимые символы (и правила, их содержащие). Согласно 8.1.2 на втором этапе ни один порождающий символ не может стать непорождающим.
Пример 8.1.4.
Рассмотрим
G
с правилами$$\begin{align*}
S \; {\to} \; U X , W \; {\to} \; Y Z Y , Y \; {\to} \; Y Y \\
S \; {\to} \; V Z , W \; {\to} \; aab , Y \; {\to} \; a U \\
T \; {\to} \; aa , X \; {\to} \; X a , Y \; {\to} \; \varepsilon \\
T \; {\to} \; bb , X \; {\to} \; X b , Z \; {\to} \; W \\
U \; {\to} \; a U a , X \; {\to} \; \varepsilon , Z \; {\to} \; b .\\
U \; {\to} \; b U b , \\
V \; {\to} \; a T b , \\
V \; {\to} \; b T a ,
\end{align*}$$
Удалив четыре правила, содержащие непорождающий символ U,
получим грамматику G1.
В ней символ X
является недостижимым.
Удалив три правила, содержащие X,
получим грамматику G2
с правилами$$\begin{align*}
S \; {\to} \; V Z , W \; {\to} \; Y Z Y , Y \; {\to} \; Y Y , \\
T \; {\to} \; aa , W \; {\to} \; aab , Y \; {\to} \; \varepsilon , \\
T \; {\to} \; bb , Z \; {\to} \; W , \\
V \; {\to} \; a T b , Z \; {\to} \; b .\\
V \; {\to} \; b T a ,
\end{align*}$$
Очевидно,
что L(G) = L(G2)
и грамматика G2
не содержит бесполезных символов.
Упражнение 8.1.5. Найти
Теорема 8.2.1. Пусть язык $$L$$ является контекстно-свободным. Тогда язык $$L \sminus \{ \varepsilon \}$$ порождается некоторой контекстно-свободной грамматикой без $$\varepsilon$$ - правил.
Доказательство.
Пусть дана L.
Проведем серию преобразований множества P.
Если для каких-то $$A \in N$$, $$B \in N$$, $$\alpha \in \ns ^*$$
и $$\beta \in \ns ^*$$
множество P содержит правила $$B \tto \alpha A \beta$$
и $$A \tto \varepsilon$$,
но не содержит правила $$B \tto \alpha \beta$$,
то добавим это правило в P.
Повторяем эту процедуру, пока возможно.
Теперь исключим из множества P
все правила вида $$A \tto \varepsilon$$.
Полученная грамматика порождает язык $$L \sminus \{ \varepsilon \}$$.
Пример 8.2.2.
Рассмотрим язык L,
порождаемый грамматикой$$\begin{align*}
S \; {\to} \; \varepsilon , \\
S \; {\to} \; aSbS .
\end{align*}$$
Язык $$L \sminus \{ \varepsilon \}$$
порождается грамматикой$$\begin{align*}
S \; {\to} \; aSbS , \\
S \; {\to} \; abS , \\
S \; {\to} \; aSb , \\
S \; {\to} \; ab .
\end{align*}$$
Упражнение 8.2.3. Найти
Определение 8.3.1. Грамматика в нормальной форме Хомского
( грамматика в бинарной нормальной форме,
квадратичная грамматика,
Пример 8.3.2. Грамматика$$\begin{align*} S \; {\to} \; RR , A \; {\to} \; a , \\ S \; {\to} \; AB , B \; {\to} \; RB , \\ R \; {\to} \; RR , B \; {\to} \; b \\ R \; {\to} \; AB , \end{align*}$$ является грамматикой в нормальной форме Хомского.
Теорема 8.3.3. Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Хомского.
Доказательство.
Пусть дана
Если правая часть какого-нибудь правила содержит символ S,
то заменим грамматику $$\lalg N , \Sigma , P , S \ralg$$
на грамматику$$\lalg N \cup \{ S_0 \} , \Sigma , P \cup \{ S_0 \tto S \} , S_0 \ralg ,$$
где S0 -
новый символ, не принадлежащий множеству $$N \cup \Sigma$$.
Заменим во всех правилах каждый терминальный символ a
на новый Ta
и добавим к множеству P
правила $$T_a \tto a$$
для всех $$a \in \Sigma$$.
Устраним правила вида $$A \tto \alpha$$,
где $$| \alpha | > 2$$,
заменив каждое из них на ряд более коротких правил
(при этом добавляются новые
Теперь устраним все правила вида $$A \tto \varepsilon$$,
где A не является начальным символом.
Это можно сделать так же, как в доказательстве
теоремы 8.2.1.
Если для каких-то $$A \in N$$, $$B \in N$$
и $$\alpha \in \ns ^*$$
множество P содержит правила $$A \tto B$$
и $$B \tto \alpha$$,
но не содержит правила $$A \tto \alpha$$,
то добавим это правило в P.
Повторяем эту процедуру, пока возможно.
После этого исключим из множества P
все правила вида $$A \tto B$$.
Пример 8.3.4. Грамматика$$\begin{align*} S \; {\to} \; \varepsilon , \\ S \; {\to} \; aUbU , \\ U \; {\to} \; S , \\ U \; {\to} \; ba \end{align*}$$ эквивалентна следующей грамматике в нормальной форме Хомского:$$\begin{align*} S_0 \; {\to} \; \varepsilon , C \; {\to} \; BU , \\ S_0 \; {\to} \; AD , C \; {\to} \; b , \\ D \; {\to} \; UC , U \; {\to} \; BA , \\ D \; {\to} \; BU , U \; {\to} \; AD , \\ D \; {\to} \; b , A \; {\to} \; a , \\ B \; {\to} \; b . \end{align*}$$
Теорема 8.3.5. Если контекстно-свободный язык не содержит пустого слова, то он порождается некоторой грамматикой, в которой каждое правило имеет один из следующих двух видов: $$A \tto a$$, $$A \tto B C$$, где $$A \in N$$, $$B \in N \sminus \{ S \}$$, $$C \in N \sminus \{ S \}$$, $$a \in \Sigma$$.
Упражнение 8.3.6. Найти
Определение 8.4.1. Грамматика в нормальной форме Грейбах
(
Пример 8.4.2. Грамматика$$\begin{align*} S \; {\to} \; aST , \\ S \; {\to} \; aT , \\ T \; {\to} \; bS , \\ T \; {\to} \; b \end{align*}$$ является грамматикой в нормальной форме Грейбах.
Замечание 8.4.3. Некоторые авторы разрешают в грамматиках в нормальной форме Грейбах использовать также правила вида $$A \tto a \beta$$, где $$A \in N$$, $$a \in \Sigma$$, $$\beta \in N^*$$ (в определении 8.4.1 разрешены, только если $$| \beta | \leq 2$$ ).
Теорема 8.4.4. Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Грейбах.
Доказательство.
Докажем теорему для
Введем |N|2
новых вспомогательных символов, соответствующих упорядоченным парам
из множества $$N \times N$$.
Новый символ, соответствующий паре $$\lp A , B \rp$$,
будем обозначать (A\B).
Построим грамматику "почти в нормальной форме Грейбах" $$\gdd{ G } = \lalg \gdd{ N } , \Sigma , \gdd{ P } , S \ralg$$,
положив $$\gdd{ N } = N \cup \{ ( A \li B ) \mid A \in N \commaand B \in N \}$$
и$$\begin{align*}
\gdd{ P } = \{ ( A \li A ) \tto \varepsilon \mid A \in N \} \cup {} \\
\myqquad \cup
\{ ( C \li E ) \squeeze{\tto} A ( A \li D ) ( B \li E ) \squeeze{\mid}
( B \squeeze{\tto} C D ) \squeeze{\in} P ,\ A \squeeze{\in} N
\commaand E \squeeze{\in} N \} \cup {} \\
\myqquad \cup
\{ A \tto a \mid
( A \tto a ) \in P
\} \cup {} \\
\myqquad \cup
\{ S \tto a ( A \li S ) \mid
( A \tto a ) \in P \}
.
\end{align*}$$
Если в этой грамматике заменить$$\begin{multiline*}
\{ ( C \li E ) \tto A ( A \li D ) ( B \li E ) \mid
( B \tto C D ) \in P ,\ A \in N \commaand E \in N \} \cup {} \\
\cup
\{ A \tto a \mid
( A \tto a ) \in P \}
\end{multiline*}$$
на$$\{ ( C \li E ) \tto a ( A \li D ) ( B \li E ) \mid
( B \squeeze{\tto} C D ) \in P ,\
( A \squeeze{\tto} a ) \in P \commaand
E \in N \} ,$$
получим эквивалентную ей грамматику в нормальной форме Грейбах.
Осталось лишь доказать, что $$L ( G ) = L ( \gdd{ G } )$$.
Сначала проверим индукцией по длине слова $$\gamma \in N ^*$$,
что если $$F \overstar{\myunderset{ G }{ \Rightarrow }} C \gamma$$,
то $$( C \li E ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }}
\gamma ( F \li E )$$
для любого $$E \in N$$.
Чтобы провести
Докажем теперь, что для любого $$\gamma \in N ^*$$
равносильны утверждения $$F \overstar{\myunderset{ G }{ \Rightarrow }} C \gamma$$
и $$( C \li F ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }}
\gamma$$.
В одну сторону это следует из только что доказанного.
Доказательство того,
что если $$( C \li F ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }}
\gamma$$,
то $$F \overstar{\myunderset{ G }{ \Rightarrow }} C \gamma$$,
проведем
индукцией по длине слова $$\gamma \in N ^*$$.
Чтобы провести
Теперь убедимся, что $$L ( G ) = L ( \gdd{ G } )$$. Рассмотрим произвольное слово $$a_0 a_1 \ldots a_m$$, где $$m \geq 0$$ и $$a_i \in \Sigma$$ для всех $$i \leq m$$. Пусть$$S \overstar{\myunderset{ G }{ \Rightarrow }} A_0 A_1 \ldots A_m \overstar{\myunderset{ G }{ \Rightarrow }} a_0 a_1 \ldots a_m ,$$ где $$A_i \in N$$ для всех $$i \leq m$$. Тогда$$S \myunderset{\gdd{ G }}{ \Rightarrow } a_0 ( A_0 \li S ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }} a_0 A_1 \ldots A_m \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }} a_0 a_1 \ldots a_m .$$ Обратно, пусть$$S \myunderset{\gdd{ G }}{ \Rightarrow } a_0 ( A_0 \li S ) \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }} a_0 A_1 \ldots A_m \overstar{\myunderset{\gdd{ G }}{ \Rightarrow }} a_0 a_1 \ldots a_m ,$$ где $$A_i \in N$$ для всех $$i \leq m$$. Тогда$$S \overstar{\myunderset{ G }{ \Rightarrow }} A_0 A_1 \ldots A_m \overstar{\myunderset{ G }{ \Rightarrow }} a_0 a_1 \ldots a_m .$$
Пример 8.4.5.
Грамматика$$\begin{align*}
S \; {\to} \; RT , U \; {\to} \; VT , \\
T \; {\to} \; b , V \; {\to} \; RT , \\
T \; {\to} \; UR , R \; {\to} \; a
\end{align*}$$
эквивалентна следующей грамматике в нормальной форме Грейбах:$$\begin{align*}
S \; {\to} \; aC , E \; {\to} \; aDF , \\
C \; {\to} \; aD , E \; {\to} \; bF , \\
C \; {\to} \; b , F \; {\to} \; a . \\
D \; {\to} \; aDE , \\
D \; {\to} \; bE ,
\end{align*}$$
Здесь C, D, E и F
соответствуют символам (A\S), (A\T), (V\T)
и (U\T)
из доказательства теоремы 8.4.4
(удален 21 бесполезный символ).
Теорема 8.4.6. Пусть язык L контекстно-свободный. Тогда язык $$L \sminus \{ \varepsilon \}$$ порождается некоторой грамматикой в нормальной форме Грейбах без $$\varepsilon$$ - правил.
Пример 8.4.7. Грамматика$$\begin{align*} S \; {\to} \; aR , \\ R \; {\to} \; bRT , \\ R \; {\to} \; \varepsilon , \\ T \; {\to} \; cSR , \\ T \; {\to} \; \varepsilon \end{align*}$$ эквивалентна следующей грамматике в нормальной форме Грейбах без $$\varepsilon$$ -правил:$$\begin{align*} S \; {\to} \; aR , R \; {\to} \; bRT , T \; {\to} \; cSR , \\ S \; {\to} \; a , R \; {\to} \; bT , T \; {\to} \; cS . \\ R \; {\to} \; bR , \\ R \; {\to} \; b , \end{align*}$$
Упражнение 8.4.8. Найти
Упражнение 8.4.9. Найти
Упражнение 8.4.10. Найти
Упражнение 8.4.11. Найти
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.