Крайни автомати. Регулярни операции.

Детерминиран краен автомат

Автомат - това е машина, конструирана да реагира по определен начин при определени подадени инструкции; с една дума - робот.
Крайният автомат (машина с краен брой състояния) е ограничен модел на съвременния компютър. Общото между тях е фактът, че и двете машини имат краен капацитет.
Като входни данни крайният автомат получава низ от символи, но не изкарва нищо като изход. Вместо това индикира дали входните данни се приемат от автомата. В този смисъл, може да се разглежда като машина за разпознаване на определен език. Това, което прави крайния автомат ограничен модел на днешните компютри е
липсата на използвана памет.

На пръв поглед толкова прост изчислителен модел следва да бъде приет като тривиален, за да предизвика изучаването си: каква полза имаме от компютър без памет? Но крайният автомат в действителност притежава памет, но памет, която е ограничена още при "създаването" му, без възможност да бъде разширена. Спорно е дали паметта на компютрите е ограничена, било то от бюджета, било физически, но и неограничена от постоянно разширяващата се Вселена. Дали най-добрият компютър е този с ограничена или този с неограничена памет вече е философски въпрос.
Доброто познаване на теорията на изчислимостта дава възможност да се прецени как би повлияла допълнителна памет върху изчислителната сила на съответния модел.

Една от главните причини да изучаваме крайните автомати е тяхното приложение в дизайна на някои широкоизползвани компютърни алгоритми и програми днес. За пример нека вземем лексикалното анализиране на фразите при компилаторите, където разпознаването на програмните единици като "begin" и "+" често се базира на симулация на краен автомат. Друг проблем - търсенето на подниз в символен низ, може също да бъде решен с помощта на методите, предоставени ни от теорията на крайните автомати.

80183140jw0.jpg

Нека сега разгледаме по-подробно операциите, извършвани от един краен автомат. Устройство, наречено входна лента приема входните данни (символни низове). Лентата е разделена на клетки, в които се записват отдените символи един по един. Главната част на машината е множеството от краен брой състояния("краен" е важно), като машината във всеки един момент се намира в едно от тях. В кое състояние се намира се определя от прочетените символи. На всяка стъпка четящата глава се мести и чете нов символ, започвайки от първия. За първи символ се счита намиращият се най-вляво на лентата. Тогава машината се намира в начално състояние. През равен интервал от време главата се мести по лентата, в резултат от което се преминава в ново състояние, което зависи само от текущото и от прочетения символ - затова и машината се нарича детерминистичен краен автомат. Този процес се повтаря отново и отново; символ бива прочетен, главата се мести надясно, променя се текущото състояние. Евентуално четецът ще достигне последния символ.1Тогава автоматът дава информация дали приема или не входния низ: ако машината се намира в крайно състояние, то считаме, че тя приема входните данни.

Език

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

Формална Дефиниция

Детерминистичен краен автомат се описва от петорката $M = \left( {K,\Sigma ,\delta ,s,F} \right)$, където

  • $K$ е крайно множество от състояния
  • $\Sigma$ е азбука
  • $s \in K$ е начално състояние
  • $F \subseteq K$ е множество от крайни състояния
  • $\delta$ е функция на прехода, $K\times\,\Sigma \, \to K$

Начинът, по който автоматът $M$ се мести от едно състояние в друго, се дефинира във функцията на прехода. Ако $M$ е в състояние $q \in K$ и прочетеният символ е $a \in \Sigma$, тогава $\delta (q,a) \in K$ е единствено състояние, в което $K$ отива. Имайки дефиницията за крайния детерминистичен автомат, ще опишем математически значението на изчисление от автомат върху входен стринг. Грубо казано, това е поредица от конфигурации, описващи машината във всеки един момент. Тъй като главата не може да се връща назад, частта от низа, намираща се вляво от главата не може да повлияе на бъдещата работа на машината. Тоест, конфигурацията е еднозначно определена от текущото състояние и непрочетената част от входа. Или още, текуща конфигурация на детерминистичен краен автомат е наредената тройка $k, a, r$ с елементи от $K\,\Sigma\,\Sigma ^*$. Естествено, още не сме казали какво значи тази звезда. $\Sigma^*$ означава "нула или повече букви от $\Sigma$ подредени една след друга." Може даже и само една.

Релацията |-

Бинарната релация $\vdash_M$ се поставя между две конфигурации на М т.с.т.к. машината може да премине от едната конфигурация в другата на един ход. Тогава ако (q,w) i (q`,w`) са
две конфигурации на машината, (q,w) $\vdash_M$ (q`,w`) тогава и само тогава когато w = aw` за някое $a \in \Sigma$ и $\delta (q,a) = q'$.

Забележете, че релацията $\vdash_M$ е функция от $K\times\,\Sigma ^+$ в $K\times\,\Sigma ^*$(плюсчето означава "един или повече елемента" и затова за всяка конфигурация освен $(q,\varepsilon )$ има еднозначно определена следваща. Конфигурация от вида $(q,\varepsilon )$ означава, че целият вход вече е изчетен и следователно в този момент се преустановяват операциите на автомата.

Ще означим рефлексивното и транзитивно затваряне на $\vdash_M$ с $\vdash^* _M$; $(q,w) \vdash^* _M (q',w')$ означава че (q`,w`) се достига от (q,w) след краен брой стъпки (възможно и 0). Входен низ $w \in \Sigma ^*$ се разпознава от M <=> $\exists q \in F:(s,w)\vdash^* _M (q,\varepsilon )$. Езикът L(M), разпознаван от автомата M, е множеството от всички низове, които се разпознават от автомата.

Пример: Нека М е детерминистичен краен автомат $\left( {K,\Sigma ,\delta ,s,F} \right)$, където

(1)
\begin{array} {l} K = \left\{ {q_{0,} q_1 } \right\}, \\ \Sigma = \left\{ {a,b} \right\}, \\ s = q_0 , \\ F = \{ q_0 \} , \\ \end{array}

и $\delta$ е функцията на прехода:

q $\sigma$ $\delta(q,\sigma )$
q0 a q0
q0 b q1
q1 a q1
q1 b q0

Лесно се забелязва, че L(M) е множеството от всички думи, които съдържат четен брой b.2 M минава от $q_0$ в $q_1$ или от $q_1$ в $q_0$ когато се прочете b. Остава се в същото състояние при прочитане на a.

Ако като вход дадем aabba, началното състояние е $(q_0, aabba)$. Тогава:

(2)
\begin{eqnarray} (q_0 ,aabba) &\vdash& M (q_0 ,abba) \\ &\vdash& M (q_0 ,bba) \\ &\vdash& M (q_1 ,ba) \\ &\vdash& M (q_0 ,a) \\ &\vdash& M (q_0 ,\varepsilon ) \\ \end{eqnarray}

Следователно $(q_0 ,aabba)\vdash^* _M (q_0 ,\varepsilon )$ и оттук aabba се разпознава от М.

Графично представяне

Тъй като горният запис не е най-ясният възможен, често се използват диаграми.
Диаграма на автомат представлява ориентиран граф.

  • Върховете са състоянията.
  • Съществува дъга а от $q$ до $q`$, къдeто $\delta (q,a) = q'$.
  • Началното и Финалните състояния се представят с някакъв визуален маркер. Прието е финалните да са с двойни кръгове, а началното - със стрелка.
80183140jw0.jpg

Забележка! На контролно рисуването на диаграма на автомат не е еквивалентно на доказателство, че автоматът е верен. Дори и когато е болезнено очевидно.
Обвинявай преподавателите.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License