Теория и реализация языков программирования



         

КС-грамматики и МП-автоматы - часть 2


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

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

L(A)}:

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

а) {wcwR : w

{a, b}*}; б) {0n1n : n
1} в) {xcxRycyR|x, y
{a, b}*}.

4.1.11. Является ли язык L = {xcxR|x

(a*b*)*} детерминированным? Обосновать ответ с помощью магазинного автомата, допускающего язык L.

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

а) L = {xRcx|x

(a*b*)*}; б) L = {xcxR|x
(b*a*)*}; в) L = {xcxR|x
b*(a*)*}.

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

A

BC; A
a , где A, B, C
VN; a
VT .

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

L = {X|X

L1; |X| = 2K; K = 0, 1, ..., } - КС-язык.

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

L(G') = L(G) \ {?}.

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

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

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

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

1) L1

L2 - КС-язык; 2) L1L2 - КС-язык.

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

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

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

а) {anbncn} : n

1}; б) {ww : w
{a, b}*};

в)

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

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

1) {aibjck|0

i <j< k}; 2) {aibjck|0
i =j= k}; 3) {aibjck|0
i = j, k
0, i
k}; 4) {aibjck|0
i = j, k
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 - тоже КС-язык).




Содержание  Назад  Вперед