Языки и трансляции. Мартыненко Б.К. - 69 стр.

UptoLike

Составители:

Рубрика:

получил наивысший номер. Приведите полученную грамматику к нормальной

форме Грейбах. Можно ли эквивалентно упростить её?

I-4.13. Докажите, что любой контекстно-свободный язык может

порождаться грамматикой с правилами вида A → a, A → aB, A → aBC, где a

 терминал, а A, B и C  нетерминалы.

I-4.14. Докажите, что любой контекстно-свободный язык может

порождаться грамматикой с правилами вида A → a, A → aαb, где a и b 

терминалы, а α  цепочка нетерминалов.

I-4.15. Используя теорему 4.7, докажите, что язык {a

i  простое} не

является контекстно-свободным.

I-4.16. Докажите, что язык {a

i  квадрат простого числа} не является

контекстно-свободным.

I-4.17. Используя теорему 4.7, докажите, что язык {a

 i ≥ 1} не явля-

ется контекстно-свободным.

I-4.18. Рассмотрим грамматику G = ({A, B, C}, {0, 1}, P, A), где

P = { S → AB, A → BSB, A → BB, A → 1, B → 0A1, B → 0, B → ε}.

Найдете эквивалентную грамматику, в которой S не появляется в правых

частях никаких правил, и S → ε  единственное правило, с ε в правой части.

I-4.19. Найдите cfl, который не может быть порождён линейной грамматикой.

I-4.20. Найдите cfl, который не является ограниченным языком.

I-4.21. Найдите cfl, который не является последовательным языком.

I-4.22. Докажите, что грамматика G

из примера 4.7 однозначная.

I-4.23. Какие из следующих грамматик являются несамовставленными?

Найдите конечные автоматы, распознающие те языки, которые имеют

несамовставленные грамматики.

a) G = ({A, B, C}, {a, b}, P, A), где P = {A → CB, A → b, B → CA, C → AB, C → a}.

b) G = ({A, B, C}, {a, b}, P, A), где P = { A → CB, A → Ca, B → bC, C → AB, C → b}.

I-4.24. Докажите, что любой cfl над односимвольным алфавитом является

регулярным.