Языки и грамматики

Страницы работы

5 страниц (Word-файл)

Посмотреть все страницы

Скачать файл

Фрагмент текста работы

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

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

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

b) N={S, 0, 1, 2}, A={3, 4}, P={S®S312½302, 0®21, 12®4, 2®e};

c) N={S, A, B, C, D}, A={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}, A={a, b, c}, P={S®013½S013, a2a®abca, 3®ab, 1a®caa, 0ca®c};

e) N={S, A, B, C, D}, A={0, 1}, P={S®0A0½1B0½1D1½0C1, A®01B½B1, C1®A10½0A0, 1B®0C½C11, D®A0½1C1½0D0½11½B00}.

3. Определить состав терминального и нетерминального словарей грамматики G=<N, A, P, S> с правилами 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}.

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

a) 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}.

5. Пусть грамматика G=<N, A, P, S> имеют вид: N={S, A, B}, A={a, b} P={S®AB, A®Aa½bB, B®a½Sb}. Построить деревья выводов цепочек:

а) baabaab,b) bBABb, c) baSb.

6. Построить левый и правый выводы цепочки baabaab в грамматике из задания 4.

7. Построить левый вывод цепочки if bÙb then if bÚb then s else s else s в грамматике G=<{S, B}, {b, s, Ù, Ú, if, then, else}, { S®if B then S else S½s, B®BÙB½BÚB½b}, S>.

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

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

10. Чем отличаются грамматики G₁ и G₂ языков L(G₁)={aⁿ0^mbⁿ½n³1, m³0} и L(G₂)={aⁿ0^kbⁿ½n³1, k³1}?

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

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}.

12. Является ли грамматика G=<N, A, P, S>, с правилами P={S®A0, A®B0, B®A1} грамматикой языка L₁\L₂, где L₁={01^2k0½k³1}, L₂={01^m0½m³0}.

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

a) N={S, A}, A={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}.

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

15. На декартовом произведении L₁´L₂, где L₁={aⁿbⁿ½n³1}, L₂={a^2kb^2k½k³1} определено бинарное отношение R={(x, y)½ xÎL₁, yÎL₂, длина цепочки x равна длине цепочки y}. Исследовать Rна симметричность, рефлексивность и транзитивность.

16. Задано бинарное отношение R={(x, y)½ xÎL₁, yÎL₂, x – подцепочка цепочки y} на множестве L₁´L₂, где L₁={0ⁿ1^k1ⁿ½n³1, k³0}, L₂={0ⁿ1ⁿ½n³1}. Является ли оно отношением эквивалентности?

17. Найти результат подстановки языка L(G₁) в язык L(G₂), если G_i=(N_i, A_i, P_i, S_i), i=1,2 и

a) N₁={S₁}, A₁={0}, P₁={S₁®S₁0½e}, N₂={S₂}, A₂={1}, P₂={S₂®1³S₂0½e};

b) N₁={S₁, S₃}, A₁={0, 1}, P₁={S₁®0S₂11, S₂®0S₂1½e},

N₂={S₂, S₄}, A₂={a, b}, P₂={S₂®a²S₄b, S₄®bS₄a½e};

18. Построить грамматику для языка – результата подстановки языка L₂ в язык L₁, если L₁={01ⁿ½n³1} и L₂={aⁿbⁿ½n³1}.

19. С помощью подходящих операций постройте язык L={(01)ⁿ½n³0} из языков:

L₁={aⁿ½n³0}, L₂={bⁿ½n³0}, L₃={01}, L₄={e}, L₅={w½wÎ{a,b}^*}, L₆={w½wÎ{b,c}^*}.

20. Из языков задания 19 постройте язык L={01aⁿ½n³1}.

21. Из языков задания 19 постройте язык L={w½wÎ{a,b,c}^*}.

22. Пусть грамматика G₁=<N₁, A₁, P₁, S₁> определяет язык L₁, а грамматика G₂=<N₂, A₂, P₂, S₂> определяет язык L₂, постройте грамматику G=<N, A, P, S> для языков:

a) L=L₁UL₂ b) L=L₁°L₂.

23. Пусть А-грамматика G₁=<N₁, A₁, P₁, S₁> определяет А-язык L₁, а А-грамматика G₂=<N₂, A₂, P₂, S₂> определяет А-язык L₂, постройте А-грамматику G=<N, A, P, S> для языков:

a) L=L₁UL₂ b) L=L₁°L₂.

24. Какие из приведенных ниже грамматик являются А-грамматиками?

a) G₁=<{a,b}, {S}, {S®ab½aSb}, S>,

b) G₂=<{a,b}, {S,A,B}, {S®AB, A®aA½e, B®bB½e }, S>,

c) G₃=<{a,b}, {S}, {S®aS½bS½e}, S>,

d) G₄=<{a,b}, {S,A}, {S®aSb½aA½e, A®aA½e}, S>,

e) G₅=<{a,b}, {S,A,B}, {S®aA½bB, A®aA½bA, B®aB½bB½b}, S>,

f) G₆=<{a,b}, {S}, {S®aS½Sb½a½b}, S>,

g) G₇=<{3,4}, {S,1,2}, {S®S312½302, 0®21, 12®4, 2®e}, S>,

h) G₈=<{a,b,1,2}, {S,A,B}, {S®aB½bB½a½b, B®AB, A®a½b½1½2}, S>,

i) G₉=<{a,b}, {S,A,B}, {S®aАа, A®aABa½b, aB®Ba, bB®bb}, S>.

25. Какие из грамматик из задания 24 являются линейными?

26. Какие из грамматик из задания 24 являются КС-грамматиками?

27. Какие из грамматик из задания 24 являются НС-грамматиками?

28. Какие из грамматик из задания 24 задают А-языки?

29. Какие из грамматик из задания 24 задают КС-языки?

30. Какие из грамматик из задания 24 задают НС-языки?

31. Докажите, что если грамматика G=<N, A, P, S> содержит правила P' (т.е. P'ÌP), то она неоднозначна.

a) P'={A®AA½a};

b) P'={A®AaA};

c) P'={A®aA½Ab};

d) P'={A®aA½aAb};

e) P'={A®Ab½aAb}.

32. Определите какие из следующих языков являются неоднозначными:

L₁={aⁿb^mc^mdⁿ½n,m³1}U{a^mb^mcⁿdⁿ½ n,m³1},

L₂={aⁿb^mc^kd^mpⁿ½n,m,k³1}I{a^mb^mc^kdⁿpⁿ ½n,m,k³1},

L₃={aⁿb^m½n,m³1, m³n}.

33. Определите какие из следующих языков

L₁={(a,ba)^*},

L₂={(ab)^m½m³0},

L₃=L₁UL₂,

L₄=L₁°L₂

L₅={aⁿb^md^k½n,m,k³1},

L₆={aⁿb^md^k½n,m,k³1, m³n},

L₇={(ab)ⁿ(ab)ⁿ½n³0},

L₈={w½wÎ{a,b}^*}

L₉=L₇UL₈,

L₁₀=L₇°L₈,

L₁₁={aⁿbⁿc^md^m½n,m,k³1, m³n},

L₁₂={a^mbⁿcⁿd^m½n,m,k³0, m³n},

L₁₃=L₅UL₇,

L₁₄=L₅°L₇

являются a) А-языками b) КС-языками c) НС-языками?

34. Постройте А-грамматику для языков

L₁={(01)ⁿ(10)^m½n³0, m³1}, L₂={aⁿba½n³0}.

35. Дан граф конечного автомата

a) построить КА,

b) детерминировать КА,

c) минимизировать ДКА,

d) построить А-грамматику по МКА,

e) определить язык.

36. По конечному автомату (КА) построить детерминированный конечный автомат (ДКА), по ДКА построить минимальный конечный автомат (МКА).

	a	b
A	F	B
B	E	D
C	C	F
D	D	A
E	B	C
F	F	E

37. Дан граф конечного автомата

a) построить КА,

b) детерминировать КА,

c) минимизировать ДКА.

38. Используя результаты из задачи 34 для каждого языка:

a) построить граф КА по грамматике G_A,

b) построить КА,

a) детерминировать КА,

b) минимизировать ДКА.

39. Постройте синтаксические схемы и схемы переходов между состояниями для следующих регулярных выражений:

a) 0^*, b) 0⁺, c) 0³, d) 01, e) 0+1⁺, f) (0+1)⁺,

g) [(01)^*+01^*]10⁺, h) (a+b)^*aba+ab^*aba.

40. Для регулярного выражения (a+b)^aba+ab^aba:

a) построить синтаксическую схему РВ;

b) упростить РВ по аксиомам;

c) построить синтаксическую схему УРВ;

d) построить схему переходов между состояниями для УРВ;

e) построить конечный автомат;

f) построить грамматику;

g) определить язык.

41. Дан язык L={baⁿw½n³0, wÎ{a, b}^}U{b^kw½k³1, wÎ{a, b}^}U{b}

a) L®G_A®КА®ДКА®МКА,

b) L®РВ®УРВ®КА, сравните результаты, полученные в a) и b).

42. Дан граф конечного автомата

a) КА®ДКА®МКА®РВ,

b) КА®РВ®УРВ,

c) сравните результаты, полученные в a) и b).

43. Дан граф конечного автомата

a) КА®ДКА®МКА®РВ,

b) КА®РВ®УРВ,

c) сравните результаты, полученные в a) и b),

d) определите язык, распознаваемый данным конечным автоматом.

44. В грамматике G=<{a, b}, {S, A, B, C}, {S®AB, A®a, B®b, C®CA}, S> найдите и устраните непродуктивные символы.

45. В грамматике G=<{a, b, c, d, e, f, g}, {S, A, B, Q}, P, S> найдите и устраните недостижимые символы, если:

a) P={S®aAcg³aBd, A®aAc½d, B®aBd½c, Q®aBc½daf},

b) P={S®aAb½cBd, A®aA½Ab½gg, B®cBd½ff, Q®cAb½gf}.

46. В грамматике G=<N, T, P, S> найдите и устраните бесполезные символы, если:

a) N={S, A, B}, T={a, b}, P={S®A½a, A®AB, B®b},

b) N={S, A, B, D, F, C}, T={p, d, g, f}, P={S®AB½Ap, A®g, B®DF½d, D®d, F®fF, C®p},

c) N={S, A, B}, T={a, b}, P={S®AB½Ap, A®aB½bS½b, B®AB½Ba, B®aS½b}.

47. Используя в качестве примера грамматики из предыдущего задания докажите, что шаги в алгоритме удаления бесполезных символов не перестановочны (т.е. нельзя вначале удалить недостижимые символы, а потом удалить непродуктивные).

48. Преобразуйте грамматику G=<N, T, P, S> в грамматику без e-правил, если:

Информация о работе

ВУЗ:

Новосибирский государственный технический университет (НГТУ)

Размер файла:

126 Kb

Скачали: