Краен автомат

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

Описание

Крайните автомати четат редица от символи (от входна азбука), наречена входна дума, и извеждат също редица от символи (от изходна азбука), наречена изходна дума. Множеството от всички входни думи се нарича език, разпознаван от автомата.

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

Работата на крайните автомати се състои от определен брой стъпки, като на всяка стъпка се чете следващият символ на входната дума. В зависимост от прочетения символ и състоянието, в което се намира, автоматът извежда редица от изходни символи и преминава в ново състояние.

Съществува опростен вид, означаван като краен разпознавател, който не извежда изходни символи, а само спира след прочитането на входната дума или в разпознаващо състояние, или в неразпознаващо такова. В първия случай се казва, че автоматът разпознава думата, т.е. думата принадлежи на езика, разпознаван от автомата.

Дефиниция

Граф на краен детерминиран автомат

Математически, крайните автомати са представени като ${\mathcal {M}}=(S,\Sigma ,T,I,A)$, където:

• S е множеството на състоянията на автомата
• Σ е азбуката на автомата
• Т е множеството на преходите между състоянията на автомата: (p, x, q) ∈ T където (p, q) ∈ SxS и x ∈ Σ
• I е множеството на началните състояния I⊆S
• A е множеството на крайните състояния на автомата. Това са състояния, които позволяват „излизане“ от автомата. A⊆S

Крайният автомат може да се представи като насочен (ориентиран) граф с етикети на ребрата. Състоянията, представени с две концентрични окръжности са крайните състояния на автомата.

Детерминизъм

Крайните автомати биват детерминирани и недетерминирани. При детерминираните може да има най-много по един преход от дадено състояние за всяка буква от азбуката на автомата, докато при недетерминираните са възможни няколко различни прехода за една и съща буква. Също така детерминираните крайни автомати имат едно-единствено начално състояние.

Всеки недетерминиран автомат може да се преобразува в детерминиран, като последният може да има най-много $2^{n}$ или $Card({\mathcal {P}}(S))$ състояния, където $n=Card(S)$.

Пример за детерминиране:

Недетерминиран краен автомат

Нека имаме един недетерминиран краен автомат ${\mathcal {M}}=(S,\Sigma ,T,I,A)$ такъв, че:

• S = {1,2,3}
• Σ = {a, b}
• T = {(1,a,1), (1,b,1), (1,a,2), (2,a,3), (2,b,3)}
• I = {1}
• A = {3}

Този автомат разпознава езика (a+b)*a(a+b).

$n=Card(S)=3\Rightarrow 2^{3}=8$ е най-големият възможен брой състояния, който можем да имаме в детерминирания автомат. Можем да проверим това и чрез броя на частите на S: ${\mathcal {P}}(S)=\{\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$. Очевидно е, че $Card({\mathcal {P}}(S))=8$.

За да получим състоянията и преходите на детерминирания краен автомат, съставяме следната таблица:

	a	b
{1}	{1,2}	{1}
{1,2}	{1,2,3}	{1,3}
{1,2,3}	{1,2,3}	{1,3}
{1,3}	{1,2}	{1}

Резултатът: детерминиран краен автомат

Получаваме детерминиран краен автомат ${\mathcal {D}}=(S_{\mathcal {D}},\Sigma ,T_{\mathcal {D}},I_{\mathcal {D}},A_{\mathcal {D}})$ такъв, че:

• $S_{\mathcal {D}}=\{\{1\},\{1,2\},\{1,3\},\{1,2,3\}\}$
• Множеството на преходите $T_{\mathcal {D}}$ е представено от таблицата.
• $I_{\mathcal {D}}=\{\{1\}\}$
• $A_{\mathcal {D}}=\{\{1,3\},\{1,2,3\}\}$

Крайните състояния на получения автомат са тези, които съдържат крайните състояния на изходния автомат.

Еквивалентни автомати

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

ω-автомати

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

Автомат с ε-преходи

Това е автомат в който някои от преходите са с празни (ε) етикети, т.е. преминаването през даден преход не променя думата. За да елиминираме ε-преходите, първо трябва да наситим автомата с ε-преходи и след това да ги заместим със съответните преходи с букви. Това действие се използва например в конкатенацията на два автомата.

Запълнен автомат

Запълнен автомат наричаме М, такъв, че ∀ p ∈ S и ∀ x ∈ Σ ∃ q ∈ S такова, че (p, x, q) ∈ T

Т.е. от всяко състояние на автомата имаме по най-малко един преход за всяка буква от азбуката му. Когато автоматът е запълнен и детерминиран, от всяко състояние имаме точно по един преход за всяка буква от Σ.

При запълване на даден автомат добавяме т.нар. състояние кладенец, от което излизат към него по един преход за всяка буква от Σ. След това добавяме преходите с липсващите (за пълнота) букви на всички останали състояния в автомата и ги ориентираме към състоянието кладенец.

Емондирани автомати

Емондиран наричаме този автомат, който има само полезни състояния. Полезно е това състояние, което е достъпно едновременно от поне едно начално и едно крайно състояние. Можем да емондираме всеки не-емондиран автомат просто премахвайки състоянията, които не са полезни.

Автомат трансдуктор

Автомат трансдуктор

Трансдуктор се нарича автомат, който за всеки входящ символ, връща съответстващ изходящ.

Например ако вземем трансдуктора от картинката, за думата bbaa ще получим 0110.

Има два вида трансдуктори – автомат на Мили и автомат на Мур.

Регулярни езици

Множеството на регулярните езици е равно на множеството на езиците, разпознавани от крайни автомати, т.е. всеки език, разпознаван от краен автомат, е регулярен (теорема на Клини (Kleene)). Това означава, че всеки регулярен израз може да се представи като краен автомат и обратното. Това именно е основният принцип, залегнал в работата на програмата grep.