Операции над языками. Классификация грамматик и языков по Хомскому. Конечные автоматы. Регулярные множества и автоматные языки. Построение распознавателей для КС-языков

3. Перечислите цепочки, выводимые из х (см. упражнение 2).

4. Выводима ли из х (см. упражнение 2) цепочка aaabbbbb?

5. Языком, порождаемым формальной грамматикой,

называется множество ___________, выводимых из ___________.

6. Определите язык, порождаемый грамматикой (см. упражнение 2).

7. Принадлежит ли цепочка 01011010 языку L(G), если G=<{0,1},{S, A, B},S,P>, где P={S®0S1½AS½BS1½e, A®S01½0A½1, B®1S0½B0½0}?

8. Определить язык, порожденный грамматикой G=<T,N,S,P>:

a)  N={S, 0, 1}, T={a, b}, P={S®10a½1S, 0®b1, 1®a};

b)  N={S, 0, 1, 2}, T={3, 4}, P={S®S312½302, 0®21,  

12®4, 2®e};

c)  N={S, A, B, C, D}, T={0, 1}, P={S®10A1½01B0½1CD1½D01,

 A®0A1½1B1½0C,     B®1C½0A11½B0,     C®A10½B1, 

          D®10½A00½B0½1C};

d)  N={S, 0, 1, 2, 3}, T={a, b, c}, P={S®013½S013, a2a®abca,

 3®ab, 1a®caa, 0ca®c};

e)  N={S, A, B, C, D}, T={0, 1}, P={S®0A0½1B0½1D1½0C1,

 A®01B½B1,      C1®A10½0A0,      1B®0C½C11, 

           D®A0½1C1½0D0½11½B00}.

9. Определите состав терминального и нетерминального словарей грамматики   G=<T,N,S,P>   с правилами 

  P={S®BC½AD½DE½SE½AB, A®EBD½AC½E, D®AB½DE½A,

 ED®CB½AE½BC, C®A½BC½E, B®A½BCD, CB®A½B,

 AEC®EC½AC½A}, если язык, порождаемый данной грамматикой, не пуст.

10. Построить грамматику, порождающую язык:

а) L={0ⁿ1^k2ⁿ½n³1, k³0;

b) L={0ⁿ1^m2^m3ⁿ½n³1, m³1};

c) L={0ⁿ1ⁿ1^m0^m½n³1, m³1};

d) L={aⁿ111b^m½n³1, m³n};

e) L={1ⁿ0a^m!!!b^m02^k½n³1, m³1, k³n};

f) L={(aⁿ=bⁿ)(c^m=d^m)½n³1, m³1};

g) L={aⁿ–b^m½n³1, m³1}U{c^k+d^k½k³1}.

11. Можно ли в грамматике G=< {1}, {S}, S,{S®S1S}> вывести цепочку 1³¹, и если нет, то каким образом следует изменить правила грамматики G, чтобы это стало возможно?

12. Найти отличие языков L(G₁) и L(G₂), если G_i = <T_i,N_i,S_i,P_i>, i=1,2, N₁=N₂={S,A,B}, T₁=T₂={0,1,2}, P₁={S®0A1, A®B½0A1, B®2B½e} P₂={S®0A1, A®B½0A1, B®2B½2}.

13. Чем отличаются грамматики G₁ и G₂ языков 

      L(G₁)={aⁿ0^mbⁿ½n³1, m³0} и L(G₂)={aⁿ0^kbⁿ½n³1, k³1}?

Занятие  4.  Операции над языками

Цель занятия: выработать навыки оперирования с формальными языками как с множествами заданной структуры. Уметь строить языки, используя основные операции над ними  и уметь по заданной формуле языка определить, из каких простейших языков его можно построить и с помощью каких операций.

Методические указания

Что необходимо знать:

·  основные понятия теории множеств (операции над множествами, эквивалентность множеств, отношения и их свойства) из курса дискретной математики,

·  операции конкатенации и подстановки языка в язык,

·  доказательство коммутативности диаграммы для операции объединения.

G₁             G₂ ----------------à G3

|                  |                              |

|                  |                              |

|                  |                              |

v                v                             v

L(G₁)      L(G₂ )  ¾¾¾¾¾> L(G₃)

Основные определения

1. Основные операции:

L3 = L1 È L2 = {x| x Π L1 или x Π L2};

L3 = L1 Ç L2 = {x| x Π  L1  и  x Π L2};

L3 = L1 \ L2  = {x| x  Î L1  и  x  Ï  L2};

L3 = L1 ° L2  = {x=yz| y Π L1,а z  Î L2};

L3 = L* = ,

где

при n > 1;  

L3 =

L3 = подстановка языков L₁, ....,L_n в язык L  вместо символов 
a₁, ...,a_n есть операция, сопоставляющая языку L в словаре T =
= {a₁, ...,a_n} и языкам L₁, ...,L_n в словарях T₁, ...,T_n соответственно следующий язык в словаре T₁ ...T_n:

{  Î L, } L^{^}

где L^{^} = {e},если eÎL и  L^{^} = Æ, если  е Ï L;

L3 = w\L = { j | wj Î L };

L3 = L/w = { j | jw Î L }.

2. Базовыми языками будем называть языки, которые не могут быть получены из других языков с помощью операций над этими языками. Например,  L₁ = {a};   L₂ = {aⁿbⁿ  |n ³ 1};

L₃ ={aⁿbⁿcⁿ | n ³ 1}.

Задачи и упражнения

1. Определить грамматику, порождающую язык:

a)  L(G) = L₁\(L₂UL₃),           L₁ = {w½wÎ{0,1}^*},

           L₂  =  {0w1½wÎ{0,1}^*},   L₃  = {0w0½wÎ{0,1}^*}.

b)  L(G) = L₂\L₁, L₁ = {b²w½wÎ{a,b}^*}, L₂ = {w^–1½wÎ{a,b}^*}.

c)  L(G) = L₁UL₂, L₁  = {0ⁿ1ⁿ½n³2},        L₂={w½wÎ{0,1}^*}.

d)  L(G) = L₁\L₂, L₁ = {w½wÎ{0,1}^*},     L₂ = {0ⁿ1ⁿ½n ³ 1}

e)  L(G) = L₁IL₂, L₁ = {01ⁿ1ⁿ0½n ³ 1},   L₂ = {01^m0½m ³ 0}.

f)  L(G) = L₂\L₁, L₁ = {ab^2ka½k ³ 0},       L₂ = {ab^ma½m ³ 1}.

2. Является ли грамматика G=<T,N,S,P> с правилами

P = {S® A0, A ® B0, B ® A1} грамматикой языка L₁\L₂,

где L₁ = {01^2k0½k ³ 1}, L₂ = {01^m0½m ³ 0}.

3. Чему равно кардинальное число множества терминальных цепочек, порожденных грамматикой G = < T, N, S, P >, если:

a)  N = {S, A}, T = {a, b}, P={S® aAb, A® aAb½e};

b)  L(G) = {aⁿbⁿc^md^m½n ³ 1, m ³ 1},

c)  L(G) = L₁UL₂, L₁ = {aⁿbⁿ½n³1},  L₂  = {0^m1^m2^m½m ³ 1}.

4. Среди всех ранее рассмотренных языков найти пары эквивалентных.