Регуларни изрази су формализам којим програмер може да опише неке језике
Потребан нам је другачији, оперативнији формализам, који ће рачунару помоћи да препозна да ли дата реч припада датом језику
Решење долази у облику коначних аутомата
Биће доказано да иако наизглед потпуно другачији од регуларних израза, коначни аутомати описују тачно класу регуларних језика
Како се проверава да ли реч припада аутомату?
креће се од почетног стања (обележено је стрелицом која улази у круг)
читајући слова прелазимо из стања у стање
када смо прочитали целу реч, проверавамо да ли се налазимо у завршном стању (двоструко заокруженом) или у незавршном (једноструко заокруженом) – реч се прихвата ако и само ако смо је прочитали целу и стигли у неко завршно стање
На пример, реч \(abbaba\) припада језику аутомата.
Ово ћемо представљати краће на следећи начин \(_0a_1b_1b_1a_0b_0a_1\)
Језик приказаног аутомата чине све речи које се састоје од слова \(a\) и \(b\) и имају непаран број појављивања слова \(a\)
Задатак: нацртати аутомат који препознаје језик свих речи које се састоје од слова \(a\) и \(b\) и завршавају се са \(b\)
Коначни аутомат (КА) је уређена петорка \(\mathcal{A} = (\Sigma, Q, I, F, \Delta)\) где је:
Неке напомене:
Пример.
Пример.
Претходни аутомат прихвата језик који се састоји од свих речи које садрже подреч \(ab\) – то је регуларни језик \((a|b)^*ab(a|b)^*\).
И наредни аутомат прихвата исти језик
Пример.
Претходни аутомат прихвата језик \(a^*\)
Аутомат се понекад представља и таблицом. На пример
| \(a\) | \(b\) | |
|---|---|---|
| \(0\) | \(\{0, 1\}\) | \(\{0\}\) |
| \(1\) | \(\emptyset\) | \(\{2\}\) |
| \(2\) | \(\{2\}\) | \(\{2\}\) |
Ова таблица описује функцију \(\delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow \mathcal{P}(Q)\)
међу приказана два аутомата постоје веома озбиљне разлике
у другом аутомату у стању \(0\) читањем слова \(a\) аутомат може да преће било у стање \(0\), било у стање \(1\)
у другом аутомату у стању \(1\) читањем слова \(b\) аутомат не може да промени стање
у првом аутомату таквих проблема нема
аутомат је детерминистички (ДКА) ако у сваком стању, за свако слово постоји највише једно стање у које можемо да прећемо. Формално:
аутомат је потпун ако у сваком стању, за свако слово постоји најмање једно стање у које можемо да прећемо. Формално:
У потпуном детерминистичком аутомату (ПДКА) за свако стање и слово постоји тачно једно стање у које се прелази.
У ПДКА уместо релације преласка \(\Delta\) можемо посматрати функцију преласка \(\delta: Q \times \Sigma \rightarrow Q\)
Уместо скупа почетних стања \(I \subseteq Q\), задаје се јединствено почетно стање \(i \in Q\)
ПДКА је онда облика \(\mathcal{A} = (\Sigma, Q, i, F, \delta)\)
Потпуни-детерминистички коначни аутомати се могу ефикасно искористити за проверу да ли реч припада језику
Недетерминистички аутомати и аутомати са \(\varepsilon\)-прелазима се користе као међуфаза између регуларних израза и ДПКА
Желимо да формализујемо дефиницију: “Реч припада језику аутомата ако се читајући једно по једно њено слово може од неког почетног стања стићи до неког завршног стања аутомата”
Приметимо да у недетерминистичким аутоматима може постојати више почетних стања и више могућих путања за исту реч на улазу – да би реч припадала језику довољно је да постоји само једна путања која се завршава у неком завршном стању
Релацију \(\Delta: Q \times (\Sigma \cup \{\varepsilon\}) \times Q\) уопштавамо на релацију \(Q \times \Sigma^* \times Q\) — од преласка по једном слову долазимо до преласка по целој речи
Важи \(p\stackrel{w}{\rightarrow}q\), за неку реч \(w = a_0a_1\ldots a_{k-1}\) ако и само ако постоје стања \(p_0 = p\), \(p_1\), \(p_2\), \(p_k=q\) таква да \(p = p_0 \stackrel{a_0}{\rightarrow} p_1 \stackrel{a_1}{\rightarrow} p_2 \ldots p_{k-1} \stackrel{a_{k-1}}{\rightarrow} p_k = q\).
Прелаз \(p \stackrel{w}{\rightarrow} q\) назива се израчунавање у аутомату. Реч \(w\) је етикета тог израчунавања.
Израчунавање је успешно ако почиње у неком почетном и завршава се у неком завршном стању.
Језик аутомата \(\mathcal{A} = (\Sigma, Q, I, F, \Delta)\) је скуп речи
\[L(\mathcal{A}) = \{w \in \Sigma^*\ |\ (\exists p \in I)(\exists q \in F)(p \stackrel{w}{\rightarrow} q)\}\]
Обратити пажњу на вишеструку егзистенцијалну квантификацију – довољно је да постоји само једна успешна путања од почетног до завршног стања по тој речи
Дефиниција језика се може дати у терминима функције преласка \(\delta: Q \times \Sigma \rightarrow Q\)
Дефинишемо функцију \(\delta^*: Q \times \Sigma^* \rightarrow Q\) — од преласка по једном слову долазимо до преласка по целој речи
Језик ПДКА је
\[L(\mathcal{A}) = \{w \in \Sigma^*\ |\ \delta^*(i, w) \in F\}\]
Могуће су и другачије дефиниције.
Конфигурација аутомата је елемент скупа \(Q \times \Sigma^*\)
Прелаз из конфигурације у конфигурацију \((p, aw) \vdash (q, w)\) акко \((p, a, q) \in \Delta\)
Језик аутомата
\[L(\mathcal{A}) = \{w \in \Sigma^*\ |\ (\exists i \in I, f \in F)((i, w) \vdash (f, \varepsilon)) \}\]
Језик \(L\) је препознатљив акко и само ако постоји коначан аутомат који га препознаје тј. постоји коначан аутомат \(\mathcal{A}\) такав да је \(L(\mathcal{A}) = L\). Класу свих препознатљивих језика над азбуком \(\Sigma\) означаваћемо са \(\mathit{Prep}(\Sigma^*)\).
У наставку курса конструктивно ћемо доказати Клинијеву теорему која тврди да се класе препознатљивих и регуларних језика поклапају тј. да је \(Prep(\Sigma^*) = Reg(\Sigma^*)\).
Алгоритам којим се од регуларног израза добија НКА са \(\varepsilon\) покретима.
Нормализовани аутомати
Рекурзивно дефинисан у односу на структуру регуларних израза.
Пример. Аутомат за регуларни израз \((a|b)^*abb\).
Основни алгоритам: пронаћи све путање облика \(\varepsilon\ldots\varepsilon a \varepsilon\ldots\varepsilon\) које воде из неког стања \(p\) у неко стање \(q\) и заменити их граном из \(p\) у \(q\) обележеном словом \(a\).
Код нормализованих аутомата, довољно је посматрати само путање облика \(\varepsilon\ldots\varepsilon a\).
Дефинишемо \(\varepsilon\)-затворење стања \(q\) као \(\bar{\varepsilon}(q) = \{q' \in Q\ |\ q\stackrel{\varepsilon}{\rightarrow} q'\}\).
Конструишемо нови аутомат, тако што крећемо од стања \(0\) и за свако стање \(p\) додато у тај нови аутомат додајемо прелазе \((p, a, q)\) такве да постоји \(q' \in \bar{\varepsilon}(p)\) такво да \((q', a, q) \in \Delta\).
Другим речима, разматрамо сва стања \(q'\) до којих из \(p\) можемо стићи само преко \(\varepsilon\)-грана, тражимо преласке из њих до неких стања \(q\) по гранама на којима пише неко \(a\) које није \(\varepsilon\) и додајемо гране од стања \(p\) до тих стања \(q\) обележене тим словима \(a\).
Пример. Томпсонов аутомат за \((a|b)^*abb\) ослобођен од \(\varepsilon\)-покрета.
У једном потезу гради НКА без \(\varepsilon\)-покрета
Обележавамо свако појављивање слова у регуларном изразу. На пример, за израз \((a|b)^*abb\) обележавамо \((a_1|b_2)^*a_3b_4b_5\).
Сваком појављивању неког слова одговара једно стање аутомата и уводимо једно додатно стање аутомата као почетно.
Гледамо којим појављивањем слова могу да почну речи у датом регуларном језику и почетно стање спајамо са тим стањима (на грани која улази у стање које одговара неком појављивању слова увек се налази то слово). На пример, у изразу \((a_1|b_2)^*a_3b_4b_5\) речи могу да почну или словом \(a_1\) или \(b_2\) или \(a_3\), а не могу да почну са \(b_4\) нити \(b_5\) (пре њих се мора јавити \(a_3\)), па почетно стање спајамо са стањима \(1\), \(2\) и \(3\).
Гледамо којим појављивањем слова могу да се заврше речи у датом регуларном језику и та стања проглашавамо за завршна стања. На пример, у изразу \((a_1|b_2)^*a_3b_4b_5\) све речи се завршавају словом \(b_5\). Зато је једино завршно стање, стање \(5\).
Разматрамо који се парови појављивања слова из регуларног израза могу јавити у речима из одговарајућег регуларног језика. Ако се може јавити пар \(s_it_j\), додајемо грану од стања \(i\) до стања \(j\) обележену словом \(t\). У нашем примеру парови су \(a_1a_1\), \(a_1b_2\), \(b_2a_1\), \(b_2b_2\), \(a_1a_3\), \(b_2a_3\), \(a_3b_4\) и \(b_4b_5\). Тако за регуларни израз \((a_1|b_2)^*a_3b_4b_5\) добијамо аутомат на слици.
Формализујемо претходни поступак.
Нека је \(\Sigma\) азбука која садржи слова регуларног израза у ком су означена појављивања сваког слова. У примеру је \(\Sigma = \{a_1, a_3, b_2, b_4, b_5\}\). Нека је \(r\) регуларни израз/језик добијен означавањем слова полазног регуларног израза. На пример, регуларни израз \(r\) је \((a_1|b_2)^*a_3b_4b_5\), а \(L(r)\) његов језик.
Нека је \(P(r) = \{a \in \Sigma\ |\ a\Sigma^* \cap L(r) \neq \emptyset\}\) – скуп слова којима почињу речи из \(L(r)\).
Нека је \(K(r) = \{a \in \Sigma\ |\ \Sigma^*a \cap L(r) \neq \emptyset\}\) – скуп слова којима се завршавају речи из \(L(r)\).
Нека је \(S(r) = \{ab \in \Sigma^2\ |\ \Sigma^*ab\Sigma^* \cap L(r) \neq \emptyset\}\) – скуп парова слова које садрже речи из \(L(r)\).
Како израчунати ове скупове? Рекурзивно у односу на структуру регуларног израза \(r\).
Користићемо и помоћни скуп \(E(r) = L(r) \cap \{\varepsilon\}\). Дакле,
\[E(r) = \left\{ \begin{array}{ll} \{\varepsilon\}, & \varepsilon \in L(r)\\ \emptyset, & \varepsilon \notin L(r) \end{array}\right.\]
Рекурзивни поступак израчунавања скупа \(E\).
Рекурзивни поступак израчунавања скупа \(P\)
Рекурзивни поступак израчунавања скупа \(K\)
Рекурзивни поступак израчунавања скупа \(S\)
Размотримо дати пример
\[\begin{eqnarray*} P((a_1|b_2)^*a_3b_4b_5) &=& P((a_1|b_2)^*) \cup E((a_1|b_2)^*) P(a_3b_4b_5)\\ &=& P(a_1|b_2) \cup \{\varepsilon\} P(a_3b_4b_5)\\ &=& P(a_1) \cup P(b_2) \cup P(a_3) \cup E(a_3)P(b_4b_5)\\ &=& \{a_1\} \cup \{b_2\} \cup \{a_3\} \cup \emptyset P(b_4b_5)\\ &=& \{a_1, b_2, a_3\} \end{eqnarray*}\]
\[\begin{eqnarray*} K((a_1|b_2)^*a_3b_4b_5) &=& K((a_1|b_2)^*)E(a_3b_4b_5) \cup K(a_3b_4b_5)\\ &=& K((a_1|b_2)^*)E(a_3)E(b_4b_5) \cup K(a_3b_4)E(b_5) \cup K(b_5)\\ &=& K((a_1|b_2)^*)\emptyset E(b_4b_5) \cup K(a_3b_4)\emptyset \cup \{b_5\}\\ &=& \{b_5\} \end{eqnarray*}\]
\[\begin{eqnarray*} S((a_1|b_2)^*a_3b_4b_5) &=& S((a_1|b_2)^*) \cup K((a_1|b_2)^*)P(a_3b_4b_5) \cup S(a_3b_4b_5)\\ &=& S(a_1|b_2) \cup K(a_1|b_2)P(a_1|b_2) \cup K(a_1|b_2)\{a_3\} \cup \{a_3b_4, b_4b_5\}\\ &=& \emptyset \cup \{a_1, b_2\}\{a_1, b_2\} \cup \{a_1, b_2\}\{a_3\} \cup \{a_3b_4, b_4b_5\}\\ &=& \{a_1a_1, a_1b_2, b_2a_1, b_2b_2\} \cup \{a_1a_3, b_2a_3\} \cup \{a_3b_4, b_4b_5\} \\ &=& \{a_1a_1, a_1b_2, b_2a_1, b_2b_2, a_1a_3, b_2a_3, a_3b_4, b_4b_5\} \end{eqnarray*}\]
Овим су одређени прелази из почетног стања, завршно стање и сви остали прелази у Глушковљевом аутомату.
| \(a\) | \(b\) | |
|---|---|---|
| \(0\) | \(\{1, 3\}\) | \(\{2\}\) |
| \(1\) | \(\{1, 3\}\) | \(\{2\}\) |
| \(2\) | \(\{1, 3\}\) | \(\{2\}\) |
| \(3\) | \(\emptyset\) | \(\{4\}\) |
| \(4\) | \(\emptyset\) | \(\{5\}\) |
| \(\bf{5}\) | \(\emptyset\) | \(\emptyset\) |
За сваки недетерминистички аутомат постоји детерминистички аутомат који препознаје исти језик
Цена се плаћа потенцијално експоненцијалним повећањем броја стања (на срећу, у пракси се тај најгори случај ретко дешава)
Основна идеја: стања детерминистичког аутомата су подскупови скупа стања недетерминистичког аутомата (конструкција подскупова, енгл. subset construction)
Нека је дат недетерминистички аутомат \(\mathcal{A} = (\Sigma, Q, I, F, \Delta)\), без \(\varepsilon\)-покрета. Дефинишемо детерминистички аутомат \(\mathcal{A}' = (\Sigma, P(Q), I, F', \delta)\), где је
У пракси не морамо посматрати све подскупове (њих има \(2^{|Q|}\)), већ само оне достижне из почетног стања \(I\)
Детерминизујмо аутомат који смо добили Томспоновом тј. Глушковљевом конструкцијом.
| \(a\) | \(b\) | |
|---|---|---|
| \(0\) | \(\{1, 3\}\) | \(\{2\}\) |
| \(1\) | \(\{1, 3\}\) | \(\{2\}\) |
| \(2\) | \(\{1, 3\}\) | \(\{2\}\) |
| \(3\) | \(\emptyset\) | \(\{4\}\) |
| \(4\) | \(\emptyset\) | \(\{5\}\) |
| \(\bf{5}\) | \(\emptyset\) | \(\emptyset\) |
Након детерминизације
| \(a\) | \(b\) | |
|---|---|---|
| \(\{0\}\) | \(\{1, 3\}\) | \(\{2\}\) |
| \(\{1,3\}\) | \(\{1, 3\}\) | \(\{2, 4\}\) |
| \(\{2\}\) | \(\{1, 3\}\) | \(\{2\}\) |
| \(\{2,4\}\) | \(\{1, 3\}\) | \(\{2,5\}\) |
| \(\bf{\{2,5\}}\) | \(\{1, 3\}\) | \(\{2\}\) |
Лема.
\[\delta^*(A, w) = \bigcup_{q \in A}\{q' \in Q\ |\ q \stackrel{w}{\rightarrow} q'\}\]
Доказ: индукцијом по речи \(w\)
Ако је \(w = \varepsilon\), тада је \(\delta^*(A, w) = A\), а такође је \(\bigcup_{q \in A}\{q' \in Q\ |\ q \stackrel{\varepsilon}{\rightarrow} q'\} = \bigcup_{q \in A}\{q\} = A\).
Нека по индуктивној хипотези тврђење важи за реч \(w\). Размотримо реч \(wa\). Важи да је
\[\begin{eqnarray*} \delta^*(A, wa) &=& \delta(\delta^*(A, w), a) \\ &=& \bigcup_{q \in \delta^*(A, w)}\{q' \in Q\ |\ (q, a, q') \in \Delta \}\\ &=& \bigcup_{q' \in \delta^*(A, w)}\{q'' \in Q\ |\ (q', a, q'') \in \Delta \}\\ &=& \{q'' \in Q\ |\ (\exists q' \in \delta^*(A, w))((q', a, q'') \in \Delta)\}\\ &=& \{q'' \in Q\ |\ (\exists q' \in \left(\bigcup_{q \in A}\{q' \in Q\ |\ q \stackrel{w}{\rightarrow} q'\}\right))((q', a, q'') \in \Delta)\}\\ &=& \{q'' \in Q\ |\ (\exists q \in A)(\exists q' \in Q)\left(q \stackrel{w}{\rightarrow} q' \wedge (q', a, q'') \in \Delta)\right)\}\\ &=& \{q'' \in Q\ |\ (\exists q \in A)(q \stackrel{wa}{\rightarrow} q'')\}\\ &=& \bigcup_{q \in A} \{q'' \in Q\ |\ q \stackrel{wa}{\rightarrow} q''\}\\ &=& \bigcup_{q \in A} \{q' \in Q\ |\ q \stackrel{wa}{\rightarrow} q'\} \end{eqnarray*}\]
Тврдимо да је \(L(\mathcal{A}) = L(\mathcal{A}')\)
\[\begin{eqnarray*} L(\mathcal{A}) &=& \{w \in \Sigma^*\ |\ (\exists i \in I)(\exists f \in F)(i \stackrel{w}{\rightarrow} f)\}\\ &=& \{w \in \Sigma^*\ |\ (\exists f \in F)(\exists i \in I)(i \stackrel{w}{\rightarrow} f)\}\\ &=& \{w \in \Sigma^*\ |\ (\exists f \in F)(f \in \{q\ |\ (\exists i \in I)(i \stackrel{w}{\rightarrow} q)\})\}\\ &=& \{w \in \Sigma^*\ |\ (\exists f \in F)(f \in \bigcup_{i \in I}\{q\ |\ i \stackrel{w}{\rightarrow} q\})\}\\ &=& \{w \in \Sigma^*\ |\ (\exists f \in F)(f \in \delta^*(I, w))\}\\ &=& \{w \in \Sigma^*\ |\ \delta^*(I, w) \cap F \neq \emptyset\}\\ &=& \{w \in \Sigma^*\ |\ \delta^*(I, w) \in F'\}\\ &=& L(\mathcal{A'})\\ \end{eqnarray*}\]
детерминизација аутомата захтева да се унапред обраде сва стања (којих може бити експоненцијално много) и да се направи потенцијално огромна таблица преласка
уместо да се детерминистички аутомат изгради пре провере припадности ниске језику, могуће је идеју детерминизације спроводити током те провере
тај алгоритам се понекад назива ефикасна симулација рада НКА
у сваком кораку памтимо само текуће стање детерминистичког тј. скуп стања детерминистичког аутомата
читамо једно по једно слово речи коју проверавамо и применом дефиниције функције \(\delta\) из алгоритма детерминизације ажурирамо скуп стања НКА (тј. мењамо стање ДКА).
Ако НКА има \(m\) стања, а реч је дужине \(n\), сложеност провере је \(O(mn)\).
Подсетимо се, аутомат је потпун ако у сваком стању из \(Q\) постоји прелаз по сваком слову из \(\Sigma\).
Сваки аутомат можемо веома једноставно употпунити.
Додамо “стање грешке” и додамо све прелазе које недостају, усмеравајући их ка том стању. Стање грешке је незавршно и из њега не може да се изађе (по сваком слову се из стања грешке прелази у стање грешке).
Пример.
Да ли је могуће смањити број стања аутомата, тако да он препознаје исти језик?
Касније ћемо доказати да је за сваки регуларни језик јединствено одређен минимални детерминистички, потпуни коначни аутомат (сваки потпуни ДКА можемо редуковати док не добијемо тај јединствени аутомат са најмањим могућим бројем стања).
Основна идеја: идентификовати стања међу којима нема суштинске разлике (која су на неки начин еквивалентна).
Прва идеја: два стања су еквивалентна ако су оба завршна или оба незавршна и имају исте прелазе по сваком слову. Таква су стања 3 и 4 у наредном примеру.
Пример.
| \(a\) | \(b\) | |
|---|---|---|
| \(0\) | \(1\) | \(2\) |
| \(1\) | \(3\) | \(2\) |
| \(2\) | \(4\) | \(1\) |
| \(\bf{3}\) | \(4\) | \(3\) |
| \(\bf{4}\) | \(4\) | \(3\) |
Стања 1 и 2 немају исте прелазе, али јесу еквивалентна (када се стопе стања 3 и 4, стања 1 и 2 ће имати веома сличне прелазе).
Шта је најопштија могућа дефиниција еквиваленције два стања? Два стања су еквивалентна ако и само су им исти језици тј. ако и само ако им је исти скуп речи који из тих стања доводи до завршних стања.
Језик стања: За стање \(q \in Q\) језик стања \(L_q = \{w \in \Sigma^*\ |\ \delta^*(q, w) \in F\}\).
Неродова еквиваленција: Два стања \(p\) и \(q\) су еквивалентна (што обележавамо са \(p \sim q\)) ако и само ако је \(L_p = L_q\). Стања \(p\) и \(q\) још називамо и неразликујућа.
Став: Неродова еквиваленција је релација еквиваленције. Доказ је јако једноставан (за вежбу). Класе еквиваленције обележавамо са \(Q/\sim\). Са \([q]\) обележавамо класу еквиваленције стања \(q\).
Нека је дат ПДКА \(\mathcal{A} = (\Sigma, Q, i, F, \delta)\) и релација еквиваленције \(\sim\). Количнички аутомат је аутомат \(\mathcal{A}/\sim = (\Sigma, Q/\sim, [i], F', \delta')\), где је
\[F' = \{[q]\ |\ q \in F\}\]
\[\delta'([q], a) = [\delta(q, a)]\]
Докажимо да је \([q] \in F'\) акко је \(q \in F\). Један смер следи директно из дефиниције \(F'\) (ако је \(q \in F\), тада је \([q] \in F'\)), али други не. Потребно је доказати да није могуће да је класа еквиваленције неког завршног стања иста као класа еквиваленције неког незавршног стања, тј. да није могуће да је неко завшно еквивалентно неком незавршном стању. Дакле, довољно је доказати да из \(p \sim q\) следи \(p \in F\) акко \(q \in F\). Међутим, то следи из тога што је \(L_p = L_q\), па \(\varepsilon\) припада језику \(L_p\) тј. \(L_q\) акко \(p \in F\) тј. \(q \in F\) (јер у ПДКА нема \(\varepsilon\)-покрета). Дакле, у свакој класи Неродове еквиваленције (класи релације \(\sim\)), или су сва стања завршна или су сва стања незавршна.
Докажимо да је функција \(\delta'\) добро дефинисана. Потребно је и довољно да докажемо да за свако \(p, q \in Q\) и \(a \in \Sigma\) из \(p \sim q\) следи \(\delta(p, a) \sim \delta(q, a)\). Дакле, из претпоставке \(L_p = L_q\) треба доказати \(L_{\delta(p, a)} = L_{\delta(q, a)}\).
Важи да је
\[\begin{eqnarray*} L_{\delta(p, a)} &=& \{w\in \Sigma^*\ |\ \delta^*(\delta(p, a), w) \in F\}\\ &=& \{ w \in \Sigma^* \ |\ \delta^*(p, aw) \in F\} \\ &=& \{w \in \Sigma^*\ |\ aw \in L_p\} \end{eqnarray*}\]
а то су тачно сви суфикси (без првог слова) речи из \(L_p\).
Слично је
\[L_{\delta(q, a)} = \{w \in \Sigma^*\ |\ aw \in L_p\}.\]
Пошто је \(L_p = L_q\), ова два скупа су једнака.
Напомена: Скуп \(\{w \in \Sigma^*\ |\ aw \in L\}\) назива се леви количник језика \(L\) по слову \(a\) и обележава се са \(a^{-1}L\). Овај појам ћемо детаљније изучавати у каснијим деловима курса.
Лема: За свако стање \(q\in Q\) и сваку реч \(w \in \Sigma^*\) важи
\[\delta'^*([q], w) = [\delta^*(q, w)]\]
Доказ индукцијом по дужини речи \(w\).
База: важи да је \(\delta'^*([q], \varepsilon) = [q] = [\delta^*(q, \varepsilon)]\)
Индуктивна хипотеза: тврђење важи за све речи \(w\) дужине \(k\). Разматрамо реч \(w\) дужине \(k+1\).
\[\delta'^*([q], wa) = \delta'(\delta'^*([q], w), a) = \delta'([\delta^*(q, w)], a) = [\delta(\delta^*(q, w), a)] = [\delta^*(q, wa)]\]
Теорема: Језик аутомата и његовог количничког аутомата је исти.
Доказ.
\[\begin{eqnarray*} L(\mathcal{A}/\sim) &=& \{w \in \Sigma^*\ |\ \delta'^*([i], w) \in F'\}\\ &=& \{w \in \Sigma^*\ |\ [\delta^*(i, w)] \in F'\}\\ &=& \{w \in \Sigma^*\ |\ \delta^*(i, w) \in F\}\\ &=& L(\mathcal{A}) \end{eqnarray*}\]
Ако познајемо Неродове класе еквиваленције, количнички аутомат можемо добити на веома једноставан начин (стапањем стања у истој класи у једно стање).
Централно питање је како одредити Неродове класе еквиваленције?
Муров алгоритам је заснован на индуктивно-рекурзивној конструкцији класа еквиваленције релације \(\sim\).
Конструише се низ релација \(\sim_k\), које све прецизније и прецизније процењују релацију \(\sim\), све док је у једном тренутку не достигну.
Нека је \(L_q^k\) скуп речи дужине највише \(k\) које се могу успешно прихватити из стања \(q\).
\[L_q^k = \{w \in \Sigma^*\ |\ \delta^*(q, w) \in F \wedge |w| \leq k\}.\]
Дефинишемо
\[p \sim_k q \Leftrightarrow L_p^k = L_q^k.\]
Низ релација \(\sim_k\) (тј. њихове класе еквиваленције) се може израчунати на основу следећих рекурентних веза.
\[p \sim_0 q \Leftrightarrow (p \in F \Leftrightarrow q \in F)\]
\[p \sim_{k+1} q \Leftrightarrow p \sim_k q \wedge (\forall a \in \Sigma)(\delta(p, a) \sim_k \delta(q, a))\]
Друго тврђење се може формулисати и на следећи начин:
\[p \not\sim_{k+1} q \Leftrightarrow p \not\sim_k q \vee (\exists a \in \Sigma)(\delta(p, a) \not\sim_k \delta(q, a))\]
Докажимо да је
\[p \sim_0 q \Leftrightarrow (p \in F \Leftrightarrow q \in F)\]
По дефиницији је \(p \sim_0 q \Leftrightarrow L^0_p = L^0_q\).
По дефиницији важи и да је \(L^0_p = \{w \in \Sigma^*\ |\ \delta^*(p, w) \in F \wedge |w| = 0\}\). Даље, \(|w|=0\) важи акко је \(w = \varepsilon\). Зато
\[L_p = \left\{\begin{array}{ll} \emptyset, & p \notin F\\ \{\varepsilon\}, & p \in F \end{array}\right.\]
Пошто исто важи и за стање \(q\), тврђење је доказано.
Из \(p \sim_{k+1} q\) тривијално следи \(p \sim_k q\). Наиме, важи \(L_p^{k+1} = L_q^{k+1}\). Међутим, важи да се \(L_p^{k+1}\) може разложити на своја два дисјунктна подскупа:
\[L_p^{k+1} = L_p^k \cup \{w \in \Sigma^*\ |\ \delta^*(p, w) \in F \wedge |w| = k+1\}.\]
Слично је и
\[L_q^{k+1} = L_q^k \cup \{w \in \Sigma^*\ |\ \delta^*(q, w) \in F \wedge |w| = k+1\}.\]
Важи и да су \(L_q^{k}\) и \(\{w \in \Sigma^*\ |\ \delta^*(p, w) \in F \wedge |w| = k+1\}\), као и \(L_p^{k}\) и \(\{w \in \Sigma^*\ |\ \delta^*(q, w) \in F \wedge |w| = k+1\}\) дисјунктни (због дужина речи које садрже), па одатле мора да следи и да је \(L_p^k = L_q^k\) тј. \(p \sim_k q\).
Докажимо и да из \(p \sim_{k+1} q\) следи \((\forall a \in \Sigma)(\delta(a, p) \sim_k \delta(a, q))\). Претпоставимо супротно. Нека је \(a \in \Sigma\) такво да је \(\delta(a, p) \not\sim_k \delta(a, q)\). То значи да је \(L^k_{\delta(a, p)} \neq L^k_{\delta(a, q)}\). Без губитка на општости можемо претпоставити да постоји реч \(w\in \Sigma^*\), таква да \(\delta^*(\delta(p, a), w) \in F\) и да \(\delta^*(\delta(q, a), w) \notin F\). Међутим, тада важи \(\delta^*(p, aw) \in F\) и \(\delta^*(q, aw) \notin F\). Пошто је \(|aw| \leq k+1\), следи да је \(L^{k+1}_p \neq L^{k+1}_q\), тј. да је \(p \not\sim_{k+1} q\), што је контрадикција.
Докажимо да из \(p \sim_k q\) и \((\forall a \in \Sigma)(\delta(a, p) \sim_k \delta(a, q))\) следи \(p \sim_{k+1} q\). Претпоставимо супротно. То значи да је \(L_p^{k+1} \neq L_q^{k+1}\). Пошто је \(L_p^k = L_q^k\), мора да постоји нека реч дужине \(k+1\) која припада једном, а не припада другом језику. Без губитка на општости, претпоставимо да је то нека реч \(aw\), где је \(|w| = k\) и где је \(\delta^*(p, aw) \in F\) и \(\delta^*(q, aw) \notin F\). Зато је \(\delta^*(\delta(p, a), w) \in F\) и \(\delta^*(\delta(q, a), w) \notin F\). Међутим, то значи да постоји реч \(w\) дужине \(k\) која разликује стања \(\delta(p, a)\) и \(\delta(q, a)\), што значи да је \(\delta(p, a) \not\sim_k \delta(q, a)\), што је у контрадикцији са претпоставком (јер је \(a \in \Sigma\)).
Прикажимо сада како се примењује Мурова конструкција.
Крећемо од класа еквиваленције релације \(\sim_0\) – постоје две класе: у једној су сва завршна стања, а у другој сва незавршна стања.
Са порастом \(k\) неке класе се “цепају”, али се различите класе никада не могу спојити.
Цепање класа се мора зауставити у једном тренутку (када је аутомат већ минималан, то ће се десити када све класе постану једночлане), за неко \(m\) важиће да је \(\sim_m = \sim_{m+1} = \sim_{m+2} = \ldots\). Међутим, тада мора да важи и да је \(\sim_m = \sim\) и Неродова еквиваленција је конструисана.
Минимализујмо аутомат
У питању је ПДКА, па нема потребе за употпуњавањем.
Класе еквиваленције релације \(\sim_0\): \(\{0, 1, 2, 4\}\), \(\{3\}\) – незавршна и завршна стања.
Класе еквиваленције релације \(\sim_1\): \(\{0, 1, 4\}\), \(\{2\}\), \(\{3\}\). Слово \(b\) је то које раздваја стање \(2\) од осталих. На пример, важи \(\delta(2, b) = 3\), \(\delta(4, b) = 4\) и \(3 \not\sim_0 4\), па важи \(2 \not\sim_1 4\). Заиста, пошто је \(3 \in F\) и \(4 \notin F\), важи да је \(b \in L_2^1\) и \(b \notin L_4^1\), па је \(L_4^1 \neq L_2^1\). Стања \(0\), \(1\) и \(2\) су неразликујућа када се анализирају само речи дужине \(1\).
Класе еквиваленције релације \(\sim_2\): \(\{0, 4\}\), \(\{1\}\), \(\{2\}\), \(\{3\}\). Слово \(b\) је то које раздваја стање \(1\) од стања \(0\) и \(4\). На пример, важи \(\delta(1, b) = 2\), \(\delta(4, b) = 4\) и \(2 \not\sim_1 4\), па важи \(1 \not\sim_2 4\). Једна реч која раздваја стања \(1\) и \(4\) је \(bb\). Слово \(b\) преводи стања \(1\) и \(4\) у стања \(2\) и \(4\), а у претходном кораку смо установили да \(b\) преводи стања \(2\) и \(4\) у стања \(3\) и \(4\), где је прво завршно, а друго није. Зато је \(bb \in L_1^2\) и \(bb \notin L_4^2\), па \(L_1^2 \neq L_4^2\). Стања \(0\) и \(4\) није могуће разликовати речима дужине највише 2.
Класе еквиваленције релације \(\sim_3\): \(\{0, 4\}\), \(\{1\}\), \(\{2\}\), \(\{3\}\). Заиста, пошто су прелази из стања \(0\) и \(4\) идентични, важи да \(0 \sim_2 4\), и за свако \(a \in \Sigma\) важи \(\delta(0, a) \sim_2 \delta(4, a)\) (јер је \(\delta(0, a) = \delta(4, a)\)), па је \(0 \sim_3 4\). Зато је \(\sim_2 = \sim_3 = \sim_4 = \sim_5 = \ldots = \sim\).
Када смо пронашли класе еквиваленције релације \(\sim\), градимо количнички аутомат.
Пример. Минимализујмо, вежбе ради и наредни аутомат
Класе еквиваленције релације \(\sim_0: \{0, 1, 2\}, \{3, 4\}\)
Прелази стања \(3\) и стања \(4\) су једнаки, па се та стања разликују.
Слово \(a\) разликује стање \(0\) и стање \(1\) (из \(1\) се прелази у класу \(\{3, 4\}\), а из \(0\) у класу \(\{0, 1, 2\}\)).
Стања \(1\) и \(2\) се не разликују (са \(a\) оба прелазе у класу \(\{3, 4\}\), а са \(b\) остају у класи \(\{0, 1, 2\}\)).
Класе еквиваленције релације \(\sim_1: \{0\}, \{1, 2\}, \{3, 4\}\)
Прелази стања \(3\) и стања \(4\) су једнаки, па се та стања разликују.
Стања \(1\) и \(2\) се не разликују (са \(a\) оба прелазе у класу \(\{3, 4\}\), а са \(b\) остају у класи \(\{1, 2\}\)).
Класе еквиваленције релације \(\sim_2: \{0\}, \{1, 2\}, \{3, 4\}\).
Класе су се поклопиле, па смо конструисали релацију \(\sim\).
Лема (Арден). Ако су \(P\) и \(Q\) регуларни језици тако да \(\varepsilon \notin P\), тада једначина \(X = PX \cup Q\) има јединствено решење \(X = P^*Q\).
Доказ. \(X = P^*Q\) јесте решење јер важи \(PX\cup Q = P(P^*Q) \cup Q = P^+Q\cup Q = P^*Q = X\).
Докажимо да је то решење јединствено.
Докажимо прво да је оно садржано у сваком другом решењу.
Прво, из \(X = PX \cup Q\) јасно је да \(Q \subseteq X\).
Даље, ако је \(Y \subseteq X\), тада је и \(P^*Y \subseteq X\). Докажимо ово. Потребно је да докажемо да важи \(\left(\bigcup_{i=0}^\infty P^i\right)Y \subseteq X\) тј. да је \(\bigcup_{i=0}^\infty P^iY \subseteq X\). Довољно је да докажемо да за свако \(i \in \mathbb{N}\) важи да је \(P^iY \subseteq X\) (унија подскупова скупа је подскуп скупа). То доказујемо индукцијом по \(i\).
За \(i=0\) важи \(P^0Y = Y \subseteq X\) (јер смо то претпоставили).
Индуктивна хипотеза је да тврђење важи за \(P^iY \subseteq X\). Одатле важи \(P \cdot P^iY \subseteq P\cdot X\), а одатле важи \(P^{i+1}Y \cup Q \subseteq PX \cup Q\). Пошто је \(X\) решење једначине тада важи да је \(PX \cup Q = X\), па је \(P^{i+1}Y \cup Q \subseteq X\) и важи \(P^{i+1}Y \subseteq X\).
Дакле знамо да је \(P^*Q \subseteq X\), тј. да је свако решење \(X\) облика \(P^*Q \sqcup X'\), за неки језик \(X'\) (унија је дисјунктна, што значи да \(P^*Q \cap X' = \emptyset)\). Докажимо да ако \(\varepsilon \notin P\), тада је \(X' = \emptyset\).
Пошто је \(X\) решење једначине, важи да је \(PX \cup Q = X\) тј. да је \(P(P^*Q \cup X') \cup Q = P^*Q \cup X'\). Међутим, важи и да је \(P(P^*Q \cup X') \cup Q = P^+Q \cup Q \cup PX' = P^*Q \cup PX'\). Дакле, \(P^*Q \cup X' = P^*Q \cup PX'\). Пошто је \(P^*Q \cap X' = \emptyset\), мора да важи да је \(X' \subseteq PX'\). Међутим, то је немогуће, ако је \(X'\) непразан. Посматрајмо најкраћу реч у \(X'\). Пошто \(\varepsilon \notin P\), важи да су све речи у \(PX'\) дуже него што је дужина те најкраће речи. Зато она не може да припадне језику \(PX'\), па не може да важи \(X' \subseteq PX'\).
Дакле, пошто је \(X' = \emptyset\), важи да је \(X = P^*Q\) јединствено решење.
Језик сваког аутомата може да се опише регуларним изразом. Једна метода је да формирамо систем линеарних једначина са регуларним коефицијентима и да га решимо применом Арденове леме. Систем се формира на следећи начин.
Нека је дат аутомат без \(\varepsilon\)-прелазака \(\mathcal{A} = (\Sigma, Q, i, F, \delta)\) и нека је \(L_q\) језик сваког стања \(q \in Q\). Тада је \(L_q = \bigcup_{(q, a, q') \in \Delta} aL_{q'}\) ако \(q \notin F\) тј. \(L_q = \bigcup_{(q, a, q') \in \Delta} aL_{q'} \cup \{\varepsilon\}\) ако \(q \in F\).
Размотримо аутомат:
Систем једначина који карактерише овај аутомат је:
\[\begin{eqnarray*} L_0 &=& aL_1\\ L_1 &=& aL_1 | bL_2\\ L_2 &=& \varepsilon \end{eqnarray*}\]
Последњу једначину можемо уврстити у претпоследњу и добијамо \(L_1 = aL_1 | b\), коју можемо решити Арденовом лемом. Зато је \(L_1 = a^*b\). Зато је \(L_0 = aL_1 = aa^*b = a^+b\).
Одредимо језик аутомата
Систем једначина који карактерише овај аутомат је:
\[\begin{eqnarray*} L_0 &=& bL_0 | aL_1\\ L_1 &=& aL_1 | bL_2\\ L_2 &=& aL_1 | bL_3\\ L_3 &=& aL_1 | bL_0 | \varepsilon \end{eqnarray*}\]
Последњу једначину можемо уврстити у претпоследњу и добијамо
\[L_2 = aL_1 | baL_1 | bbL_0 | b\]
Ову једначину можемо уврстити у претходну и добијамо.
\[L_1 = aL_1 | baL_1 | bbaL_1 | bbbL_0 | bb = (a|ba|bba)L_1\ |\ bbbL_0 | bb\]
Ова једначина може да се реши Арденовом лемом и добијамо:
\[L_1 = (a|ba|baa)^*(bbbL_0|bb)\]
Ово се може уврстити у прву једначину и добијамо
\[L_0 = bL_0\ |\ a(a|ba|baa)^*(bbbL_0|bb) = (b | a(a|ba|baa)^*bbb)L_0\ |\ a(a|ba|baa)^*bb\]
Применом Арденове леме добијамо коначно решење
\[L_0 = (b | a(a|ba|baa)^*bbb)^*a(a|ba|baa)^*bb\]
Приметимо да смо добили регуларни израз који је знатно компликованији од \((a|b)^*abb\), од којег је добијен аутомат. Ако се не примењује упрошћавање регуларних израза током поступка решавања система, регуларни израз који се добије може бити прилично компликован. Са друге стране, значај овог поступка је углавном само теоријски (за имплементацију су нам кориснији аутомати него регуларни изрази), па нећемо пуно водити рачуна о овоме.
Регуларни језици и коначни аутомати су по дефиницији затворени за унију
Међутим, да ли су затворени за пресек, комплемент и остале скуповне операције?
Јесу! Доказаћемо то конструкцијом производа аутомата. Прозвод суштински истовремено (паралелно) симулира рад два аутомата.
Нека су дати ПДКА \(\mathcal{A}_1 = (\Sigma, Q_1, i_1, F_1, \delta_1)\) и \(\mathcal{A}_2 = (\Sigma, Q_2, i_2, F_2, \delta_2)\).
Производ аутомата \(\mathcal{A}_1 \times \mathcal{A}_2\) је аутомат \((\Sigma, Q_1 \times Q_2, (i_1, i_2), F, \delta)\), где се \(F\) одређује у зависности од тога који језик желимо да прихватимо, док се \(\delta\) дефинише помоћу \(\delta((q_1, q_2), a) = (\delta_1(q_1, a), \delta_2(q_2, a))\).
Ако желимо да прихватимо пресек језика \(L_1 \cap L_2\), тада је \(F = F_1 \times F_2\).
Лема: Важи \(\delta^*((q_1, q_2), w) = (\delta_1^*(q_1, w), \delta_2^*(q_2, w))\).
Доказ индукцијом по дужини речи \(w\).
База. \(\delta^*((q_1, q_2), \varepsilon) = (q_1, q_2) = (\delta_1^*(q_1, \varepsilon), \delta_2^*(q_2, \varepsilon))\).
ИХ: тврђење важи за реч \(w\). Тада је
\[\begin{eqnarray*} \delta^*((q_1, q_2), wa) &=& \delta(\delta^*((q_1, q_2), w), a)\\ &=& \delta((\delta_1^*(q_1, w), \delta_2^*(q_2, w)), a) \\ &=&(\delta_1(\delta_1^*(q_1, w), a), \delta_2(\delta_2^*(q_2, w), a))\\ &=& (\delta_1^*(q_1, wa), \delta_2^*(q_2, wa)) \end{eqnarray*}\]
Докажимо да је језик приозвода једнак пресеку језика, ако је \(F = F_1 \times F_2\).
\[\begin{eqnarray*} L(\mathcal{A}_1 \times \mathcal{A}_2) &=& \{w \in \Sigma^*\ |\ \delta^*((i_1, i_2), w) \in F\}\\ &=& \{w \in \Sigma^*\ |\ (\delta_1^*(i_1, w), \delta_2^*(i_2, w)) \in F_1 \times F_2\}\\ &=& \{w \in \Sigma^*\ |\ \delta_1^*(i_1, w) \in F_1\ \wedge\ \delta_2^*(i_2, w)) \in F_2\}\\ &=& \{w \in \Sigma^*\ |\ w \in L(\mathcal{A}_1)\ \wedge\ w \in L(\mathcal{A}_2)\}\\ &=& \{w \in \Sigma^*\ |\ w \in L(\mathcal{A}_1) \cap L(\mathcal{A}_2)\}\\ &=& L(\mathcal{A}_1) \cap L(\mathcal{A}_2) \end{eqnarray*}\]
Слично се може доказати да
Комплемент језика \(L\) је \(\Sigma^* \setminus L\). За потпун детерминистички коначни аутомат \((\Sigma, Q, i, F, \delta)\) он се може конструисати још једноставније као \((\Sigma, Q, i, Q \setminus F, \delta)\) — завршна стања постају незавршна, а незавршна постају завршна (почетно стање остаје исто). Потпуност је јако важна (конструисати контрапример).
Разматрамо ПДКА.
Ако је \(\delta(p, a) = q\) тада важи да је \(L_p = aL_q \cup \ldots\) тј. да је \(aL_q \subseteq L_p\). Да ли можда можемо изразити некако \(L_q\) у функцији \(L_p\)? Можемо! Размотримо све речи које нас од \(p\) воде до неког завршног стања и издвојимо оне од њих које почињу са \(a\). Када прочитамо то \(a\) долазимо у стање \(q\) а затим одатле читамо остатак речи и долазимо у неко завршно стање. То значи да се \(L_q\) састоји од суфикса речи из \(L_p\) које почињу са \(a\), који се добијају када се обрише то \(а\) са почетка.
Дефиниција: Леви количник језика \(L\) по слову \(a\) је
\[a^{-1}L = \{w \in \Sigma^*\ |\ aw \in L\}\]
Леви количник језика \(L\) по речи \(w\) је
\[w^{-1}L = \{w' \in \Sigma^*\ |\ ww' \in L\}\]
Леве количнике можемо лако одредити за регуларне језике.
Са \(Q(L)\) означавамо скуп свих левих количника језика \(L\) (по било којој речи из \(\Sigma^*\)).
\[Q(L) = \{w^{-1}L\ |\ w \in \Sigma^*\}\]
Лема (веза између левих количника и језика стања аутомата): Нека је \(\mathcal{A}\) потпуни детерминистички коначни аутомат у ком су сва стања доступна. Тада је скуп свих језика стања једнак скупу свих количника тј. \(\{L_q\ |\ q \in Q\} = Q(L)\). Другим речима, сваки леви количник јесте језик неког стања аутомата и сваки језик стања јесте неки леви количник.
Претпоставимо да је \(q\) неко стање и да важи да је \(\delta^*(i, w) = q\). Тада је \(L_q = w^{-1}L\). Докажимо то.
\[\begin{eqnarray*} L_q &=& \{w \in \Sigma^*\ |\ \delta^*(q, w) \in F\} \\ &=& \{w' \in \Sigma^*\ |\ \delta^*(q, w') \in F\} \\ &=& \{w' \in \Sigma^*\ |\ \delta^*(\delta^*(i, w), w') \in F\} \\ &=& \{w' \in \Sigma^*\ |\ ww' \in L\} \\ &=& w^{-1}L \end{eqnarray*}\]
Докажимо сада да је сваки леви количник језик неког стања. Размотримо произвољни леви количник \(w^{-1}L\), за неко \(w \in \Sigma^*\). Пошто је аутомат потпун, постоји неко стање \(q = \delta^*(i, w)\). Тада је \(L_q = w^{-1}L\).
Докажимо сада да је сваки језик стања неки леви количник. Разматрајмо произвољно стање \(q\). Пошто су сва стања доступна, постоји неко \(w \in \Sigma^*\) такво да је \(q = \delta^*(i, w)\). Тада је \(L_q = w^{-1}L\).
Последица: Ако је језик \(L\) регуларан, тада је скуп свих левих количника \(Q(L)\) коначан.
Ако је језик \(L\) регуларан, тада постоји коначни аутомат \(\mathcal{A}\) такав да је \(L = L(\mathcal{A})\). Он има коначно много стања \(Q\). Пошто је \(Q(L) = \{L_q\ |\ q \in Q\}\), а \(Q\) је коначан скуп, важи да је \(Q(L)\) коначан.
Важи и обратно. Ако је скуп левих количника коначан, језик је регуларан.
Докажимо то тако што ћемо конструисати коначни аутомат \(\mathcal{M}(L)\) чији ће скуп стања бити \(Q(L)\).
\[\mathcal{M}(L) = (\Sigma, Q(L), L, F, \delta),\]
где је \(F = \{w^{-1}L\ |\ \varepsilon \in w^{-1}L\} = \{w^{-1}L\ |\ w \in L\}\), а важи \(\delta(w^{-1}L, a) = a^{-1}(w^{-1}L) = (wa)^{-1}L\).
Лема: Важи да је \(\delta^*(w^{-1}L, w') = (w')^{-1}(w^{-1}L) = (ww')^{-1}L\).
Доказ, индукцијом по дужини речи \(w'\).
База индукције је \(w'=\varepsilon\) и тада је \(\delta^*(w^{-1}L, \varepsilon) = w^{-1}L = (w\varepsilon)^{-1}L\).
Претпоставимо да тврђење важи за реч \(w'\). Размотримо реч \(w'a\). Тада важи
\[\delta^*(w^{-1}L, w'a) = \delta(\delta^*(w^{-1}L, w'), a) = \delta((ww')^{-1}L, a) = (ww'a)^{-1}L.\]
Важи да је језик аутомата \(\mathcal{M}(L)\) једнак \(L\).
\[\begin{eqnarray*} L(\mathcal{M}(L)) &=& \{w \in \Sigma^*\ |\ \delta^*(L, w) \in \{w^{-1}L\ |\ w \in L\}\}\\ &=& \{w \in \Sigma^*\ |\ w^{-1}L \in \{w^{-1}L\ |\ w \in L\}\}\\ &=& \{w \in L\}\\ &=& L\\ \end{eqnarray*}\]
Слично се може доказати да је за свако стање \(q\) у аутомату \(\mathcal{M}(L)\) које је једнако неком количнику \(w^{-1}L\) језик тог стања \(L_q\) једнак управо \(w^{-1}L\). Зато важи да су језици свих стања различити, тако да су сва стања у аутомату неразликујућа. Зато је тај аутомат минималан.
Дакле, доказали смо следећу теорему.
У књигма се иста ова тврђења некада изражавају мало другачијим језиком.
Дефиниција. Речи \(x, y \in \Sigma^*\) су разликујуће у односу на језик \(L \subseteq \Sigma^*\) акко је \(x^{-1}L \neq y^{-1}L\) тј. ако постоји реч \(w\) таква да је тачно једна од речи \(xw\) и \(yw\) елемент језика \(L\). У супротном су речи \(x\) и \(y\) неразликујуће у односу на \(L\), што обележавамо са \(x \sim_L y\).
Став. Релација \(\sim_L\) је релација еквиваленције.
Теорема. Језик \(L\) је регуларан акко је број класа еквиваленције релације \(\sim_L\) коначан.
Скуп класа еквиваленције релације \(\sim_L\) је \(Q(L)\).
Доказаћемо да је сваки потпуни детерминистички коначни аутомат у коме су сва стања разликујућа изоморфан аутомату \(\mathcal{M}(L)\), тј. да је минимални ПДКА за сваки језик \(L\) јединствен (до на изоморфизам).
Дефиниција (изоморфизам аутомата). Два ДКА \(\mathcal{A}_1 = (\Sigma, Q_1, i_1, F_1, \delta_1)\) и \(\mathcal{A}_2 = (\Sigma, Q_2, i_2, F_2, \delta_2)\) су изоморфна акко постоји бијективна функција \(f: Q_1 \mapsto Q_2\), таква да је
Теорема (Михил-Нерод). Сви ПМДКА у којима су сва стања доступна и који препознају дати регуларни језик \(L\) су међусобно изоморфни.
Доказаћемо да је сваки ПМДКА за језик \(L\) изоморфан аутомату \(\mathcal{M}(L)\), одакле на основу особина релације еквиваленције тривијално следи и да су сви аутомати међусобно изоморфни. Нека је \(\mathcal{A} = (\Sigma, Q, i, F, \delta)\) један ПМДКА у коме су сва стања доступна, такав да је \(L(\mathcal{A}) = L\).
Дефинишимо функцију \(f\) са доменом \(Q\), тако да за свако стање \(q \in Q\) важи \(f(q) = L_q\). На основу ранијих резултата важи да је \(\{L_q\ |\ q \in Q\} = Q(L)\), тј. да је скуп свих слика једнак скупу свих левих количника језика \(L\). Међутим, то је тачно скуп стања минималног аутомата \(\mathcal{M}(L)\).
Докажимо да је \(f\) бијекција.
Сваки количник јесте језик неког стања (подсетимо се, количник \(w^{-1}L\) је једнак \(L_{\delta^*(i, w)}\)), па је функција сурјективна. Докажимо и да је инјективна.
Претпоставимо да за нека два различита стања \(q_1, q_2 \in Q\) важи \(f(q_1) = f(q_2)\). Тада је \(L_{q_1} = L_{q_2}\), што значи да је \(q_1 \sim q_2\), међутим то је директна контрадикција са претпоставком да је аутомат минимализован (код минималних аутомата сва стања су различита и Неродова еквиваленција је једнакост).
Докажимо и да је \(f\) изоморфизам између \(\mathcal{A}\) и \(\mathcal{M}(L)\).
\(f(i) = L_i = L = i^{\mathcal{M}}\), што је почетно стање аутомата \(\mathcal{M}(L)\).
\(f(F) = \{L_q\ |\ q \in F\} = \{L_q\ | \varepsilon \in L_q\}\), јер је \(\varepsilon \in L_q\) ако и само ако је \(q \in F\) (јер у детерминистичком аутомату нема епсилон прелазака). Међутим, пошто је \(\{L_q\ |\ q \in Q\} = Q(L)\), ово је управо скуп левих количника који садрже \(\varepsilon\), тј. \(f(F) = \{w^{-1}L\ |\ \varepsilon \in w^{-1}L\} = \{w^{-1}L\ |\ w \in L\}\), што је управо скуп \(F^\mathcal{M}\) свих завршних стања аутомата \(\mathcal{M}(L)\).
\(f(\delta(q, a)) = L_{\delta(q, a)} = a^{-1}L_q = a^{-1}f(q) = \delta^\mathcal{M}(f(q), a)\). Заиста, пошто је \(\{L_q\ |\ q \in Q\} = Q(L)\), важи да постоји \(w \in \Sigma^*\) такво да је \(f(q) = w^{-1}L\) (пошто је стање \(q\) доступно, то је реч која нас води од стања \(i\) до стања \(q\)), па је \(a^{-1}f(q) = a^{-1}(w^{-1}L) = (wa)^{-1}L\), што је по дефиницији аутомата \(\mathcal{M}\) једнако \(\delta^\mathcal{M}(w^{-1}L, a)\).