Задачите на контролните и писмения изпит по ЕАИ са лесни.
Реално никаква мисловна дейност не се изисква, за всяко нещо има алгоритми и задачите просто проверяват дали тези алгоритми са научени. След като това беше казано, тук ще бъдат разгледани всички видове задачи, които могат да бъдат дадени на изпит и ще представя метода, по който се решават. Доказателства, че тези методи са коректни не се изискват на изпит, затова те ще бъдат поместени в лекциите.
Генериране на Краен, Детерминиран, Минимален Автомат
Задължително поне на две от оформящите крайната оценка контролни ще има задача за генериране на такъв автомат. Това най-обикновено се състои от няколко етапа, всеки от които може да бъде прескочен(защото понякога отнема буквално цял час) и ако е достатъчно очевидно, може даже и да ви се размине :). Етапите трябва да се изпълняват подред, иначе отговорът няма да е верен.
Задача: Даден е езикът 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 |
Автоматът не е красив. Обикновено недетерминираните не са.
Детерминирането става на няколко стъпки. Първо, ако има несъществуващи преходи (тук няма), трябва да се създаде едно състояние "грешка", което при всякакъв преход се връща в себе си и не е крайно - там отиват думите, които не се разпознават от езика. Всички несъществуващи преходи се създават и сочат към това състояние.
След тази сравнително скучна част… си правим още една таблица. Тя напомня на "обхождане в ширина" на автомата. Знам, гадно е - почти свършихме.
Таблицата се попълва "в реално време". Когато всичко е готово, в нея ще има нов автомат, който е детерминиран. Отново в редовете има състояния, а в колоните - преходи. Започва се от началното състояние:
Състояние \ Преход |
0 |
1 |
А(начално) |
A |
(B, C) |
След това за всяко все още необходено състояние се добавя по един ред в таблицата.
Ако има няколко състояния при преход, създава се ново състояние - комбинация от двете. Неговите преходи са съвкупност от преходите на всичките "примитивни" състояния. В случая - B и C. Ако някое от тези състояния е крайно - цялото ново състояние става крайно. Следващият ред е:
И в крайна сметка така се стига до цялата таблица:
Състояние \ Преход |
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 |
Групите първоначално са:
Разглеждаме 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).
И това наистина е така.
- Най-късата дума от езика е празната дума, която се генерира от $S \rightarrow \epsilon$ за n=0.
- Индукционното твърдение може да се формулира като "S разпознава всяка дума от езика с дължина 2n или по-малко".
Ако думата е с дължина 2(n+1), то със сигурност можем да твърдим, че тя е от вида aXa или bXb, където X е палиндром с дължина 2n. В първия случай се извършва изводът $S \rightarrow aSa$, а във втория: $S \rightarrow bSb$, като при това и в двата случая след този извод стигаме точно до дума с дължина 2n - такава, която със сигурност се разпознава от нетерминала, в който се отива - S. С това тази посока е доказана.
Индукция по броя изводи.
Това е малко или повече обратната посока на предишното доказателство.
Доказваме(директно), че всички думи, генерирани от G с най-малкия възможен брой изводи принадлежат на езика.
След това, от твърдението, че за всяка дума, генерирана с най-много n извода принадлежи на езика L трябва да следва, че и всяка дума, генерирана с n+1 извода също принадлежи на него.
- $S \rightarrow \epsilon$ принадлежи на езика.
- Ако всички думи с генерирани с n извода принадлежат на езика, то всяка дума, генерирана с n+1 извода може да се раздели на 2 части:
-
- $S \rightarrow aSa | bSb$ - първият извод задължително е един от тези двата.
- $S \rightarrow ...$ - след това се правят n на брой други изводи.
Но, това накратко казва, че всяка дума, получена с n+1 извода е всъщност aYa или bYb, където Y е дума, получена с n извода. Директно се проверява, че и в двата случая тази дума е палиндром с четна дължина, следователно отговаря на условията на езика.
С което и тази посока на доказателството е завършена.
И, съответно, задачата е решена.
Забележка:
Добре е да се каже, че много често всъщност езикът, за който трябва да се генерира граматика дори не е контекстно-свободен, а най-обикновен автоматен език. В такъв случай доказателството може още да бъде опростено - трябва просто да се състави автомат, който да разпознава езика. Естествено, той също ще трябва да се докаже, но тук няма ограничения. Може да е неминимален, недетерминиран - няма проблем. Такъв автомат се генерира чрез Конкатенация/Обединене/Звезда на Клини на елементарни (с по едно състояние) автомати. В почти всички случаи е по-лесно да се направи автомат.