Слова, языки и грамматики

1.2. Операции над языками

Определение 1.2.1. Пусть $$L_1 , L_2 \subseteq \Sigma ^*$$. Тогда$$L_1 \cdot L_2 \rightleftharpoons \{ x y \mid x \in L_1, \; y \in L_2 \} .$$ Язык $$L_1 \cdot L_2$$ называется конкатенацией языков L1 и L2.

Пример 1.2.2. Если L1 = {a,abb} и L2 = {bbc,c}, то $$L_1 \cdot L_2 = \{ ac , abbc , abbbbc \}$$.

Упражнение 1.2.3. При каких положительных целых числах k, l, m, n существуют алфавит $$\Sigma$$, язык $$L_1 \subseteq \Sigma^*$$ и язык $$L_2 \subseteq \Sigma^*$$, удовлетворяющие условиям $$| \Sigma | = k$$, |L1| = l, |L2| = m, $$| L_1 \cdot L_2 | = n$$

Определение 1.2.4. Пусть $$L \subseteq \Sigma ^*$$. Тогда$$\begin{align*} L^0 \rightleftharpoons \{ \varepsilon \} ,\\ L^n \rightleftharpoons \underbrace{ L \cdot \ldots \cdot L }_{n \; \text{раз}} \,, \; \text{если} \; n > 0 . \end{align*}$$

Пример 1.2.5. Если L = {akbal | 0 < k < l}, то L2 = {akbalbam | 0 < k < l - 1, m > 1}.

Упражнение 1.2.6. Пусть $$\Sigma = \{ a , b \}$$ и L = {aa,ab}. Найти L3.

Определение 1.2.7. Итерацией языка (Kleene closure) языка L (обозначение L* ) называется язык$$\bigcup \limits_{ n \in \mathbb{N} } L^n.$$ Эта операция называется также звездочкой Клини (Kleene star, star operation).

Пример 1.2.8. Если $$\Sigma = \{ a , b \}$$ и L = {aa,ab,ba,bb}, то$$L^* = \{ w \in \Sigma ^* \mid | w | \; \vdots \; 2 \} .$$

Упражнение 1.2.9. Пусть $$\Sigma = \{ a , b , c , d \}$$ и$$L = \{ w \in \Sigma ^* \mid | w |_a = 1, \; | w |_c = 1 \} .$$ Верно ли, что $$abcdcacdcabbacba \in L^*$$

Упражнение 1.2.10. Существует ли такой язык L, что выполняется неравенство $$L^* \neq \{ x^n \mid x \in L ,\ n \geqslant 0 \}$$

Определение 1.2.11. Обращением или зеркальным образом слова w (обозначается wR ) называется слово, в котором символы, составляющие слово w, идут в обратном порядке.

Пример 1.2.12. Если w = baaca, то wR = acaab.

Определение 1.2.13. Пусть $$L \subseteq \Sigma ^*$$. Тогда$$L \reverse \rightleftharpoons \{ w \reverse \mid w \in L \} .$$ Язык LR называется обращением языка L.

Упражнение 1.2.14. Существует ли такой язык L, что выполняется неравенство $$(L \reverse)^* \neq (L^*) \reverse$$?

Определение 1.2.15. Говорят, что слово x - префикс ( начало ) слова y (обозначение $$x \sqsubset y$$ ), если y = xu для некоторого слова u.

Пример 1.2.16. Очевидно, что $$\varepsilon \sqsubset baa$$, $$b \sqsubset baa$$, $$ba \sqsubset baa$$ и $$baa \sqsubset baa$$.

Определение 1.2.17. Пусть $$L \subseteq \Sigma ^*$$. Тогда через Pref(L) обозначается множество, состоящее из всех префиксов слов языка L:$$\mathrm{Pref} ( L ) \rightleftharpoons \{ x \mid ( \exists y \in L )\, x \sqsubset y \} .$$ Множество Pref(L) называется множеством префиксов языка L.

Определение 1.2.18 Говорят, что слово x - суффикс ( конец ) слова y (обозначение $$x \sqsupset y$$ ), если y = ux для некоторого слова u.

Определение 1.2.19. Пусть $$L \subseteq \Sigma ^*$$. Тогда через Suf(L) обозначается множество, состоящее из всех суффиксов слов языка L:$$\mathrm{Suf} ( L ) \rightleftharpoons \{ x \mid ( \exists y \in L )\, x \sqsupset y \} .$$ Множество Suf(L) называется множеством суффиксов языка L.

Определение 1.2.20. Говорят, что слово x - подслово (substring) слова y, если y = uxv для некоторых слов u и v.

Определение 1.2.21. Пусть $$L \subseteq \Sigma ^*$$. Тогда через Subw(L) обозначается множество, состоящее из всех подслов слов языка L. Множество Subw(L) называется множеством подслов языка L.

Определение 1.2.22. Слово a1a2...an (длины $$n \geqslant 0$$ ) называется подпоследовательностью (subsequence) слова y, если существуют такие слова u0, u1, ..., un, что u0a1u1a2...anun = y.

Замечание 1.2.23. Все подслова слова y являются также подпоследовательностями слова y.

Определение 1.2.24. Пусть $$L \subseteq \Sigma ^*$$. Тогда через Subseq(L) обозначается множество, состоящее из всех подпоследовательностей слов языка L. Множество Subseq(L) называется множеством подпоследовательностей языка L.

Пример 1.2.25. Рассмотрим язык L = {cba, c} над алфавитом {a, b, c}. Очевидно, что $$\mathrm{Subseq} ( L ) = \{ \varepsilon , a , b , c , ba , ca , cb , cba \}$$.

Определение 1.2.26. Функция $$f \colon K \to L$$ называется биекцией (bijection), если каждый элемент множества L является образом ровно одного элемента множества K (относительно функции f ).

Определение 1.2.27. Множества K и L называются равномощными (of equal cardinality), если существует биекция из K в L.

Упражнение 1.2.28. Существуют ли такие языки L1 и L2, что языки $$L_1 \cdot ( L_2 \reverse )$$ и $$L_1 \reverse \cdot L_2$$ неравномощны?

Упражнение 1.2.29. Существуют ли такие языки L1 и L2, что языки $$L_1 \reverse \cdot L_2$$ и $$L_2 \reverse \cdot L_1$$ неравномощны?

1.3. Гомоморфизмы

Определение 1.3.1. Пусть $$\Sigma_1$$ и $$\Sigma_2$$ - алфавиты. Если отображение $$h \colon \Sigma_1^* \rightarrow \Sigma_2^*$$ удовлетворяет условию $$h ( x \cdot y ) = h ( x ) \cdot h ( y )$$ для всех слов $$x \in \Sigma_1^*$$ и $$y \in \Sigma_1^*$$, то отображение h называется гомоморфизмом ( морфизмом ).

Замечание 1.3.2. Можно доказать, что если $$h$$ - гомоморфизм, то $$h ( \varepsilon ) = \varepsilon$$.

Замечание 1.3.3. Пусть $$\Sigma_1 = \{ a , b \}$$ и $$\Sigma_2 = \{ c \}$$. Тогда отображение $$h \colon \Sigma_1^* \rightarrow \Sigma_2^*$$, заданное равенством $$h ( w ) = c^{2 | w |}$$, является гомоморфизмом.

Замечание 1.3.4. Каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах.

Замечание 1.3.5. Если $$h \colon \Sigma_1^* \rightarrow \Sigma_2^*$$ - гомоморфизм и $$L \subseteq \Sigma_1^*$$, то через h(L) обозначается язык $$\{ h ( w ) \mid w \in L \}$$.

Пример 1.3.6. Пусть $$\Sigma = \{ a , b \}$$ и гомоморфизм $$h \colon \Sigma ^* \rightarrow \Sigma ^*$$ задан равенствами h(a) = abba и $$h ( b ) = \varepsilon$$. Тогда$$h ( \{ baa , bb \} ) = \{ abbaabba , \varepsilon \} .$$

Определение 1.3.7. Если $$h \colon \Sigma_1^* \rightarrow \Sigma_2^*$$ - гомоморфизм и $$L \subseteq \Sigma_2^*$$, то через h-1(L) обозначается язык $$\{ w \in \Sigma_1^* \mid h ( w ) \in L \}$$.

Пример 1.3.8. Рассмотрим алфавит $$\Sigma = \{ a , b \}$$. Пусть гомоморфизм $$h \colon \Sigma ^* \rightarrow \Sigma ^*$$ задан равенствами h(a) = ab и h(b) = abb. Тогда$$h^{-1} ( \{ \varepsilon , abbb , abbab , ababab \} ) = \{ \varepsilon , ba , aaa \} .$$

Упражнение 1.3.9. Пусть $$\Sigma = \{a,b,c,d\}$$. Существует ли такой гомоморфизм $$h \colon \Sigma^* \rightarrow \Sigma^*$$, что h(abc) = bac и h(da) = ba?

Упражнение 1.3.10. Существуют ли такой язык $$L \subseteq \{a,b\}^+$$ и такой гомоморфизм $$h \colon \{a,b\}^* \rightarrow \{a,b\}^*$$, что $$h(h^{-1}(L)) = L$$ и $$h^{-1}(h(L)) \neq L$$?

Упражнение 1.3.11. Пусть $$\Sigma = \{a,b\}$$. Существует ли такой гомоморфизм $$h \colon \Sigma ^* \rightarrow \Sigma ^*$$, что $$h(h^{-1}(\{ \varepsilon \})) = \{ \varepsilon \}$$ и $$h^{-1}(h(\{ \varepsilon \})) \neq \{ \varepsilon \}$$?

Упражнение 1.3.12. Существуют ли такой язык $$L \subseteq \{a,b\}^+$$ и такой гомоморфизм $$h \colon \{a,b\}^* \rightarrow \{a,b\}^*$$, что $$h(h^{-1}(L)) \neq L$$ и $$h^{-1}(h(L)) = L$$?

Упражнение 1.3.13. Пусть $$h \colon \{a,b,c\}^* \rightarrow \{a,b\}^*$$ - гомоморфизм, заданный соотношениями h(a) = a, h(b) = ba, h(c) = bb. Существуют ли такие слова u и v, что |u|<|v| и |h(u)|>|h(v)|?

1.4. Порождающие грамматики

Определение 1.4.1. Порождающей грамматикой ( грамматикой типа 0, generative grammar, rewrite grammar) называется четверка $$G \rightleftharpoons \langle N , \Sigma , P , S \rangle$$, где N и $$\Sigma$$ - конечные алфавиты, $$N \cap \Sigma = \varnothing$$, $$P \subset (N \cup \Sigma) ^+ \times (N \cup \Sigma) ^*$$, P конечно и $$S \in N$$. Здесь $$\Sigma$$ - основной алфавит ( терминальный алфавит ), его элементы называются терминальными символами или терминалами (terminal), N - вспомогательный алфавит ( нетерминальный алфавит ), его элементы называются нетерминальными символами, нетерминалами, вспомогательными символами или переменными (nonterminal, variable), S - начальный символ ( аксиома, start symbol). Пары $$( \alpha , \beta ) \in P$$ называются правилами подстановки, просто правилами или продукциями (rewriting rule, production) и записываются в виде $$\alpha \rightarrow \beta$$.

Пример 1.4.2. Пусть даны множества N = {S}, $$\Sigma = \{ a , b , c \}$$, $$P = \{ S \rightarrow acSbcS ,\ cS \rightarrow \varepsilon \}$$. Тогда $$\langle N , \Sigma , P , S \rangle$$ является порождающей грамматикой.

Замечание 1.4.3. Будем обозначать элементы множества $$\Sigma$$ строчными буквами из начала латинского алфавита, а элементы множества N - заглавными латинскими буквами. Обычно в примерах мы будем задавать грамматику в виде списка правил, подразумевая, что алфавит N составляют все заглавные буквы, встречающиеся в правилах, а алфавит $$\Sigma$$ - все строчные буквы, встречающиеся в правилах. При этом правила порождающей грамматики записывают в таком порядке, что левая часть первого правила есть начальный символ S.

Замечание 1.4.4. Для обозначения n правил с одинаковыми левыми частями $$\alpha \rightarrow \beta_1,\ldots, \alpha \rightarrow \beta_n$$ часто используют сокращенную запись $$\alpha \rightarrow \beta_1 \mid \ldots \mid \beta_n$$.

Определение 1.4.5. Пусть дана грамматика G. Пишем $$\phi \underset { G } {\Rightarrow } \psi$$, если $$\phi = \eta \alpha \theta$$, $$\psi = \eta \beta \theta$$ и $$( \alpha \rightarrow \beta ) \in P$$ для некоторых слов $$\alpha, \; \beta, \; \eta, \; \theta$$ в алфавите $$N \cup \Sigma$$. Если $$\phi \underset{ G }{\Rightarrow } \psi$$, то говорят, что слово $$\psi$$ непосредственно выводимо из слова $$\phi$$.

Замечание 1.4.6. Когда из контекста ясно, о какой грамматике идет речь, вместо $$\underset{ G }{\Rightarrow}$$ можно писать просто $$\Rightarrow$$.

Пример 1.4.7. Пусть$$G = \langle \{ S \} , \{ a , b , c \} , \{ S \rightarrow acSbcS ,\ cS \rightarrow \varepsilon \} , S \rangle .$$ Тогда $$cSacS \underset{ G }{\Rightarrow } cSa$$.

Определение 1.4.8. Если $$\omega_0 \underset{ G }{\Rightarrow } \omega_1 \underset{ G }{\Rightarrow } \ldots \underset{ G }{\Rightarrow } \omega_n$$, где $$n \geqslant 0$$, то пишем $${\omega_0 \overset * {\underset{ G }{\Rightarrow}} \omega_n}$$ и говорим, что слово $$\omega_n$$ выводимо из слова $$\omega_0$$. Другими словами, бинарное отношение $${\overset * {\underset{ G }{\Rightarrow}}}$$ является рефлексивным, транзитивным замыканием бинарного отношения $${\underset{ G }{\Rightarrow}}$$, определенного на множестве $$(N \cup \Sigma) ^*$$.

При этом последовательность слов $$\omega_0, \omega_1,\ldots, \omega_n$$ называется выводом (derivation) слова $$\omega_n$$ из слова $$\omega_0$$ в грамматике G. Число n называется длиной ( количеством шагов ) этого вывода.

Замечание 1.4.9. В частности, для всякого слова $$\omega \in (N \cup \Sigma) ^*$$ имеет место $$\omega \oversуt * {\underset{ G }{\Rightarrow}} \omega$$ (так как возможен вывод длины 0 ).

Пример 1.4.10. Пусть $$G = \langle \{ S \} , \{ a , b \} , \{ S \rightarrow aSa ,\ S \rightarrow b \} , S \rangle$$. Тогда $$aSa \overset * {\underset{ G }{\Rightarrow }} aaaaSaaaa$$. Длина этого вывода - 3.

Определение 1.4.11. Язык, порождаемый грамматикой G, - это множество $$L(G) \rightleftharpoons \{ \omega \in \Sigma ^* \mid S \overset * {\underset{ G }{\Rightarrow}} \omega \}$$. Будем также говорить, что грамматика G порождает (generates) язык L(G).

Замечание 1.4.12. Существенно, что в определение порождающей грамматики включены два алфавита - $$\Sigma$$ и N. Это позволило нам в определении 1.4.11 "отсеять" часть слов, получаемых из начального символа. А именно, отбрасывается каждое слово, содержащее хотя бы один символ, не принадлежащий алфавиту $$\Sigma$$.

Пример 1.4.13. Если $$G = \langle \{ S \} , \{ a , b \} , \{ S \rightarrow aSa ,\ S \rightarrow bb \} , S \rangle$$, то $$L(G) = \{ a^n bb a^n \mid n \geqslant 0 \}$$.

Определение 1.4.14. Две грамматики эквивалентны, если они порождают один и тот же язык.

Пример 1.4.15. Грамматика$$\begin{align*} S \; {\to} \; abS , \\ S \; {\to} \; a \end{align*}$$ и грамматика$$\begin{align*} T \; {\to} \; aU , \\ U \; {\to} \; baU , \\ U \; {\to} \; \varepsilon \end{align*}$$ эквивалентны.

Упражнение 1.4.16. Описать язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; F F , \\ F \; {\to} \; a F b , \\ F \; {\to} \; ab . \end{align*}$$

Упражнение 1.4.17. Описать язык, порождаемый грамматикой$$\begin{align*} C \; {\to} \; C c , \\ C \; {\to} \; A , \\ A \; {\to} \; a A b , \\ A \; {\to} \; \varepsilon . \end{align*}$$

Упражнение 1.4.18. Описать язык, порождаемый грамматикой$$\begin{align*} K \; {\to} \; \varepsilon , \\ K \; {\to} \; a , \\ K \; {\to} \; b , \\ K \; {\to} \; a K a , \\ K \; {\to} \; b K b . \end{align*}$$

Упражнение 1.4.19. Описать язык, порождаемый грамматикой$$\begin{align*} D \; {\to} \; D A , \\ D A A \; {\to} \; A D b , \\ A D A \; {\to} \; b , \\ A \; {\to} \; a . \end{align*}$$

Упражнение 1.4.20. Описать язык, порождаемый грамматикой$$\begin{align*} F \; {\to} \; a F H , \\ F \; {\to} \; a b c , \\ b H \; {\to} \; b b c , \\ c H \; {\to} \; H c . \end{align*}$$

Упражнение 1.4.21. Описать язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a T S , \\ S \; {\to} \; U , \\ T a \; {\to} \; aa T , \\ T U \; {\to} \; U , \\ U \; {\to} \; a . \end{align*}$$

Упражнение 1.4.22. Эквивалентны ли грамматика$$\begin{align*} S \; {\to} \; ab , \\ S \; {\to} \; a K S b , \\ K \; {\to} \; b S b , \\ K S \; {\to} \; b , \\ K \; {\to} \; \varepsilon \end{align*}$$ и грамматика$$\begin{align*} S \; {\to} \; a T b , \\ T \; {\to} \; \varepsilon , \\ T \; {\to} \; b , \\ T \; {\to} \; S , \\ T \; {\to} \; b S b S ? \end{align*}$$

Упражнение 1.4.23. Эквивалентны ли грамматика$$\begin{align*} S \; {\to} \; aD , \\ D \; {\to} \; bba , \\ D \; {\to} \; baDa , \\ D \; {\to} \; aDaDa \\ \end{align*}$$ и грамматика$$\begin{align*} S \; {\to} \; aaE , \\ S \; {\to} \; abJ , \\ E \; {\to} \; bJJ , \\ J \; {\to} \; aaEa , \\ J \; {\to} \; abJa , \\ J \; {\to} \; ba ? \end{align*}$$

1.5. Классы грамматик

Определение 1.5.1. Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой непосредственно составляющих, НС-грамматикой, грамматикой типа 1, context-sensitive grammar, phrase-structure grammar) называется порождающая грамматика, каждое правило которой имеет вид $$\eta A \theta \to \eta \alpha \theta$$, где $$A \in N$$, $$\eta \in (N \cup \Sigma) ^*$$, $$\theta \in (N \cup \Sigma) ^*$$, $$\alpha \in (N \cup \Sigma) ^+$$.

Пример 1.5.2. Грамматика$$\begin{align*} S \; {\to} \; T S , A \; {\to} \; a , \\ S \; {\to} \; U S , T A \; {\to} \; A A T , \\ S \; {\to} \; b , U A b \; {\to} \; b , \\ T b \; {\to} \; A b , U A A A \; {\to} \; A A U \end{align*}$$ не является контекстной (последние три правила не имеют требуемого вида).

Определение 1.5.3. Контекстно-свободной грамматикой ( бесконтекстной грамматикой, КС-грамматикой, грамматикой типа 2, context-free grammar) называется порождающая грамматика, каждое правило которой имеет вид $$A \to \alpha$$, где $$A \in N$$, $$\alpha \in (N \cup \Sigma) ^*$$.

Пример 1.5.4. Грамматика$$\begin{align*} S \; {\to} \; ASTA , AT \; {\to} \; UT , \\ S \; {\to} \; AbA , UT \; {\to} \; UV , \\ A \; {\to} \; a , UV \; {\to} \; TV , \\ bT \; {\to} \; bb , TV \; {\to} \; TA \end{align*}$$ является контекстной, но не контекстно-свободной (последние пять правил не имеют требуемого вида).

Определение 1.5.5. Линейной грамматикой (linear grammar) называется порождающая грамматика, каждое правило которой имеет вид $$A \to u$$ или $$A \to u B v$$, где $$A \in N$$, $$u \in \Sigma ^*$$, $$v \in \Sigma ^*$$, $$B \in N$$.

Грамматика$$\begin{align*} S \; {\to} \; TT , \\ T \; {\to} \; cTT , \\ T \; {\to} \; bT , \\ T \; {\to} \; a \end{align*}$$ является контекстно-свободной, но не линейной (первые два правила не имеют требуемого вида).

Определение 1.5.7. Праволинейной грамматикой ( рациональной грамматикой, грамматикой типа 3, right-linear grammar) называется порождающая грамматика, каждое правило которой имеет вид $$A \to u$$ или $$A \to u B$$, где $$A \in N$$, $$u \in \Sigma ^*$$, $$B \in N$$.

Пример 1.5.8. Грамматика$$\begin{align*} S \; {\to} \; aSa , \\ S \; {\to} \; T , \\ T \; {\to} \; bT , \\ T \; {\to} \; \varepsilon \end{align*}$$ является линейной, но не праволинейной (первое правило не имеет требуемого вида).

Пример 1.5.9. Грамматика$$\begin{align*} S \; {\to} \; T , \\ U \; {\to} \; abba \end{align*}$$ праволинейная. Она порождает язык $$\varnothing$$.

Пример 1.5.10. Грамматика$$\begin{align*} S \; {\to} \; aS , T \; {\to} \; aT , \\ S \; {\to} \; bS , T \; {\to} \; bT , \\ S \; {\to} \; aaaT , T \; {\to} \; \varepsilon \\ S \; {\to} \; aabaT , \\ S \; {\to} \; abaaT , \\ S \; {\to} \; aabbaT , \\ S \; {\to} \; ababaT , \\ S \; {\to} \; abbaaT , \end{align*}$$ праволинейная.

Пример 1.5.11. Грамматика$$\begin{align*} S \; {\to} \; \varepsilon , T \; {\to} \; abaT , \\ S \; {\to} \; aaaS , T \; {\to} \; baaT , \\ S \; {\to} \; abbS , T \; {\to} \; bbbT , \\ S \; {\to} \; babS , T \; {\to} \; bbaS \\ S \; {\to} \; aabT , \end{align*}$$ праволинейная. Обобщенный вариант языка, порождаемого этой грамматикой, используется в доказательстве разрешимости арифметики Пресбургера.

Определение 1.5.12. Правила вида $$\alpha \to \varepsilon$$ называются $$\varepsilon$$ - правилами или эпсилон-правилами.

Лемма 1.5.13. Каждая праволинейная грамматика является линейной. Каждая линейная грамматика является контекстно-свободной. Каждая контекстно-свободная грамматика без $$\varepsilon$$ -правил является контекстной грамматикой.

Определение 1.5.14. Классы грамматик типа 0, 1, 2 и 3 образуют иерархию Хомского (Chomsky hierarchy).

Определение 1.5.15. Язык называется языком типа 0 ( контекстным языком, контекстно-свободным языком, линейным языком, праволинейным языком ), если он порождается некоторой грамматикой типа 0 (соответственно контекстной грамматикой, контекстно-свободной грамматикой, линейной грамматикой, праволинейной грамматикой). Контекстно-свободные языки называются также алгебраическими языками.

Пример 1.5.16. Пусть дан произвольный алфавит$$\Sigma = \{ a_1 , \ldots , a_n \} .$$ Тогда язык $$\Sigma ^*$$ является праволинейным, так как он порождается грамматикой$$\begin{align*} S \; {\to} \; \varepsilon , \\ S \; {\to} \; a_1 S , \\ \vdots\\ S \; {\to} \; a_n S . \end{align*}$$

Упражнение 1.5.17. Какому классу принадлежит грамматика$$\begin{align*} S \; {\to} \; abba , \\ S \; {\to} \; baa ? \end{align*}$$

Упражнение 1.5.18. Какому классу принадлежит грамматика$$\begin{align*} S \; {\to} \; A D , \\ A \; {\to} \; a A , \\ A \; {\to} \; \varepsilon , \\ D \; {\to} \; b D c , \\ D \; {\to} \; \varepsilon ? \end{align*}$$

Упражнение 1.5.19. Найти праволинейную грамматику, порождающую язык $$\{ a^n b^m \mid n \geqslant 1 \text{ или } m \geqslant 1 \}$$.

Упражнение 1.5.20. Найти праволинейную грамматику, эквивалентную грамматике$$\begin{align*} S \; {\to} \; K bba K, \\ K \; {\to} \; K a, \\ K \; {\to} \; K b, \\ K \; {\to} \; \varepsilon . \end{align*}$$

Упражнение 1.5.21. Найти праволинейную грамматику, эквивалентную грамматике$$\begin{align*} S \; {\to} \; a S b, K \; {\to} \; a K, \\ S \; {\to} \; K, J \; {\to} \; J b, \\ S \; {\to} \; J, K \; {\to} \; a, \\ J \; {\to} \; \varepsilon . \end{align*}$$