V3_2009 (1115096)

1

2

3

4

5

6

7

8

9

10

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

S  Bc | Sa| ε

B  Ad

A  d

A  bB

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

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

Ответ:

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

Ответ:

2. (а) Дать определение приведенной КС-грамматики.

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

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

G₁ : S  BA

A  bAa | a | 

B  b | 

G₂ : S  E | BA

D  dDd | c | 

E  ED | Ed

A  bAa | ADE | a | 

B  DbE | b

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

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

G:

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

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

4.

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

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

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

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

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

5.

(а)

(б)

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

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

G: S  aAeS | bB | 

A  aAd | bC | aC

C  cC | 

B  eS | d

6.

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

ПОЛИЗ

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