Приклади завдань для контрольної роботи

 

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) = x^y.

11. f(x, y)=|x–y|

12.  f(x)=

13.  f(x, y) = (x+1)²×y;

14. f(x, y) = HCK(x, y);

15. f(x, y) = (x+1)×2^y ;

16. f(x) = x⁴–x;

17. f(x) = 2^x–3x

18. f(x, y) = 3^x×(y+1);

19.  f(x) = (2x)!!

20. f(x) = [log₂ x];

21.  f(x, y, z) = x^y+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, S₁, S₂}; Pr = {S->aS₁; S->bS₂; S₁->aS₁; S₁->bS₂; S₂->aS₂; S₂->ε}, S ={S}

Отже G = < {a, b}; {S, S₁, S₂}; {S->aS₁; S->bS₂; S₁->aS₁; S₁->bS₂; S₂->aS₂; S₂->ε}, {S}>

2) Тепер побудуємо систему лінійних рівнянь для цієї граматики:

Кількість рівнянь дорівнює кількості нетерміналів. В нашому випадку 3. Кожному нетерміналу ставимо у відповідність змінну : S-> X₁; S₁->X₂; S₂->X₃. Система має такий вигляд:

 

X₁ = p₁+ q₁₁X₁ + q₁₂X₂ + q₁₃X₃

X₂ = p₂+ q₂₁X₁ + q₂₂X₂ + q₂₃X₃

X₃ = p₃+ q₃₁X₁ + q₃₂X₂ + q₃₃X₃

 

p_i визначається так : для всіх продукцій вигляду X_i ->γ_j, p_i = . Всі q_ij визначаються так: для всіх продукцій вигляду X_i ->γ_jX_j, q_ij = . Маємо:

X₁ = X₂a + X₃b

X₂ = X₂a + X₃b

X₃ = ε+ X₃a

 

Зауважимо, що розв’язком рівняння виду X = Xα + β буде регулярний вираз βα^*, що доводиться підстановкою. Систему рівнянь розв’язуємо методом Гауса. Розв’язком системи ми вважаємо X_k вираз при змінній, яка відповідає нетерміналу аксіоми. В нашому випадку буде регулярній вираз при змінній X₁. Робимо послідовні підстановки:

X₁ = X₂a + X₃b підставляємо у всі рівняння. Рівняння X₂ = X₂a + X₃b має розв’язок X₂=(X₃b)a^*.Підставляємо X₂ у останнє рівняння. Маємо X₃ = ε+ X₃a. Тепер робимо зворотню підстановку: розв’язком останнього рівняння буде X₃ = εa^* = a^*. Підставляємо X₃ в перше і друге рівняння : X₁ = X₂a + a^*b; X₂ = X₂a + a^*b. Розв’язуємо друге рівняння : X₂ = a^*ba^* і підставляємо в перше рівняння X₁ = a^*ba^*a + a^*b = a^*b(a^*a + ε) = a^*ba^*. Отже отримали регулярний вираз a^*ba^*, який описує ту саму мову, що і граматика, побудована за початковим регулярним виразом.

 

 

2.2. Побудова мови методом наближень

 

 

Завдання 2.2. Задано мову L, яку описує регулярний вираз r = aⁿbaⁿ. Побудувати граматику і методом послідовних наближень побудувати мову.

 

Розв’язок.

Побудуємо породжуючу граматику G для мови L: G = <{a, b}, {S}, {S->aSa, S->ε}, {S}>. Покажемо, що мова, яку описує побудована граматика складається зі слів вигляду aⁿbaⁿ і тільки з них.

Запишемо для цієї граматики рівняння : S = {b} {a}S{a}. Тоді функція φ(L_i) = {b} {a}L_i{a}.

Розглянемо L₀, як перше наближення мови L : L₀ = {b}. Застосовуючи метод послідовних наближень маємо L₁ = φ(L₀) = {b} {a}{b}{a} = {b} {aba}. Нехай L_k= , тоді L_k+1 = φ(L_k) = φ( ) = {b} {a} {a} = {b}  = .

    Очевидно, що послідовність (L_k) – зростаюча, отже існує границя – L′= . Отже L містить у собі L′ (це очевидно, бо для кожного слова w мови L′ існує таке невід’ємне n, що слово w = aⁿbaⁿ ).

Покажемо зворотне включення. Візьмемо довільне слово w з мови L. Зрозуміло, що це слово має вигляд : w = aⁿbaⁿ. Покажемо, що це слово належить мові L′. Це слідує з існування виводу цього слова у граматиці. Для виводу слова необхідно застосувати до аксіоми S правило S->aSa n разів, а потім правило S->b один раз. Отже мови L і L′ однакові і граматика G задає мову L і тільки її.

 

 

2.3. Побудова граматики за мовою

 

 

Завдання 2.3. Нехай задано мову L = {aⁿbⁿ|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) a^kSb^k

2) a^kb^k , k>=0

Можливо, доведеться їх змінити. Адже нам треба отримати такі класи, щоб застосування правил виведення граматики не виводило нас за їх межі.

 Тепер побудуємо наступну таблицю:

	типи	1	2
правила
1: S→aSb		1	-
2: S→ε		2	-

 

Тобто, застосування 1-го правила до 1-го типу залишає слово у 1 типі.

2-го правила до 1-го типу – переводить у 2-ий тип.

Жодне правило не застосовне до слів 2-го типу(-).

1тип.1пр) a^kSb^k →¹ a^kaSbb^k = a^(k+1)Sb^(k+1)

1.2) a^kSb^k →² a^kb^k

Таким чином, ми поділили все, що породжує граматика на «замкнені у своїх межах» класи. Тобто все те, що вона породжує, не виходить за їх межі.

3)Порівняємо тепер вихідну мову, і мову, породжену побудованою граматикою.

(a^kSb^k)∩VT*=Ø

(a^kb^k , k>=0)∩VT*= a^kb^k , k>=0

Тобто ця граматика породжує усі слова мови і тільки їх.

 

Завдання 2.4. Нехай задано мову L = {aⁿbⁿcⁿ|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)ⁿScⁿ

2) ycⁿ , де |y|_a = |y|_B = n, y = (a|B)*

3) ycⁿ , де |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)ⁿScⁿ →¹ (aB)ⁿaBSccⁿ = (aB)⁽ⁿ⁺¹⁾Sc⁽ⁿ⁺¹⁾

1.2) (aB)ⁿScⁿ →² (aB)ⁿcⁿ = ycⁿ , де |y|_a = |y|_B = n, y = (a|B)*

1.3) (aB)ⁿScⁿ →³ yScⁿ , де |y|_a = |y|_B = n, y = (a|B)*

       Так як клас yScⁿ , де |y|_a = |y|_B = n, y = (a|B)*, який ми отримали внаслідок застосування правила 3 до 1-го класу включає у себе клас 1 ((aB)ⁿScⁿ), тому змінимо клас 1 на цей отриманий клас. Попередні правила та виводи не зміняться.

Правила 4 та 5 незастосовні до класу 1.

Правила 1, 2, 5 незастосовні до класу 2.

2.3) ycⁿ →³ ycⁿ , де |y|_a = |y|_B = n, y = (a|B)*

2.4) ycⁿ →³ qcⁿ , де |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) ycⁿ →³ ycⁿ , де |y|_a = |y|_b + |y|_B = n, y = (a|B)*b*b

3.5) ycⁿ →³ ycⁿ , де |y|_a = |y|_b + |y|_B = n, y = (a|B)*b*b

 

Таким чином, ми поділили все, що породжує граматика на «замкнені у своїх межах» класи.

1) yScⁿ , де |y|_a = |y|_B = n, y = (a|B)*

2) ycⁿ , де |y|_a = |y|_B = n, y = (a|B)*

3) ycⁿ , де |y|_a = |y|_b + |y|_B = n, y = (a|B)*b*b

Тобто все те, що вона породжує, не виходить за їх межі.

3)Порівняємо тепер вихідну мову, і мову, породжену побудованою граматикою.

(yScⁿ , де |y|_a = |y|_B = n, y = (a|B)*)∩T*=Ø

(ycⁿ , де |y|_a = |y|_B = n, y = (a|B)*)∩T*= {ε}

(ycⁿ , де |y|_a = |y|_b + |y|_B = n, y = (a|B)*b*b)∩T* = ycⁿ , де |y|_a = |y|_b + |y|_B = n, y = (a|B)*b*, причому |y|_B = 0, тому y = a*b*b= aⁿbⁿ.

Тобто:

(ycⁿ , де |y|_a = |y|_b + |y|_B = n, y = (a|B)*b*b)∩T* = aⁿbⁿcⁿ .

Отже, ця граматика породжує усі слова мови і тільки їх.

 

 

Завдання 2.5. Нехай задано мову L = {aⁿb^m|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, t₁, t₂, x Î{a*,b**,c*} такі, що ut₁ⁱx t₂ⁱvÎL для всіх i=0,1,…. Зрозуміло, що t₁ (так само як і t₂) не може складатися з різних символів (інакше для деякого i ланцюжок ut₁ⁱx t₂ⁱv не буде належати L. Але якщо t₁ складається лише з одного символу, то збільшуючи i можна порушити баланс символів a,b,c. Тому мова L не може бути КВ-мовою.

 

 

Завдання для самостійної та контрольної роботи

 

Побудувати граматику G, яка породжує задану мову L, та довести L(G) = L для L:

1) aⁿb^m, n>=m

2) a^*|b^*| c^*

3) (a|b|c)^*

4) (a|b)^*c

5) a^*ba^*b

6) a^*b|b^*a

7) aⁿbⁿcⁿ

8) aⁿbc^m, m>n

9) aⁿb²ⁿ

10) a^*|ba^*b

11) aⁿbⁿ⁺²

12) a^*b^*c^*

13) aⁿb^mcⁿ

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; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!