Приклади завдань для контрольної роботи
1. f(x) = sg(x):
2. f(x, y) = max(x, y):
3. f(x) = [x/2]:
4. f(x, y) =
5. f(x, y) = 2x+y+1
6. f(x) = nsg(x);
7. f(x, y) = min(x, y);
8. f(x, y, z) = max(x, y)+z;
9. f(x, y, z) = mіп(x+y, z);
10. f(x, y) = xy.
11. f(x, y)=|x–y|
12. f(x)=
13. f(x, y) = (x+1)2×y;
14. f(x, y) = HCK(x, y);
15. f(x, y) = (x+1)×2y ;
16. f(x) = x4–x;
17. f(x) = 2x–3x
18. f(x, y) = 3x×(y+1);
19. f(x) = (2x)!!
20. f(x) = [log2 x];
21. f(x, y, z) = xy+z
22. f(x, y) = ;
23. f(x, y) = mod(x, y).
24. f(x, y) = .
25. f(x, y, z) = min(mod(x, y), z);
26. f(x, y, z) = mod(x+1, min(y, z));
27. f(x, y, z) = HCK(x, y+z);
28. P(x): "x – непарне число";
29. P(x): "x – парне число".
30. P(x,y): "x=y":
31. P(x,y): "х³y";
32. P(x,y): "х>y";
33. P(x,y): "х¹y";
34. P(x,y): "х<y".
35. P(x): "x не кратне 2";
36. P(x): "x не кратне 3";
37. P(x,y,z): z= (x div y)
38. P(x,y,z): z=x%y
39. P(x,y): x=y!
40. P(n,m): m=n-те число Фібоначі
Тема 2. Формальні мови та граматики
Теорія …
+ домовленість: якщо не фіксується інше, то вважаємо, що великими латинськими літерами позначаються нетермінальні символи граматики, а малими – термінальні.
Побудова мови за допомогою системи рівнянь з регулярними коефіцієнтами
Завдання 2.1. Нехай задано мову L, яку описує регулярний вираз r = a*ba*. Побудувати за регулярним виразом граматику і систему лінійних рівнянь, розв’язати систему.
Розв’язок.
1) Побудуємо праволінійну граматику G для мови L. G = <VT, VN, Pr, S>.
VT = {a, b}; VN = {S, S1, S2}; Pr = {S->aS1; S->bS2; S1->aS1; S1->bS2; S2->aS2; S2->ε}, S ={S}
Отже G = < {a, b}; {S, S1, S2}; {S->aS1; S->bS2; S1->aS1; S1->bS2; S2->aS2; S2->ε}, {S}>
2) Тепер побудуємо систему лінійних рівнянь для цієї граматики:
|
|
Кількість рівнянь дорівнює кількості нетерміналів. В нашому випадку 3. Кожному нетерміналу ставимо у відповідність змінну : S-> X1; S1->X2; S2->X3. Система має такий вигляд:
X1 = p1+ q11X1 + q12X2 + q13X3
X2 = p2+ q21X1 + q22X2 + q23X3
X3 = p3+ q31X1 + q32X2 + q33X3
pi визначається так : для всіх продукцій вигляду Xi ->γj, pi = . Всі qij визначаються так: для всіх продукцій вигляду Xi ->γjXj, qij = . Маємо:
X1 = X2a + X3b
X2 = X2a + X3b
X3 = ε+ X3a
Зауважимо, що розв’язком рівняння виду X = Xα + β буде регулярний вираз βα*, що доводиться підстановкою. Систему рівнянь розв’язуємо методом Гауса. Розв’язком системи ми вважаємо Xk вираз при змінній, яка відповідає нетерміналу аксіоми. В нашому випадку буде регулярній вираз при змінній X1. Робимо послідовні підстановки:
X1 = X2a + X3b підставляємо у всі рівняння. Рівняння X2 = X2a + X3b має розв’язок X2=(X3b)a*.Підставляємо X2 у останнє рівняння. Маємо X3 = ε+ X3a. Тепер робимо зворотню підстановку: розв’язком останнього рівняння буде X3 = εa* = a*. Підставляємо X3 в перше і друге рівняння : X1 = X2a + a*b; X2 = X2a + a*b. Розв’язуємо друге рівняння : X2 = a*ba* і підставляємо в перше рівняння X1 = a*ba*a + a*b = a*b(a*a + ε) = a*ba*. Отже отримали регулярний вираз a*ba*, який описує ту саму мову, що і граматика, побудована за початковим регулярним виразом.
|
|
2.2. Побудова мови методом наближень
Завдання 2.2. Задано мову L, яку описує регулярний вираз r = anban. Побудувати граматику і методом послідовних наближень побудувати мову.
Розв’язок.
Побудуємо породжуючу граматику G для мови L: G = <{a, b}, {S}, {S->aSa, S->ε}, {S}>. Покажемо, що мова, яку описує побудована граматика складається зі слів вигляду anban і тільки з них.
Запишемо для цієї граматики рівняння : S = {b} {a}S{a}. Тоді функція φ(Li) = {b} {a}Li{a}.
Розглянемо L0, як перше наближення мови L : L0 = {b}. Застосовуючи метод послідовних наближень маємо L1 = φ(L0) = {b} {a}{b}{a} = {b} {aba}. Нехай Lk= , тоді Lk+1 = φ(Lk) = φ( ) = {b} {a} {a} = {b} = .
Очевидно, що послідовність (Lk) – зростаюча, отже існує границя – L′= . Отже L містить у собі L′ (це очевидно, бо для кожного слова w мови L′ існує таке невід’ємне n, що слово w = anban ).
Покажемо зворотне включення. Візьмемо довільне слово w з мови L. Зрозуміло, що це слово має вигляд : w = anban. Покажемо, що це слово належить мові L′. Це слідує з існування виводу цього слова у граматиці. Для виводу слова необхідно застосувати до аксіоми S правило S->aSa n разів, а потім правило S->b один раз. Отже мови L і L′ однакові і граматика G задає мову L і тільки її.
|
|
2.3. Побудова граматики за мовою
Завдання 2.3. Нехай задано мову L = {anbn|n>=0}. Побудувати граматику і показати, що вона породжує усі слова мови і тільки їх.
Розв’язок.
1) Побудуємо граматику G для мови L. G = <VT, VN, Pr, S>.
VT = {a, b}; VN = {S}; Pr = {S→aSb; S→ε}, S ={S}.
Отже G = < {a, b}; {S}; {S→aSb; S→ε}, {S}>
2)Перевіримо, що граматика породжує всі слова мови.
Поділимо все, що породжує граматика на такі типи (класи):
1) akSbk
2) akbk , k>=0
Можливо, доведеться їх змінити. Адже нам треба отримати такі класи, щоб застосування правил виведення граматики не виводило нас за їх межі.
Тепер побудуємо наступну таблицю:
типи | 1 | 2 | |
правила | |||
1: S→aSb | 1 | - | |
2: S→ε | 2 | - |
Тобто, застосування 1-го правила до 1-го типу залишає слово у 1 типі.
2-го правила до 1-го типу – переводить у 2-ий тип.
Жодне правило не застосовне до слів 2-го типу(-).
1тип.1пр) akSbk →1 akaSbbk = a(k+1)Sb(k+1)
1.2) akSbk →2 akbk
Таким чином, ми поділили все, що породжує граматика на «замкнені у своїх межах» класи. Тобто все те, що вона породжує, не виходить за їх межі.
3)Порівняємо тепер вихідну мову, і мову, породжену побудованою граматикою.
|
|
(akSbk)∩VT*=Ø
(akbk , k>=0)∩VT*= akbk , k>=0
Тобто ця граматика породжує усі слова мови і тільки їх.
Завдання 2.4. Нехай задано мову L = {anbncn|n>=0}. Побудувати граматику і показати, що вона породжує усі слова мови і тільки їх.
Розв’язок.
1) Побудуємо граматику G для мови L. G = <VT, VN, Pr, S>.
VT = {a, b, c}; VN = {S; B}; Pr = {S→aBSc; S→ε; Ba→aB; Bc→bc; Bb→bb}, S ={S}.
Отже G = < {a, b, c}; {S; B}; {S→aBSc; S→ε; Ba→aB; Bc→bc; Bb→bb}, {S}>
2)Перевіримо, що граматика породжує всі слова мови.
Поділимо все, що породжує граматика на такі типи(класи):
1) (aB)nScn
2) ycn , де |y|a = |y|B = n, y = (a|B)*
3) ycn , де |y|a = |y|b + |y|B = n, y = (a|B)*b*b
Можливо, доведеться їх змінити. Адже нам треба поділити на класи так, щоб застосування правил виведення граматики не виводило нас за межі цих класів.
Тепер побудуємо наступну таблицю:
типи | 1 | 2 | 3 | |
правила | ||||
1: S→aBSc | 1 | - | - | |
2: S→ε | 2 | - | - | |
3: Ba→aB | 1 | 2 | 3 | |
4: Bc→bc | - | 3 | - | |
5: Bb→bb | - | - | 3 |
Тобто, застосування 1-го правила до 1-го типу залишає слово у 1 типі.
2-го правила до 1-го типу – переводить у 2-ий тип.
1тип.1пр)(aB)nScn →1 (aB)naBSccn = (aB)(n+1)Sc(n+1)
1.2) (aB)nScn →2 (aB)ncn = ycn , де |y|a = |y|B = n, y = (a|B)*
1.3) (aB)nScn →3 yScn , де |y|a = |y|B = n, y = (a|B)*
Так як клас yScn , де |y|a = |y|B = n, y = (a|B)*, який ми отримали внаслідок застосування правила 3 до 1-го класу включає у себе клас 1 ((aB)nScn), тому змінимо клас 1 на цей отриманий клас. Попередні правила та виводи не зміняться.
Правила 4 та 5 незастосовні до класу 1.
Правила 1, 2, 5 незастосовні до класу 2.
2.3) ycn →3 ycn , де |y|a = |y|B = n, y = (a|B)*
2.4) ycn →3 qcn , де |y|a = |y|B = n, y = (a|B)*, |q|a = |q|b + |q|B = n, q = (a|B)*b*b
Правила 1, 2, 4 незастосовні до класу 3.
3.3) ycn →3 ycn , де |y|a = |y|b + |y|B = n, y = (a|B)*b*b
3.5) ycn →3 ycn , де |y|a = |y|b + |y|B = n, y = (a|B)*b*b
Таким чином, ми поділили все, що породжує граматика на «замкнені у своїх межах» класи.
1) yScn , де |y|a = |y|B = n, y = (a|B)*
2) ycn , де |y|a = |y|B = n, y = (a|B)*
3) ycn , де |y|a = |y|b + |y|B = n, y = (a|B)*b*b
Тобто все те, що вона породжує, не виходить за їх межі.
3)Порівняємо тепер вихідну мову, і мову, породжену побудованою граматикою.
(yScn , де |y|a = |y|B = n, y = (a|B)*)∩T*=Ø
(ycn , де |y|a = |y|B = n, y = (a|B)*)∩T*= {ε}
(ycn , де |y|a = |y|b + |y|B = n, y = (a|B)*b*b)∩T* = ycn , де |y|a = |y|b + |y|B = n, y = (a|B)*b*, причому |y|B = 0, тому y = a*b*b= anbn.
Тобто:
(ycn , де |y|a = |y|b + |y|B = n, y = (a|B)*b*b)∩T* = anbncn .
Отже, ця граматика породжує усі слова мови і тільки їх.
Завдання 2.5. Нехай задано мову L = {anbm|m>n}. Побудувати граматику G, яка породжує мову L, та довести L(G)=L.
Розв’язок.
Побудуємо граматику G для мови L. G = <VT, VN, Pr, S>.
VT = {a, b}; VN = {S; B; C}; Pr = {S→aSb; S→B; B→Cb; C→Cb; C→ε}; S ={S}.
Отже G = < {a, b}; {S; B; C}; {S→aSb; S→B; B→Cb; C→Cb; C→ε}, {S}>.
1) Граматика G для мови має наступні правила виводу:
2) Доведемо, що
В граматиці G можна побудувати наступні види слів:
Покажемо, що це всі можливі види слів, що породжуються в граматиці – для цього відобразимо, як правила виводу перетворюють один вигляд в інший, таким чином показавши замкненість множини слів (точніше, їх видів) відносно виведення:
типи слів правила виводу | 1 | 2 | 3 |
1 | 1 | - | - |
2 | 2 | - | - |
3 | - | 2 | - |
4 | - | 3 | - |
Отже, очевидно, що в граматиці виводяться лише слова 3 типу, оскільки лише вони складаються з терміналів.
Таким чином доведено . Доведемо тепер .
Покажемо можливість виводу будь-якого слова з L.
Вивід слова з аксіоми S повинен бути наступним:
1) Правило 1) застосовується n разів.
2) Правило 2) застосовується m-n-1 разів.
3) Правило 3) застосовується 1 раз.
Таким чином, доведено взаємне включення множин L(G) та L.
Завдання 2.6.
1) Побудувати породжувальну граматику G для мови
2) довести, що
3) довести, що мова L не є КВ мовою.
Розв’язок.
1) Граматика G для мови має наступні правила виводу:
2) Доведемо, що
В граматиці G можна побудувати наступні види слів:
Покажемо, що це всі можливі види слів, що породжуються в граматиці – для цього відобразимо, як правила виводу перетворюють один вигляд в інший, таким чином показавши замкненість множини слів (точніше, їх видів) відносно виведення:
типи слів правила виводу | 1 | 2 | 3 | 4 |
1 | 1 | - | - | - |
2 | 1 | - | - | - |
3 | 2 | - | - | - |
4 | 1 | 2 | 3 | - |
5 | - | 3 | 3,4 | - |
Отже, очевидно, що в граматиці виводяться лише слова 4 типу.
Таким чином доведено . Доведемо тепер .
Покажемо можливість виводу будь-якого слова з L.
Вивід слова з аксіоми S повинен бути наступним:
1) Правило 1) застосовується n разів.
2) Правило 2) застосовується m-n разів.
3) Правило 3) застосовується 1 раз.
4) Правило 4) застосовується, поки застосовне ((n-1)*(n-2)/2 разів).
5) Правило 5) застосовується m-1 раз.
3) Довести, що мова L не є КВ мовою.
Якби мова L була КВ-мовою, то існували б ланцюжки u, v, t1, t2, x Î{a*,b**,c*} такі, що ut1ix t2ivÎL для всіх i=0,1,…. Зрозуміло, що t1 (так само як і t2) не може складатися з різних символів (інакше для деякого i ланцюжок ut1ix t2iv не буде належати L. Але якщо t1 складається лише з одного символу, то збільшуючи i можна порушити баланс символів a,b,c. Тому мова L не може бути КВ-мовою.
Завдання для самостійної та контрольної роботи
Побудувати граматику G, яка породжує задану мову L, та довести L(G) = L для L:
1) anbm, n>=m
2) a*|b*| c*
3) (a|b|c)*
4) (a|b)*c
5) a*ba*b
6) a*b|b*a
7) anbncn
8) anbcm, m>n
9) anb2n
10) a*|ba*b
11) anbn+2
12) a*b*c*
13) anbmcn
14) a|b*c| cb*
15) a*b|a|b
16) (a|b)*a*
17) (abc)*
18) (ab)*|ab
19) a*(a|b)*b*
20) (ab)*|(a|b)*
Дата добавления: 2018-04-05; просмотров: 347; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!