V2_2009 (1115094)

1

2

3

4

5

6

7

8

9

10

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

S  A | ε

A  cdAa | cB

cdcBa  cdсDa

Da  Daa

D  a

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

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

Ответ:

(б) Каким из перечисленных классов языков принадлежит язык L(G) ? Ответ:

Ответ:

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

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

Ответ обосновать.

G₁ : S  BAaС | BC

A  Aa | a | 

B  b

G₂ : S  E | BAa | AA

D  bDc | a

E  EaD | Ed

A  AaE | ADE | 

B  DbE | bE

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

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

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

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

4.

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

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

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

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

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

5.

(а)

(б)

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

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

G: S  dDS | cBA | 

D  dD | aAc| b

A  aAca | bB

B  cB | 

6.

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

ПОЛИЗ

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