Задачи по ЕАИ

Задачите на контролните и писмения изпит по ЕАИ са лесни.
Реално никаква мисловна дейност не се изисква, за всяко нещо има алгоритми и задачите просто проверяват дали тези алгоритми са научени. След като това беше казано, тук ще бъдат разгледани всички видове задачи, които могат да бъдат дадени на изпит и ще представя метода, по който се решават. Доказателства, че тези методи са коректни не се изискват на изпит, затова те ще бъдат поместени в лекциите.

Генериране на Краен, Детерминиран, Минимален Автомат

Задължително поне на две от оформящите крайната оценка контролни ще има задача за генериране на такъв автомат. Това най-обикновено се състои от няколко етапа, всеки от които може да бъде прескочен(защото понякога отнема буквално цял час) и ако е достатъчно очевидно, може даже и да ви се размине :). Етапите трябва да се изпълняват подред, иначе отговорът няма да е верен.

Задача: Даден е езикът L, които се състои от всички думи над азбуката {0, 1, 2}, които имат сума на буквите кратна на 3 и съдържащи "120" като поддума. Да се състави Краен Детерминиран Минимален Автомат, който разпознава езика L.

1. Генериране на Автомат, който разпознава езика

Покажи

Първи начин: УСБССС (Умен Съм Бил, Сетил Съм Се)
При този начин просто "познаваме" какъв трябва да е автоматът. Предимства - става много по-бързо.
Недостатъци - може да е грешен. Ако не е доказано, че този автомат разпознава езика L и само езика L - тази точка не се брои за вярна. А доказателството може да отнеме дълго време.

Втори начин: Правилен
Езиците от тези задачи най-често не са особено сложни и могат да се представят като логически израз на по-лесни езици. Това означава да се използват операциите Обединение, Сечение, Конкатенация и Звезда на Клини за по-малки и удобни за работа езици. Това е по-лесно, отколкото звучи.
Например, езикът от условието не е нищо повече от сечението на езиците A1 = "Има поддума '120'" и A2 = "Има сума на цифрите кратна на 3".
Тези "основни" автомати обаче също трябва да се докаже, че разпознават съответния си език.

Ето съответните им таблици:

A1
Състояние \ Преход	0	1	2
S (начално)	S	A	S
A (завършва на 1)	S	A	B
B (завършва на 12)	C	A	S
C (съдържа 120 - крайно)	C	C	C

A2
Състояние \ Преход	0	1	2
0 (начално и крайно)	0	1	2
1	1	2	0
2	2	0	1

(Състоянията в A2 характеризират какъв е остатъкът по модул 3 в момента)

Алгоритъм за генериране на обединение/сечение на езици:
Таблица. В редовете се слагат състоянията на единия автомат, а в колоните - състоянията на другия. Така се генерират всички възможни комбинации от състояния.

A2 \ A1	S	A	B	C
0	S0	A0	B0	C0
1	S1	A1	B1	C1
2	S2	A2	B2	C2

- Новият автомат има 12 състояния. Началното му е това състояние, чиито индекси са начални и за двата автомата. Ако търсим обединение неговите крайни състояние са всички с индекси крайни на A1 или на A2.При сечение са всички състояния, които са крайни за A1 и за A2.
Ребрата на новия автомат са комбинация от ребрата на двата стари. Няма да ги пиша всичките (много са), но ето пример: Ако в A1 от A с преход "2" се отива в състояние B, а в A2 от състояние 0 с "2" се отива в състояние 2, то в новия автомат съществува преход:
$A0 \overset{2}\rightarrow B2$

Алгоритъм за конкатенация:
A = A1.A2
Силно елементарен - от всички крайни състояния на А1 се слага $\epsilon$-преход към началното на A2.

Алгоритъм за звезда на клини:
A = A1*
От крайните състояния на A1 се слага $\epsilon$-преход към началното такова.
Началното състояние също става "крайно", защото може да има 0 повторения.

Внимание:
Дадените алгоритми не винаги генерират детерминирани или минимални автомати.
Винаги трябва да се гледа дали следващите стъпки не трябва да бъдат изпълнени.

2. Детерминиране на Автомат

Покажи

Един автомат е детерминиран, когато в него няма епсилон преходи и от всяко състояние има преход с всяка буква от азбуката, над която е езикът, който автоматът разпознава.
Алгоритъм за детерминиране на Автомат:
Внимание: Този алгоритъм е гаден и дълъг. Добра идея - генерирайте си автоматите в предишната точка детерминирани, за да го избегнете изцяло. Проверката дали автомат е детерминиран е тривиална.

Правим си таблица. За всяко състояние има по един ред, за всеки преход - по една колона.
Тъй като автоматът от примера е детерминиран, ще работим със следния прост автомат:
А е автомат, който разпознава език над {0,1}, чиито думи съдържат 101 или 11.

Да кажем, че с някакъв преход може да стигне до две (или повече) състояния едновременно - все пак автоматът не е детерминиран. Разделяме ги със запетая в таблицата. Също така, ако от A до B може да се достигне с "1"-преход, но от B до C може да стигне с $\epsilon$-преход, то значи и от A до C се стига с "1"-преход.

Да кажем, че това е таблицата на автомата:

Състояние \ Преход	0	1
А(начално)	A	B, C
B	D	А
C	A	Е
D	A	E
Е(крайно)	E	E

Автоматът не е красив. Обикновено недетерминираните не са.
Детерминирането става на няколко стъпки. Първо, ако има несъществуващи преходи (тук няма), трябва да се създаде едно състояние "грешка", което при всякакъв преход се връща в себе си и не е крайно - там отиват думите, които не се разпознават от езика. Всички несъществуващи преходи се създават и сочат към това състояние.

Err(грешка)	Err	Err

След тази сравнително скучна част… си правим още една таблица. Тя напомня на "обхождане в ширина" на автомата. Знам, гадно е - почти свършихме.

Таблицата се попълва "в реално време". Когато всичко е готово, в нея ще има нов автомат, който е детерминиран. Отново в редовете има състояния, а в колоните - преходи. Започва се от началното състояние:

Състояние \ Преход	0	1
А(начално)	A	(B, C)

След това за всяко все още необходено състояние се добавя по един ред в таблицата.
Ако има няколко състояния при преход, създава се ново състояние - комбинация от двете. Неговите преходи са съвкупност от преходите на всичките "примитивни" състояния. В случая - B и C. Ако някое от тези състояния е крайно - цялото ново състояние става крайно. Следващият ред е:

(B,C)	(D,A)	(A,E)

И в крайна сметка така се стига до цялата таблица:

Състояние \ Преход	0	1
А(начално)	A	(B, C)
(B,C)	(D,A)	(A,E)
(D,A)	A	(B,C,E)
(A,E)(крайно)	(A,E)	(B,C,E)
(B,C,E)(крайно)	(D,A,E)	(B,C,E)
(D,A,E)(крайно)	(A,E)	(B,C,E)

Това е детерминиран, но не гарантирано минимален автомат - следващата стъпка винаги трябва да се прилага. Впрочем, този алгоритъм се използва основно от компютри. На изпит най-често може и по-лесно.

3. Минимизация на Автомат

Покажи

Това вече е по-лесно. Естествено, става с таблица. Как пък веднъж не стана с игра на тетрис, а винаги с таблици… Идеята е да се разделят състоянията на дотук-получения автомат на "класове на еквивалентност". Алгоритъмът е следният: Разделяме състоянията на автомата A на две групи - крайни и некрайни. За всяко състояние от първата група гледаме в коя група отива при всеки от преходите. Групираме ги наново по този признак.
Например, за автомата(който е същият като в предишната точка, но с номерирани състояния):

Състояние \ Преход	0	1
0(начално)	0	1
1	2	3
2	0	4
3(крайно)	3	4
4(крайно)	5	3
5(крайно)	3	4

Групите първоначално са:

• A={0,1,2}
• B={3,4,5}

Разглеждаме 0 и 1. при "0"-преход и двете отиват в елемент на група A, но при "1"-преход отиват в различни групи. Следователно двете състояния не са еквивалентни и не трябва да са в един клас на еквивалентност. Това се прави за всеки две състояния във всяка отделна група(с поне 2 елемента). Получава се:
{0}, {1,2}, {3,4,5}
Същото нещо се повтаря отново:
{0}, {1}, {2}, {3,4,5}
И така докато в някой момент се получат еднакви групи на две поредни стъпки. Това означава, че всички елементи са в своите класове на еквивалентност. Без да се впускам в доказателства, това означава, че всичко в един клас е еквивалентно. Тоест, ако заменим всичките тези състояния с едно общо - няма да има разлика във функционирането на автомата. Това и правим.
{3,4,5} = 6

Състояние \ Преход	0	1
0(начално)	0	1
1	2	6
2	0	6
6(крайно)	6	6

Автоматът вече е минимизиран и с това задачата е напълно решена.
Това беше дългоо.

Доказване нерегулярност на даден език

Note: Pumping лемата не е достатъчно условие за регулярност!

Този тип задачи се решават с прилагане на pumping лемата за регулярни езици. Нейното твърдение е:
Ако един език L е регулярен,то съществува такова число n , че всяка дума от L с дължина поне n може да се раздели на три части xyz такива, че:

• |xy| <= n
• |y| >= 1
• $xy^i \in L$ за всяко цяло неотрицателно i.

За да бъде един език нерегулярен, то трябва да се докаже противоречие в горната дефиниция. Най-често това става като се вземе произволно n и се покаже, че твърдението не е изпълнено за някоя дума.
Пример:
Даден е езикът L. $L= \{ uww^r | u,w \in \{0,1\}^*\}, |u| < |w| \}$. Да се докаже, че L не е регулярен.

Решение

Приемаме n за фиксирано. Тогава, дума съставена от n на брой нули и 2(n+1) единици принадлежи на езика.
$v = \underbrace{000...000}_{n}\underbrace{11..11}_{2(n+1)}$
Разделяме я на три части - v=xyz.
Според условията на pumping лемата |y| <n, следователно y се състои изцяло от нули.
В такъв случай за i=2 $|y^i|$ ще стане по-голямо от $|w|$. Тоест, ще се получи дума от следния вид:
$v_1 = \underbrace{000...000}_{n} \underbrace{000...000}_{n}\underbrace{11..11}_{2(n+1)}$
В този момент, за да бъде изпълнено условието $|u| < |w|$, налага се последните n нули да принадлежат на w. Но, по дефиниция всяка дума от L завършва с палиндром $ww^r$, а в този случай това вече е невъзможно. Получено е търсеното противоречие и оттук следва, че езикът L не е регулярен.

Доказване, че език не е контекстно свободен

Тук има два вида задачи:

Pumping Lemma

Лемата за покачването си има вариант и за CFL.

Ако един език L е контекстно свободен,то съществува такова число n , че всяка дума w от L, с дължина поне n, може да се раздели на пет части uvxyz такива, че:

• |vxy| <= n
• |vy| >= 0 (забележка: vy не е задължително поддума на uvwxyz. Това е все едно: "|v| > 0 или |y| > 0")
• $uv^ixy^iz \in L$ за всяко цяло неотрицателно i.

Естествено, ползва се най-вече за i=0 и i=2.
Пример:
Даден е езикът $L = { a^nb^nc^n }$ при стандартните уговорки за означенията. Да се докаже, че не е контекстно свободен.

Решение

Решение ама друг път.
Все пак, набързо - разгледай различня брой видове букви, които може да съдържа vy.
Т.е. ако съдържа само a,b или c е "очевидно" противоречието за i=0 (две от буквите се срещат по-често от третата).
Ако vy съдържа две от трите букви, то също е очевидно за i=0 (тогава третата буква се среща по-често)
Ако съдържа и трите букви, то или v, или y съдържа поне две различни букви(това не беше "изключващо или"). И, съответно, има противоречие за i=2(Protip: Разпиши си думата, и виж).

Сечение с регулярен език

Ако пресечем контекстно-свободен език с регулярен език, получава се отново контекстно свободен език
Пример:
Езикът L = {(a,b,c)*}, където всяка от трите букви се среща по равен брой пъти.

Решение

G = {a*b*c*}. Очевидно е регулярен(ако не е очевидно, обади ми се, ще ти покажа къде е записването за УНСС).
Сечем L с G и се получава точно $L_1 = { a^nb^nc^n }$ - езикът от предишната подточка. Той не е контекстно свободен. Следователно L не е контекстно свободен. КТДД.
Ако ти се струва, че този метод включва много УСБССС - точно така си е.

Намиране на граматика за даден език

В този тип задачи е дадено описание на някакъв език и трябва да се създаде граматика, която го генерира.
Това става на две части - първо се съставя някаква граматика, за която се предполага, че генерира езика. Тук не мога да помогна. Основният принцип, на който стават нещата е "Умен Съм Бил…". За щастие, на контролни и изпити се дават само очебийни граматики - акцентът не е на тази част.
След това трябва да се докаже, че точно това е търсената граматика.

• За всяка дума от езика трябва да се докаже, че граматиката я разпознава.
• За всяка дума, генерирана от граматиката трябва да се докаже, че принадлежи на езика.

И двете стават чрез индукция.

Пример

Даден е езикът $L = \{ ww^r | w \in \{a, b\}^*\}$. Това е езикът на всички палиндроми с четна дължина, съставени от буквите a и b.

Ще доказваме, че това е неговата граматика G:
Терминали: $\epsilon, a, b$
Нетерминали: S
Аксиома: S
Преходи: $S \rightarrow aSa | bSb | \epsilon$

Индукция по дължината на думата
С това доказваме първото от горните твърдения.
Първо, за най-късата възможна дума от езика трябва да се докаже, че се генерира от езика.
След това, ако всички думи с дължина 2n, принадлежащи на езика, се генерират от тази граматика, то трябва да следва, че всички думи с дължина 2(n+1) се генерират също(2n и 2(n+1) са избрани за удобство, иначе по принцип са n и n+1).
И това наистина е така.

1. Най-късата дума от езика е празната дума, която се генерира от $S \rightarrow \epsilon$ за n=0.
2. Индукционното твърдение може да се формулира като "S разпознава всяка дума от езика с дължина 2n или по-малко".

Ако думата е с дължина 2(n+1), то със сигурност можем да твърдим, че тя е от вида aXa или bXb, където X е палиндром с дължина 2n. В първия случай се извършва изводът $S \rightarrow aSa$, а във втория: $S \rightarrow bSb$, като при това и в двата случая след този извод стигаме точно до дума с дължина 2n - такава, която със сигурност се разпознава от нетерминала, в който се отива - S. С това тази посока е доказана.

Индукция по броя изводи.
Това е малко или повече обратната посока на предишното доказателство.
Доказваме(директно), че всички думи, генерирани от G с най-малкия възможен брой изводи принадлежат на езика.
След това, от твърдението, че за всяка дума, генерирана с най-много n извода принадлежи на езика L трябва да следва, че и всяка дума, генерирана с n+1 извода също принадлежи на него.

1. $S \rightarrow \epsilon$ принадлежи на езика.
2. Ако всички думи с генерирани с n извода принадлежат на езика, то всяка дума, генерирана с n+1 извода може да се раздели на 2 части:
   • • $S \rightarrow aSa | bSb$ - първият извод задължително е един от тези двата.
     • $S \rightarrow ...$ - след това се правят n на брой други изводи.

Но, това накратко казва, че всяка дума, получена с n+1 извода е всъщност aYa или bYb, където Y е дума, получена с n извода. Директно се проверява, че и в двата случая тази дума е палиндром с четна дължина, следователно отговаря на условията на езика.
С което и тази посока на доказателството е завършена.

И, съответно, задачата е решена.
Забележка:
Добре е да се каже, че много често всъщност езикът, за който трябва да се генерира граматика дори не е контекстно-свободен, а най-обикновен автоматен език. В такъв случай доказателството може още да бъде опростено - трябва просто да се състави автомат, който да разпознава езика. Естествено, той също ще трябва да се докаже, но тук няма ограничения. Може да е неминимален, недетерминиран - няма проблем. Такъв автомат се генерира чрез Конкатенация/Обединене/Звезда на Клини на елементарни (с по едно състояние) автомати. В почти всички случаи е по-лесно да се направи автомат.