Задачи по разделам курса

S -> SA|A
A -> (S)|()

S -> SS|A
A -> 0A1|S|01

S -> A0B|B1A
A -> BB|0
B -> AA|1

S -> Bab|aDa; A -> Dc|cA; B -> Sb|b;
D -> AB|aD.

S -> SAS|A; A -> Ac|Da|b; B -> DaD;
D -> ABD|AB.

S -> ASS|A; A -> c|Ab|aD; B -> aDD;
D -> AB|BaB.

S -> AB; AB -> CBb; CB -> ABB;
A -> a; aB -> a:

S -> AB; AB -> aDB; DB -> ABB; B -> b; Ab -> b.

S -> AB; AB -> aABB; B -> b; A -> a;

S -> AcBs; A -> AcA|B; B -> a|b;

S -> bAb; A -> AA|a

2.3.19. Построить КС-грамматики для следующих языков:

$$а)\ \{ 0^{n}1^{n} : n \ge 1 \\ б)\ \{ ww^{R} : w \in \{ a, b\} ^{*}\} \\ в)\ Вcе\ цепочки\ из\ нулей\ и\ единиц\ с\ одинаковым\ числом\ те\ х\ и \\ других \\ г)\ \{ \{ a, b\} ^{*} \setminus \{ a^{m}b^{n}a^{m}b^{n}\} : m, n \ge 1\} ; \\ д)\ \{ \{ a, b\} ^{*} \setminus \{ a^{2m}b^{3n}a^{2m}b^{n}\} : m, n \ge 1\} ; \\ е)\ \{ \{ a, b\} ^{*} \setminus \{ a^{m}b^{n}a^{m}\} : m, n \ge 1\} ; \\ ж)\ \{ \{ a, b\} ^{*} \setminus \{ ww\} : w \in \{ a, b^{*}\} ; \\ з)\ \{ \{ a, b\} ^{*} \setminus \{ a^{n}b^{n}a^{n}\} : n \ge 1\} ;$$

2.3.20. Определить КС-грамматики, которые порождали бы следующие языки:

1) все строки - элементы множества {0, 1}* такие, что в каждой из них непосредственно справа от каждого символа 0 стоит символ 1.

2) все строки - элементы множества {0, 1}* такие, что результаты чтения этих строк слева направо и справа налево совпадают;

3) все строки - элементы множества {0, 1}*, которые содержат символов 0 вдвое больше, чем символов 1 ;

4) все строки - элементы множества {0, 1}*, которые имеют одинаковое число символов 0 и 1 ;

5) все строки - элементы множества {0, 1}*, которые имеют четное число символов 0 и нечетное число символов 1 ;

6) все строки - элементы множества {0, 1}*, в которых скобки расставлены правильно.

2.3.21. Построить КС-грамматики, порождающие языки:

$$а)\ \{ a^{m}b^{n}c^{p}|m + n + p \equiv 0(mod 2);\ m, n, p \ge 0\} ; \\ б)\ \{ a^{p}b^{q}c^{r}|p + q > r; p, q, r \ge 0\} ; \\ в)\ \{ x|x \in \{ a, b\} *, |x|_{a} = |x|_{b}\} ; \\ г)\ \{ x|x \in \{ a, b\} *, |x|_{a} > |x|_{b}\} ; \\ д)\ построить\ однозначную\ КС-грамматику\ (однозначность \\ должна\ быть\ доказана)\ для\ языка\ \{ x|x \in \{ a, b\} *, |x|_{a} = |x|_{b}, \\ и\ для\ \forall u, v : x = uv;\ |u| \ne 0,\ |v| \ne 0\ выполнено\ |u|_{a} > |u|_{b}\} .$$

2.3.22. Построить КС-грамматику, порождающую язык

$$а) \{ a^{n}cb^{n}\} \cup \{ b^{n}ac^{n}\} ;\ n \ge 0 \\ б) \{ x|x \in \{ a, b\} * \setminus \varepsilon ;\ x \ne yy^{R}\}$$

2.3.23. Построить НС-грамматики для следующих языков:

а) $$\{ w \in \{ a, b, c\} *, |w|_{a} = |w|_{b} = |w|_{c}\}$$ (Винегрет)

б) $$\{ w \in \{ a, b, c\} *,\ 3|w|_{a} = 5|w|_{b} = 7|w|_{c}\}$$ (Винегрет 2)

в) {anpnrn} : n >=; 1} (Три мушкетeра)

г) {ambnambn : m, n >= 1} (Две калоши)

д) {a2mbnamb5n : m, n >= 1} (Калоши 2)

е) {ambnck : m >= n >= k >= 1} (Горка)

ж) {ambnck : 2m >= 3n >= k >= 1} (Горка 2)

з) $$\{a^{3^n}\mid n \geq 1 \} $$ (Бог любит троицу)

и) $$\{a^{5^n}b^n \mid n \geq 1 \}$$

к) $$\{a^{n^2} : n \geq 1\} $$ (Квадратные числа)

л) $$\{a^{n^2-5n+1} : n \geq 5 \}$$

м) $$\{a^nb^{n^2} : n \geq 1 \}$$ (Дама с собачкой)

н) $$\{d^{n^2-3n+2}h^n : n \geq 1}$$

о) {an : n = 1, 2, 3, 5, 8, 13, ...} (Числа Фиббоначи)

п) {an : n = 1, 3, 6, 10, 15, ...} (Треугольные числа, an = n(n + 1)/2 )

р) {an : n = 1, 5, 12, 22, ...} (Пятиугольные числа, an = n + 3n(n - 1)/2. Пятиугольное число может быть разбито на три треугольных + n точек)

с) $$\{ ww : w \in \{ a, b\} ^{*}\}$$ (Два лебедя)

т) $$\{a^{n^3} : n \geq 1 \}$$ (Кубические числа)

у) $$\{f^{n^3-n^2+2n-1}t^{3n} : n \geq 1}$$

ф) {an : n = 1, 2, 6, 24, ... , k!} (Факториал)

х) {012...0n-11n0n-1...120|n >= 1} (Пирамида Хеопса)

ч) {012...0n-11n1n0n-1...120|n >= 1} (Пирамиды майя)

ш) $$\{a^{3^n}b^{n^2}a^n \mid n \geq 1 \}$$

щ) $$\{ \{ a \} ^+ \backslash a^{n^2} : n \geq 1 \}$$ (Для студентов с исследовательской жилкой).

2.3.24. Построить КС-грамматики, порождающие языки

$$а) \{ xcy|x \ne y;\ x, y \in \{ a, b\} ^{*}\} ; \\ б) \{ a^{i}b^{j}c^{k}|i, j, k \ge 1\} \setminus \{ a^{n}b^{n}c^{n}|n \ge 1\} ; \\ в) \{ a, b, c\} ^{*} \setminus \{ a^{n}b^{n}c^{n}|n \ge 0\} .$$

2.3.25. Пусть G - грамматика с правилами:

$$S \to CD \ \ C \to aCA|bCB|\varepsilon \ \ AD \to aD \\ BD \to bD \ \ Aa \to aA \ \ Ab \to bA \\ Ba \to aB \ \ Bb \to bB \ \ D \to \varepsilon$$

Показать, что $$L(G) = \{ xx|x \in \{ a, b\} ^{*}\}$$.

2.3.26. Построить грамматику, порождающую данный язык:

{ancbnancbn|n > 0}:

2.3.27. Построить регулярную грамматику, порождающую цепочки в алфавите (a, b), в котором символ a не встречается два раза подряд.

2.3.28. Построить грамматику, порождающую сбалансированные относительно круглых скобок цепочки в алфавите $$\{a, (, ), \bot \}$$. Сбалансированную цепочку $$\alpha$$ определим реккурентно: цепочка $$\alpha$$ сбалансирована, если:

а) $$\alpha$$ не содержит скобок,

б) $$\alpha = (\alpha _{1})$$ или $$\alpha = \alpha _{1}\alpha _{2}$$, где $$\alpha _{1 }$$ и $$\alpha _{2}$$ сбалансированы.

2.3.29 Показать, что наличие в КС-грамматике правил вида

а) $$A \to AA|\alpha$$ б) $$A \to A\alpha A|\beta в) A \to \alpha A|A\beta |\gamma$$, где $$\alpha$$, $$\beta$$, $$\gamma$$ $$\in$$ (V_N $$\cup$$ V_T)^*; A $$\in$$ V_N, делает еe неоднозначной. Можно ли преобразовать эти правила таким образом, чтобы полученная эквивалентная грамматика была однозначной?

2.3.30. Показать, что грамматика G неоднозначна.

G : S -> abC|aB B -> bc; bC -> bc

2.3.31. Дана КС-грамматика G = (VT, VN, P, S). Предложить алгоритм построения множества

$$X = \{ A \in V_{N}|A \varepsilon \} .$$

2.3.32. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли язык L(G).

2.3.33. Одинаковые ли языки порождают грамматики из а), б), в)?

$$а) S \to aAb \ \ A \to BB \ \ B \to ab|A|\varepsilon ; \\ б) S \to aAb \ \ A \to AaAb|\varepsilon ; \\ в) S \to aB \ \ B \to aBB|b.$$

2.3.34. Эквивалентны ли грамматики с правилами

$$S \to AB;\ B \to Bb|A;\ A \to Aa|B;\ C \to c. \\ и \\ S \to \varepsilon .$$

2.3.35. Эквивалентны ли грамматики с правилами

A -> AB; B -> bC; A -> aAc|Sa; C -> c|Ca.
и
S -> As|Bc; B -> Ac|cS; A -> Bd; C -> c.

Лексический анализ

Регулярные множества и выражения

3.1.1. Показать, что множества, соответствующие двум данным регулярным выражениям, совпадают,

1) (a*b)c и a*(bc); 		2) a*b и b + aa*b;
3) b(b + ab)*a и b(b*ab)*b*a; 	4) b(ab + b)* и bb*a(bb*a)*:

3.1.2. Заменить каждое из следующих выражений эквивалентным, в котором не используются знак "+":

1) (a + b)*;
2) (a + bb + ba)*;
3) (a + (bb + ab)*)*:

3.1.3. Найти регулярные выражения, обозначающие языки, все слова которых - элементы множества {0, 1}*:

$$1)\ оканчивающиеся\ на\ 011, 101, 110; \\ 2)\ начинающиеся\ с\ 110, 101\ или\ 011; \\ 3)\ у\ которых\ каждый\ третий\ символ\ есть\ 0\ или\ каждым \\ второй - 1; \\ 4)\ не\ содержащие\ ни\ одной\ из\ подстрок\ 011\ и\ 101; \\ 5)\ содержащие\ каждую\ из\ подстрок\ 011\ и\ 101; \\ 6)\ начинающиеся\ с\ 011\ и\ оканчивающиеся\ на\ 110\ или\ 101; \\ 7)\ начинающиеся\ с\ 011\ или\ 110\ и\ оканчивающиеся\ на\ 101; \\ 8)\ начинающиеся\ с\ 011\ и\ содержащие\ вхождения\ подстроки \\ 110; \\ 9) \{ 01^{n}|n > 1\} ; \\ 10) \{ 01^{n}0|n > 0\} ; \\ 11) \{ 0^{m}1^{n}|n, m > 1\} ; \\ 12) \{ \alpha \in \{ 0, 1\} * : |\alpha |=3 - целое\ неотрицательное\ число\} ; \\ 13) \{ \alpha a|\alpha \in \{ 0, 1\} ^{+}, a \in \{ 0, 1\} , a\ входит\ в\ \alpha \} ; \\ 14) \{ (010)^{n}|n > 0\} ; \\ 15) \{ 0^{m}|m > 2\}\ или\ \{ 1^{n}|n > 0\} ; \\ 16) \{ (01)^{m}(10)^{n}|m \ge 0, n \ge 0\} ; \\ 17)\ содержащее\ четное\ число\ символов\ 0\ и\ нечетное\ число \\ символов\ 1; \\ 18)\ содержащее\ четное\ число\ символов\ 0\ или\ четное\ число \\ символов\ 1.$$

3.1.4. Является ли язык, состоящий из всех цепочек из 0 и 1, не содержащих подцепочки 010, регулярным?

3.1.5. Является ли язык, состоящий из всех цепочек из 0 и 1, содержащих чeтное число 0 и нечeтное - 1, регулярным?

3.1.6. Является ли язык, состоящий из всех цепочек чeтной длины в алфавите {fa, b, c}, регулярным?

3.1.7. Регулярен ли

$$а)\ язык\ формул\ вида\ A*(B),\ где\ A, B \in \{ a, b\} ^{+}? \\ б)\ язык\ формул\ вида\ (A_{1}.A_{2}),\ где\ для\ i = 1, \in A_{i}\ есть\ либо \\ слово\ в\ алфавите\ \{ a, b\} ,\ либо,\ в\ свою\ очередь,\ формула? \\ в)\ язык\ формул\ вида\ (A + B), где A, B \in \{ a, b\} ^{+}? \\ г)\ язык\ формул\ вида (A_{1})A_{2}, где для i = 1, \in A_{i}\ есть\ либо \\ слово\ в\ алфавит\е \{ a, b\} ,\ либо,\ в\ свою\ очередь,\ формула?$$

3.1.8. Определить язык, состоящий из всех идентификаторов, с помощью:

а) регулярного выражения;
б) леволинейной грамматики;
в) конечного автомата;
г) праволинейной грамматики.

3.1.9. Будет ли регулярным язык $$L = \{ x \in \{ a, b\} ^{*} : |x|_{a}$$ четно и |x|b нечетно}?

3.1.10. Построить праволинейную грамматику, порождающую язык L всех слов в алфавите {0, 1}, содержащих чeтное число единиц и нечeтное число нулей. Будет ли она однозначной?

3.1.11. Построить регулярное выражение для языка LR, где L - язык всех слов в алфавите {0, 1}, содержащих чeтное число единиц и нечeтное число нулей.

Конечные автоматы

3.2.1. Какой язык допускается конечным автоматом $$M = (\{ q_{0}\} , \{ a, b\} , \varnothing , q_{0}, \{ q_{0}\} )$$?

3.2.2. Построить недетерминированный конечный автомат, допускающий цепочки в алфавите {1, 2}, у которых последний символ цепочки уже появлялся в ней раньше. Построить эквивалентный детерминированный конечный автомат. Построить аналогичные конечные автоматы в алфавите {1, 2, 3}.

3.2.3. Построить конечный автомат, допускающий язык $$\{ xy\} \cup \{ yx\}$$, где $$x \in \{ a\} ^{*} \setminus \varepsilon y \in \{ b\} ^{*} \setminus \varepsilon$$.

3.2.4. Построить детерминированный конечный автомат, допускающий язык L всех слов в алфавите {0, 1}, содержащих чeтное число единиц и нечeтное число нулей;

Алгоритмы построения конечных автоматов

3.3.1. Для регулярного выражения над алфавитом T = {a, b} построить эквивалентный детерминированный конечный автомат:

а) b(ba|b)*|b 		б) (ab|b)*ba|ab
в) (a|b)*ba(a|b) 	г) (a|b)*ab(a|b)*
д) a(ab|b)*|ba 		е) (ba|b)*ab|ba
ж) (a*b)*ab*a 		з) (a|b)*(a|b)(a|b(a|b)

Лексический анализ

Регулярные множества и их представления

3.4.1. Будет ли регулярным язык $$L = \{ x \in \{ a, b\} |x$$ не содержит подцепочки aba }?

3.4.2. Возможно ли построить регулярную грамматику, порождающую язык, включающий в себя все непустые цепочки из 0 и 1, не содержащие трeх 1 подряд?

Алгебраические свойства регулярных множеств. Лемма о разрастании.

3.5.1. Будут ли регулярными следующие языки в алфавите {a}:

а) $$L_{1} = \{ \{ a^{2n+5}\} \cup \{ a^{7n+4}\} ,\ n = 0, 1, \dots \}$$ ;

б) $$L_{2} = \{ \{ a^{2n+5}\} \cap \{ a^{7n+4}\} ,\ n = 0, 1, \dots \}$$ ;

в) $$L_{3} = \{ \{ a^{4n+5}\} , n = 0, 1, \dots , n \ne 5(mod11)\}$$ ;

д) $$L_4 = \{a^{n^2}, n = 0, 1, \ldots \}$$.

3.5.2. Будут ли регулярными следующие языки в алфавите $$\Sigma = \{ a, b\}$$:

$$а)\ язык\ L_{1}\ из\ всех\ слов \Sigma *,\ содержащих\ подслова\ a?b; \\ б)\ язык\ L_{2}\ из\ всех\ слов\ \Sigma *,\ не\ содержащих\ двух\ b\ подряд; \\ в)\ язык\ L_{3}\ из\ всех\ слов\ \Sigma *,\ не\ принадлежащих\ L_{1}\ или\ L_{2}; \\ г) L_{4} = \{ \{ a^{2n+5}b^{7n+4}\} ,\ n = 0, 1, \dots \} ?$$

3.5.3. Задается ли язык {aⁿb^m|n $$\ge$$ m $$\ge$$ 1} регулярным выражением?

3.5.4. Является ли грамматика с правилами:

$$S \to aA|bB|C;\ B \to bB|b|\varepsilon ; \\ A \to aA|a|\varepsilon ; \ C \to cSC:$$

праволинейной грамматикой?

Синтаксический анализ

КС-грамматики и МП-автоматы

4.1.1. Пусть G - грамматика с правилами:

S -> SbS|ScS|a

Найти 2 различных дерева вывода для цепочки abaca.

4.1.2. Дана однозначная КС-грамматика G = (N, T, P, S) и цепочка $$w \in L(G)$$. Количество элементов во множествах N, T, P равно n1, n2, n3 соответственно, а |w| = l. Найти нижнюю и верхнюю границу для числа деревьев разбора w в G.

4.1.3. Являются ли однозначными следующие грамматики?

$$а)\ S \to a|C;\ C \to AB;\ A \to aA|Ba|a;\ B \to aB; \\ б)\ S \to BA;\ A \to Aa|bA|\varepsilon ;\ B \to Bb|aB|b; \\ в)\ S \to b|C;\ C \to aC|AC;\ A \to aA|Aa|a; \\ г)\ S \to AB;\ A \to aA|bA|a;\ B \to Ba|Bb|\varepsilon ; \\ д)\ S \to A|B;\ A \to AA|a;\ B \to aB|b|C;\ C \to cC; \\ е)\ S \to aA|bB;\ A \to aA|a|b;\ B \to bB|b|\varepsilon ; \\ ж)\ S \to aAc|bS;\ A \to aA|Aa|\varepsilon ; \\ з)\ S \to aA|b;\ A \to abA|abAcb;\ B \to c; \\ и)\ S \to aB|cA;\ A \to BaA|a;\ B \to A|a; \\ к)\ S \to ABS|\varepsilon ;\ A \to abA|a;\ B \to Ba|Bab|\varepsilon .$$

4.1.4. Является ли однозначной грамматика с правилами:

$$а)\ S \to A|B;\ B \to aB|b|C;\ A \to AA|a;\ C \to cC; \\ б)\ S \to aAc|bS;\ A \to aA|Aa|c; \\ в)\ S \to aA|b;\ A \to abA|abAcb;\ B \to c; \\ г)\ S \to aB|cA;\ A \to BaA|a;\ B \to A|b; \\ д)\ S \to a|C;\ C \to AB;\ A \to aA|Ba|a;\ B \to aB; \\ е)\ S \to BA;\ A \to Aa|bA|\varepsilon ;\ B \to Bb|aB|b; \\ ж)\ S \to b|C;\ C \to aC|AC;\ A \to aA|Aa|a; \\ з)\ S \to AB;\ A \to aA|bA|a;\ B \to Ba|Bb|\varepsilon .$$

4.1.5. Пусть G1 - грамматика, имеющая продукции:

S -> bA|ab; A -> a|aS|bAA; B -> b|bS|aBB;

а G2 - грамматика, определяемая продукциями:

S -> aB|aBS|bAS|bA; A -> bAA|a; B -> bBB|b.

Показать, что

1) G1 - неоднозначная грамматика;
2) G2 - однозначная грамматика;
3) L(G1) = L(G2):

4.1.6. Какой язык допускается автоматом с магазинной памятью

$$P = (Хq_{0}\} , \{ a, b\} , \{ z_{0}\} , \varnothing , q_{0}, z_{0}, \{ q_{0}\} ) ?$$

4.1.7. Построить МП-автоматы, определяющие языки

$$а)\ \{ ww^{R} : w \in \{ a, b\} ^{*}\} ; \\ б)\ язык\ всех\ цепочек\ из\ нулей\ и\ единиц\ с\ одинаковым\ числом \\ тех\ и\ других \\ в)\ \{ \{ a, b\} ^{*} \setminus \{ a^{m}b^{n}a^{m}b^{n}\} : m, n \ge 1\} ; \\ г)\ \{ \{ a, b\} ^{*} \setminus \{ a^{m}b^{n}a^{m}\} : m, n \ge 1\} ; \\ д)\ \{ \{ a, b\} ^{*} \setminus \{ ww\} : w \in \{ a, b]^{*}\} :$$

4.1.8. Построить автомат с магазинной памятью, допускающий язык:

$$а)\ (\{ a^{n}b^{n}c^{m}|n, m \ge 1\} ) \cup (\{ a^{m}b^{n}c^{n}|n, m \ge 1\} ); \\ б)\ \{ a^{n}c^{k}b^{n}|k, n \ge 1\} ; \\ в)\ \{ a^{m}b^{n}c^{p}|m + n + p \equiv 0(mod2),\ m,\ n,\ p \ge 0\} ; \\ г)\ \{ a^{p}b^{q}c^{r}|p + q > r;\ p, q, r \ge 0\} ; \\ д)\ \{ x|x \in \{ a, b\} ^{*}, |x|_{a} = |x|_{b}\} ; \\ е)\ \{ x|x \in \{ a, b\} ^{*}, |x|_{a} \ge |x|_{b}\} ; \\ ж)\ \{ x|x \in \{ a, b\} ^{*}; |x|_{a} = |x|_{b},\ и\ для\ \forall u, v : x = uv; |u| \ne 0, |v| \ne 0\ выполнено\ |u|_{a} > |u|_{b}\} .$$

4.1.9. Пусть A - магазинный автомат. Построить магазинный автомат B, допускающий все префиксы языка

$$L(A),\ то\ есть\ язык\\ L(B) = \{ x|xy \in L(A)\} :$$

4.1.10. Построить детерминированные МП-автоматы, определяющие языки:

$$а)\ \{ wcw^{R} : w \in \{ a, b\} ^{*}\} ; \\ б)\ \{ 0^{n}1^{n} : n \ge 1\} \\ в)\ \{ xcx^{R}ycy^{R}|x, y \in \{ a, b\} ^{*}\} .$$

4.1.11. Является ли язык $$L = \{ xcx^{R}|x \in (a*b*)*\}$$ детерминированным? Обосновать ответ с помощью магазинного автомата, допускающего язык L.

4.1.12. Является ли детерминированным следующий язык:

$$а)\ L = \{ x^{R}cx|x \in (a*b*)*\} ; \\ б)\ L = \{ xcx^{R}|x \in (b*a*)*\} ; \\ в)\ L = \{ xcx^{R}|x \in b*(a*)*\} .$$

4.1.13. Доказать, что для любой КС-грамматики G' существует эквивалентная ей КС грамматика G, имеющая лишь правила вида

$$A \to BC; A \to a ,\ где\ A,\ B,\ C \in V_{N}; a \in V_{T} .$$

4.1.14. Доказать, что если L1 - КС-язык, то язык L, состоящий из всех слов L1 четной длины - КС-язык, то есть

$$L = \{ X|X \in L_{1};\ |X| = 2K; K = 0, 1, \dots , \} - КС-язык.$$

4.1.15. Доказать, что для КС-грамматики G существует неукорачивающая КС-грамматика G', порождающая язык

$$L(G') = L(G) \setminus \{ \varepsilon \} .$$

4.1.16. Привести алгоритм, позволяющий узнать, принадлежит ли данное слово данному КС-языку и доказать его правильность.

4.1.17. КС-грамматика называется левооднозначной, если каждое слово порождаемого ею языка имеет единственный левый вывод. Аналогично определяется правооднозначная грамматика. Построить пример левооднозначной, но не правооднозначной КС-грамматики.

C.4.2. Алгебраические свойства КС-языков. Лемма о разрастании.

4.2.1. Пусть L1, L2 - КС-языки. Докажите:

$$1) L_{1} \cup L_{2} - КС-язык; \\ 2) L_{1}L_{2} - КС-язык.$$

4.2.2. Пусть L - КС-язык. Докажите:

1) L* - КС-язык;
2) LR - КС-язык.

4.2.3. Доказать, что не существует КС-грамматик, порождающих языки

а) {anbncn} : n >= 1}; б) $$\{ ww : w \in \{ a, b\} ^{*}\} ;$$

в) $$\{ a^{n^2} : n \geq 1 \};$$ г) $$\{a^{n^3} : n \geq 1\}$$.

4.2.4. Выяснить, какие из приведенных ниже языков не являются КС-языками:

$$1)\ \{ a^{i}b^{j}c^{k}|0 \le i <j< k\} ; \\ 2)\ \{ a^{i}b^{j}c^{k}|0 \le i =j= k\} ; \\ 3)\ \{ a^{i}b^{j}c^{k}|0 \le i = j, k \ge 0,\ i \ne k\} ; \\ 4)\ \{ a^{i}b^{j}c^{k}|0 \le i = j,\ k \ge 0\} :$$

4.2.5. Показать, что язык {anbncn|n>=1g не является КС-языком.

4.2.6. Является ли язык {anbmanbm|n >= 1, m >= 1 } КС-языком?

4.2.7. Является ли язык {anbmbnam|n >= 1, m >= 1} КС-языком?

4.2.8. Является ли язык {ap|p - простое число} КС- языком?

4.2.9. Является ли язык $$\{a^nb^{n^2} \mid n \in N \}$$ КС-языком?

4.2.10. Определить, замкнуто ли множество КС-языков относительно дополнения?

4.2.11. Замкнуто ли множество КС-языков относительно обращения? (Иначе говоря, верно ли, что если L - КС-язык, то LR - тоже КС-язык).

Преобразования КС-грамматик

4.3.1. Указать множество бесполезных символов для грамматики:

S -> A|B; B -> aB|b|C; A -> AA|a; C -> cC:

4.3.2. Указать множество бесполезных символов в грамматике G = ({S, A, B, C}, {a, b, c}, P, S), где P состоит из

$$S \to aSb|Abb|\varepsilon\ B \to AB \\ A \to aBCb|bAb\ C \to a|c.$$

4.3.3. Указать множество бесполезных символов в грамматике G = ({S, A, B, C}, {a, b, c}, P, S), где P состоит из

S -> A|B 	A -> aB|bS|b
B -> AB|Ba 	C -> AS|b.

4.3.4. Указать множество бесполезных символов в грамматике G=({S, A, B, C, D}, {a, b, c}, P, S}, где P состоит из

S -> aBb|aCb 	A -> Dc|cA
B -> aS|b 	C -> AB|aD
D -> AB|cDa.

4.3.5. Указать множество бесполезных символов в грамматике G = ({S, A, B, C}, {0, 1, 2}, P, S), где P состоит из

S -> SS|A A -> 0A1|C|0
B -> 0C|1 C -> BC|CS.

4.3.6. Являются ли следующие грамматики приведeнными? Указать для каждой грамматики множества недостижимых, бесплодных и бесполезных символов:

$$а) S \to a|C \ \ \ б) S \to BA \\ C \to AB \ \ \ A \to Aa|bA|\varepsilon \\ A \to aA|Ba|a \ \ \ B \to Bb|aB|b; \\ B \to aB; \\ \\ в) S \to b|C \ \ \ г) S \to AB \\ C \to aC|AC \ \ \ A \to aA|bA|a \\ A \to aA|Aa|a; \ \ \ B \to Ba|Bb|\varepsilon ; \\ \\ д) S \to A|B \ \ \ е) S \to aA|bB \\ A \to AA|a \ \ \ A \to aA|a|b \\ B \to aB|b|C \ \ \ B \to bB|b|\varepsilon ; \\ C \to cC; \\ \\ ж) S \to aAc|bS \ \ \ з) S \to aA|b \\ A \to aA|Aa|\varepsilon ; \ \ \ A \to abA|abAcb \\ B \to c; \\ \\ и) S \to aB|cA \ \ \ к) S \to ABS|\varepsilon \\ A \to BaA|a \ \ \ A \to abA|a \\ B \to A|a; \ \ \ B \to Ba|Bab|\varepsilon .$$

4.3.7. Построить приведeнные грамматики, эквивалентные следующим грамматикам:

$$a) S \to A|B \ \ \ A \to C|D \ \ \ B \to D|E \\ C \to S|a|\varepsilon \ \ \ D \to S|b \ \ \ E \to S|c|\varepsilon ; \\ б) S \to AB \ \ \ A \to Aa|bB \ \ \ B \to a|Sb.$$

4.3.8. Построить $$\varepsilon$$ -свободные КС-грамматики, эквивалентные следующим грамматикам:

$$1) S \to AB \ \ \ 2) S \to ABC \\ A \to C|ab \ \ \ A \to BB|\varepsilon \\ C \to c|\varepsilon \ \ \ B \to CC|\varepsilon \\ B \to aAa; \ \ \ C \to AA|b; \\ \\ 3) S \to aSbS \ \ \ 4) S \to AB \\ S \to bSaS|\varepsilon ; \ \ \ A \to SA|BB|bB \\ B \to b|aA|\varepsilon .$$

4.3.9. Доказать, что для каждой КС-грамматики существует эквивалентная ей приведенная КС-грамматика.

4.3.10. Привести алгоритм построения множества достижимых символов и доказать его правильность

4.3.11. Доказать, что для каждой КС-грамматики существует эквивалентная ей КС-грамматика, не являющаяся леворекурсивной

Предсказывающий разбор сверху- вниз

4.4.1. Построить множества FIRST и FOLLOW для каждого нетерминала грамматики

$$а) S \to aAB|B \ \ \ б) S \to aAB|BA \\ A \to aA|a \ \ \ A \to BBB|a \\ B \to BS|A|b; \ \ \ B \to AS|b; \\ \\ в) S \to S + T \ \ \ г) S \to ABC \\ S \to T \ \ \ A \to BB|\varepsilon \\ T \to a \ \ \ B \to CC|a \\ T \to S[S]; \ \ \ C \to AA|b; \\ \\ д) S \to aB|bA \ \ \ е) S \to Ba|Ab \\ A \to aS|bAA|a \ \ \ A \to Sa|AAb|a \\ B \to bS|aBB|b; \ \ \ B \to Sb|BBa|b; \\ \\ ж) S \to (SbS) \ \ \ з) B \to begin D; S end \\ S \to (T) \ \ \ B \to s \\ S \to a \ \ \ D \to D; d \\ T \to TS \ \ \ D \to d \\ T \to S; \ \ \ S \to S; B \\ S \to B; \\ \\ и) A \to aACd|b \\ C \to c|\varepsilon .$$

4.4.2. Является ли следующая грамматика LL(1)? Использовать критерий LL(1).

S -> aAb; 	A -> 0; 		A -> aaA.

4.4.3. Для грамматики написать эквивалентную LL(1) - грамматику

$$а) S \to aS|a; \\ б) S \to ba|A \ \ \ A \to a|Aab|Ab; \\ в) S \to aaS|abA \ \ \ A \to \varepsilon |Aa|Ab; \\ г) S \to baaA|babA \ \ \ A \to \varepsilon |Aa|Ab; \\ д) S \to abaA|abbA \ \ \ A \to \varepsilon |Aa|Ab; \\ е) S \to ab|baA \ \ \ A \to \varepsilon |Aab|Ab.$$

4.4.4. Для следующих грамматик определить, являются ли они LL(k) грамматиками и найти точное значение k. Для LL(1) -грамматик построить детерминированный левый анализатор:

$$a) S \to aAS|b \ \ \ A \to a|bSA; \\ б) S \to A|B \ \ \ A \to aAb|0 \ \ \ B \to aBbb|1; \\ в) S \to \varepsilon |abA \ \ \ A \to Saa|b; \\ г) S \to aS|a; \\ д) S \to aAaa|bAba \ \ \ A \to b|\varepsilon ; \\ е) S \to Sa|b; \\ ж) S \to TE'; \ \ \ E' \to +TE'|\varepsilon \ \ \ T \to FT' \\ T' \to *FT'|\varepsilon \ \ \ F \to (S)|a.$$

4.4.5. Определить, являются ли следующие грамматики LL(k) -грамматиками, и указать точное значение k:

$$а) S \to Ab \ \ \ A \to Aa|a; \\ б)S \to Ab \ \ \ A \to aA|a; \\ в) S \to aAb \ \ \ A \to BB \ \ \ B \to ab|A|\varepsilon ; \\ г) S \to aAb \ \ \ A \to AaAb|\varepsilon ; \\ д) S \to aB \ \ \ B \to aBB|b.$$

4.4.6. Преобразовать грамматику к LL(1)- виду и построить для неe LL(1) -таблицу

а) S -> Ab 		A -> aA|a;
б) S -> aB 		B -> aBB|b:

4.4.7. Сколько тактов сделает LL(1) -анализатор для грамматики G c правилами:

$$S \to aAB\ A \to bC\ B \to SS|\varepsilon\ C \to A|\varepsilon$$

при разборе цепочки x = ab; ab, b?

4.4.8. Является ли грамматика S -> Sa|b LL(2) - грамматикой?

4.4.9. Является ли язык, состоящий из всех целых чисел без знака и без незначащих нулей, LL(1) -языком?

4.4.10. Является ли язык, состоящий из всех цепочек из 0 и 1, не содержащих подцепочки 010, LL(1) -языком?

4.4.11. Является ли язык, состоящий из всех непустых цепочек из 0 и 1, не содержащих трех 1 подряд, LL(1) -языком?

4.4.12. Существует ли контекстно-свободная грамматика, LL(1) -таблица для которой не содержит элементов "ошибка" ?

4.4.13. Сформулируйте необходимые и достаточные условия того, что КС-грамматика есть LL(1) -грамматика. Докажите необходимость и достаточность.

Разбор снизу-вверх типа сдвиг- свертка

4.5.1. Построить все состояния для LR(0) -анализа грамматики G:

$$S \to aAb;\ A \to \varepsilon ;\ A \to aaA$$

Будет ли G LR(0) -грамматикой? А LR(1)?

4.5.2. Является ли грамматика с правилами:

S -> A|B; B -> aB|b|C; A -> AA|a; C -> cC

LR(0) -грамматикой?

4.5.3. Сколько множеств LR(0) -ситуаций в канонической системе LR(0) -ситуаций грамматики G с правилами

а) S -> aA|aB 		A -> bA|c 		B -> bB|d;
б) S -> A0|F1 		A -> S0|B1 		B -> A1|F0 	F -> B0|S1;
в) E -> (L)|a 		L -> EL|E.

4.5.4. Сколько LR(0) -таблиц имеет грамматика с правилами:

S -> Aa|Bb; B -> b; A -> ab.

4.5.5. Построить все состояния LR(1) -анализа для грамматики:

$$S \to aAb;\ A \to \varepsilon |aaA.$$

4.5.6. Сколько множеств LR(1) -ситуаций в канонической cистеме LR(1) -ситуаций грамматики G с правилами

а) S -> aSb|ab;
б) S -> aAc|b 		A -> aSc|b.

4.5.7. Определить, является ли грамматика c приведенным набором правил LR(1) -грамматикой:

$$а) A \to aAB|b \ \ \ B \to b|\varepsilon ; \\ б) S \to SaS \ \ \ S \to a; \\ в) S \to Abb|Bba \ \ \ A \to a \ \ \ B \to a; \\ г) S \to aL|a \ \ \ L \to Lb|b.$$

4.5.8. Построить все состояния анализа (K = 1) для грамматики

S -> S1; S1->S1S1; S1->a.

Будет ли эта грамматика LR(1)?

4.5.9. Построить все состояния LR(1) анализа для грамматики:

S -> aBc; 		B -> b; 		B -> bBb:

Применив критерий LR(K), определить, будет ли это LR(1) - грамматика.

4.5.10. Выяснить, являются ли следующие грамматики LR(k) -грамматиками. Найти точное значение k и построить детерминированный правый анализатор:

$$а)\ S \to SaSb|\varepsilon ; \\ б)\ S \to Sa|a; \\ в)\ S \to C|d\ C \to Ac|b\ D \to aD|c; \\ г)\ S \to Ab|Bc\ A \to Aa|\varepsilon\ B \to Ba|\varepsilon ; \\ д)\ S \to AB\ A \to a\ B \to CD|aE\ C \to ab\ D \to bb\ E \to bba; \\ е)\ S \to AB\ A \to 0A1|\varepsilon\ B \to 1B|1.$$

4.5.11. Является ли нижеприведенная грамматика LR(k), и если да, то определить минимальное k.

$$а) S \to aAc \ \ \ A \to aSc \ \ \ S \to b \ \ \ A \to b; \\ б) S \to S1 \ \ \ S1 \to S1S1 \ \ \ S1 \to a; \\ в) S \to aBc \ \ \ B \to b \ \ \ B \to bBb; \\ г) S \to aAc S \to b A \to aSc A \to b; \\ д) S \to aAb A \to 0 A \to aaA; \\ е) S \to aAb A \to \varepsilon A \to aaA.$$

4.5.12. Являются ли следующие грамматики LR(k) - грамматиками? Указать точное значение k и построить соответствующий детерминированный правый анализатор.

$$а) S \to Ab \ \ \ A \to Aa|a; \\ б) S \to Ab \ \ \ A \to aA|a; \\ в) S \to aAb \ \ \ A \to BB \ \ \ B \to ab|A|\varepsilon ; \\ г) S \to aAb \ \ \ A \to AaAb|\varepsilon ; \\ д) S \to aB \ \ \ B \to aBB|b:$$

4.5.13. Для грамматики

$$S \to Ab|Bc A \to Aa|\varepsilon B \to Ba|\varepsilon$$

написать эквивалентную LR(0) -грамматику.

4.5.14. Сколько сверток и переносов сделает LR(1) - анализатор для грамматики G = ({S, A}, {a}, P, S) c правилами S -> A A -> Aa|a при анализе цепочки a100?

4.5.15. Сколько SLR(1) -таблиц имеет грамматика с правилами:

S -> Aaa|Bb|C B -> aa A -> aa C -> cAc|cBd.

4.5.16. Сколько тактов сделает LALR(1) -анализатор для грамматики с правилами:

S -> A|BC B -> a A -> a; C -> AAAS
при разборе цепочки aaaaa?

4.5.17. Выписать цепочку минимальной длины, на которой видны отличия LARL(1) и LR(1) -анализаторов для грамматики с правилами:

S -> Aa|Bb|C B -> aa A -> aa C -> cAc|cBd.

4.5.18. Пусть G = (N, T, P, S) - LR(1) -грамматика, $$w \in T^{*}$$. В каких случаях (в зависимости от G и w ) LR(1) - анализатор при анализе цепочки w не сделает ни одного сдвига?

4.5.19. Пусть G = (N, T, P, S) - LR(1) -грамматика; $$w \notin L(G); |w| = n$$: Пусть k - число сдвигов, делаемых LR(1) - анализатором при анализе цепочки w. Привести нижнюю и верхнюю оценку для числа k.

4.5.20. Пусть G = (N, T, P, S) - LR(1) -грамматика, $$|P| = m \ge 1; w \in L(G), |w| = n$$. Пусть k - число сверток, делаемых LR(1) -анализатором при анализе цепочки w. Привести нижнюю оценку для числа k.

4.5.21. Пусть G = (N, T, P, S) - LR(1) -грамматика, $$|P| = m \ge 1;\ w \notin L(G),\ |w| = n$$. Пусть k - число сверток, делаемых LR(1) -анализатором при анализе цепочки w. Привести нижнюю оценку для числа k.

4.5.22. Существует ли LR(1) -грамматика, для которой функция действий LR(1) -таблицы не содержит элементов "ошибка" ?

4.5.23. Дана КС-грамматика G = (N, T, P, S). Найти верхнюю оценку числа LR(1) -ситуаций для G.

4.5.24. Дана LR(1) -грамматика без $$\varepsilon$$ -правил G и цепочка $$w \in L(G)$$. В дереве разбора w - n1 листьев и n2 внутренних вершин. Сколько сдвигов и сверток сделает LR(1) -анализатор для G при анализе цепочки w?

Элементы теории перевода

Атрибутные грамматики

5.3.1. Дополнить грамматику $$S \to 0S11;\ S \to 1S00;\ S \to \varepsilon$$ до атрибутной так, чтобы вычислялась максимальная длина непрерывной последовательности единиц в порожденном слове.

5.3.2. Дополнить грамматику $$S \to AA;\ A \to 0A;\ A \to 1A;\ A \to \varepsilon$$ до атрибутной так, чтобы вычислялась максимальная длина непрерывной последовательности из 1 в порожденном слове.

5.3.3. Дополнить грамматику $$S \to AA;\ A \to A0;\ A \to A1;\ A \to \varepsilon$$ до атрибутной так, чтобы вычислялось число сочетаний 01 в порожденном слове.

5.3.4. В грамматике $$[целое] \to dC; \ C \to dC|\varepsilon$$ терминал d имеет атрибут 0 или 1. Определить атрибуты так, чтобы нетерминал [целое] имел атрибут, равный восьмеричному значению выводимого числа.

5.3.5. Построить атрибутные грамматики для следующих переводов:

$$а) \{ (x, x)|x \in \{ a, b\} ^{*}\} ; \ \ \ б) \{ (x, x^{R})|x \in \{ a, b\} ^{*}\} ; \\ в) \{ (x, xx)|x \in \{ a, b\} ^{*}\} ; \ \ \ г) \{ (a^{n}b^{n}; a^{n}b^{n}c^{n})|n \ge 1\} .$$

5.3.6. Привести пример атрибутной грамматики с некорректно заданными семантическими правилами

5.3.7. Привести пример атрибутной грамматики, вычисление атрибутов для которой нельзя выполнить параллельно с LL(1) -анализом.

5.3.8. Привести пример атрибутной грамматики, вычисление атрибутов для которой нельзя выполнить параллельно с LR(1) -анализом.

Генерация кода

Трансляция арифметических выражений

9.1.1. Для следующих арифметических выражений с помощью алгоритма Сети-Ульмана сгенерировать программу и изобразить атрибутированное дерево:

а) A*B + C*(D + E)*F; 		б) A*(B + C)*(D + E)*F;
в) A + B + C*D + E*F; 		г) A + B*C*D*E + F;
д) A + B*(C*D + E*F).

Трансляция логических выражений

9.2.1. Для следующих логических выражений сгенерировать код на командах перехода и изобразить атрибутированное дерево

а) A and not (B or C) or (D and E);
б) A and B and C or not (D or E);
в) A and (B or not (C and D) and E);
г) not (A and B or C or D) and E;
д) A and B or C or D and not E.

Генерация оптимального кода методами синтаксического анализа

9.3.1. Для следующих операторов присваивания сгенерировать оптимальный код методом сопоставления образцов:

а) a = b[i] + j; 		б) a = b[i+5]; 			в) a = b[i] + c[2];
г) a = b[i+2+j]; 		д) a = b[2+c[1]]; 		е) a = b[i+j];
ж) a = b[i+2] + 3; 		з) a =j+ b[i+3]; 		и) a = b[i+j+1];
к) a = b[i+j] + 1.