litceysel.ru
добавить свой файл
1

Грамматики и конечные автоматы.


1. Дана регулярная грамматика с правилами:


S  S0 | S1 | P0 | P1

P  N.

N  0 | 1 | N0 | N1 .


Построить по ней диаграмму состояний и использовать ДС для разбора цепочек : 11.010 , 0.1 , 01. , 100 . Какой язык порождает эта грамматика ?


2. Дана ДС.





  1. Осуществить разбор цепочек 1011 , 10+011 и 0-101+1 .

  2. Восстановить регулярную грамматику, по которой была построена данная ДС.

  3. Какой язык порождает полученная грамматика ?


3. Пусть имеется переменная c и функция gc(), считывающая в с очередной символ анализируемой цепочки. Дана ДС с действиями:





  1. Определить, что будет выдано на печать при разборе цепочки 1+101//p11+++1000/5?

  2. Написать на Си анализатор по этой ДС.


4. Построить регулярную грамматику, порождающую язык

L = {(abb)k| k  1},

по ней построить ДС, а затем по ДС написать на Си анализатор для этого языка.


5. Построить ДС, по которой в заданном тексте, оканчивающемся на , выявляются все парные комбинации <>, <= и >= и подсчитывается их общее количество.


6. Дана регулярная грамматика:

S  A

A  Ab | Bb | b

B  Aa

Определить язык, который она порождает; построить ДС; написать на Си анализатор.


7. Написать на Си анализатор, выделяющий из текста вещественные числа без знака (они определены как в Паскале) и преобразующий их из символьного представления в числовое.


8. Даны две грамматики G1 и G2.

G1: S  0C | 1B |  G2: S  0D | 1B

B  0B | 1C |  B  0C | 1C


C  0C | 1C C  0D | 1D | 

D  0D | 1D

L1 = L(G1);

L2 = L(G2).

Построить регулярную грамматику для:


  1. L1L2

  2. L1L2

Если разбор по ней оказался недетерминированным, найти эквивалентную ей грамматику, допускающую детерминированный разбор.


9. Написать леволинейную регулярную грамматику, эквивалентную данной праволинейной, допускающую детерминированный разбор.


a) S  0S | 0B b) S  aA | aB | bA

B  1B | 1C A  bS

C  1C |  B  aS | bB | 


c) S  aB d) S  0B

B  aC | aD | dB B  1C | 1S

C  aB C  

D  


10. Для данной грамматики

  1. определить ее тип;

  2. какой язык она порождает;

  3. написать Р-грамматику, почти эквивалентную данной;

  4. построить ДС и анализатор на Си.

S  0S | S0 | D

D  DD | 1A | 

A  0B | 

B  0A | 0


11. Написать анализатор по следующей грамматике:

a) S  C b) S  C

B  B1 | 0 | D0 C  B1

C  B1 | C1 B  0 | D0

D  D0 | 0 D  B1


c) S  A0

A  A0 | S1 | 0


12. Грамматика G определяет язык L=L1L2, причем L1 L2 =. Написать регулярную грамматику G1, которая порождает язык L1L2 (см. задачу 20). Для нее построить ДС и анализатор.

S  0A | 1S

A  0A | 1B

B  0B | 1B | 


13. Даны две грамматики G1 и G2, порождающие языки L1 и L2. Построить регулярные грамматики для

  1. L1 L2

  2. L1 L2

  3. L1  L2


G1: S  0B | 1S G2: S  B

B  0C | 1B |  A  B1 | 0

C  0B | 1S B  A1 | C1 | B0 | 1


C  A0 | B1


Для грамматики b) построить ДС и анализатор.


14. По данной грамматике G1 построить регулярную грамматику G2 для языка L1 L1, где L1 = L(G1); по грамматике G2 - ДС и анализатор.

G1: S  0S | 0B

B  1B | 1C

C  1C | 


15. Написать регулярную грамматику, порождающую язык:


  1. L = { |   {0,1}* , где за каждой 1 непосредственно следует 0};

  2. L = {11 |  {0,1}+ , где между вхождениями 1 нечетное количество 0};

по ней построить ДС, а по ДС написать на Си анализатор.

16. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последовательность "точек", "тире" и "пауз" (например, ..--. .- ...-). Выходом являются соответствующие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы.