V1_2009 (1115092)

1

2

3

4

5

6

7

8

9

10

1. Дана грамматика G:

S  Aa | cSad | ε

cAad  cBad

B  c

cB  cBc

(a) Классификация:

н айти такое целое k, что G является грамматикой типа k и не является грамматикой типа k+1.

Ответ:

(б) Каким из перечисленных классов

языков принадлежит язык L(G) ? Ответ:

Ответ:

2. (а) Дать определение недостижимого символа.

(б) Эквивалентны ли данные КС-грамматики

G₁ и G₂ ? Ответ обосновать.

G₁ : S  BAa

A  Aa | a | 

B  b

G₂ : S  E | BAa

D  dDd | c

E  EaD | Ed

A  Aa | ADE | a |

B  DbE | b

3. По леволинейной грамматике G была построена диаграмма состояний A:

( a) Восстановить по диаграмме A грамматику G:

(б) Детерминирован ли разбор по данной диаграмме ? Объясните ответ.

(в) Если разбор по диаграмме состояний A недетерминированный (т.е. конечный автомат A — недетерминированный), то с помощью соответствующего алгоритма построить эквивалентный детерминированный автомат A_D , иначе — написать для A программу-анализатор на языке C++.

4.

И меется клетчатый лист бумаги, бесконечный вправо и вниз. В левом верхнем углу расположено перо, оставляющее на бумаге след при перемещении. Перо управляется интерпретатором-графопостроителем. На вход интерпретатору подается последовательность символов-команд из алфавита {a, b}:

a — переместить перо на одну клетку вправо;

b — переместить перо по диагонали на одну клетку влево-вниз.

Например, по последовательности aaaaabbbbbaaaaa интерпретатор построит букву «Z» размера 55, изображенную на рисунке.

Построить грамматику с терминальным алфавитом {a, b}, описывающую буквы «Z» любого размера nn, n 1. В грамматике должно быть не более 7 правил вывода (считая альтернативы).

5.

(а)

(б)

Сформулируйте достаточное условие применимости метода рекурсивного спуска с учетом возможной -альтернативы (т.н. «канонический вид» КС-грамматики).

Выполняется ли это условие для грамматики G ? Обоснуйте ответ.

G: S  aAS | bB | 

A  aAca | bBb

B  cB | 

6.

Описать грамматику, порождающую язык L_вх  { d ⁿa ^m a ⁿ | m, n  0 }, и вставить в нее действия вида cout << ′символ′ ; так, чтобы для любых целых m, n  0 в процессе анализа рекурсивным спуском входной цепочки d ⁿa ^ma ⁿ печаталась бы цепочка cbⁿa ^m.

ПОЛИЗ

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35