Teoria automatelor

În informatica teoretică, teoria automatelor este studiul mașinilor abstracte și al problemelor rezolvabile de acestea. Teoria automatelor este în legătură apropiată cu teoria limbajului formal, automatele fiind clasificate după clasa limbajului formal recunoscut de acestea.

Descriere

Un automat este un model matematic al unei mașini de stare. O mașină de stare este o mașină care, având la intrare un set de simboluri, 'sare' printr-o serie de stări folosind o funcție de tranziție( ce poate fi descrisă de o tabelă). În varietatea "Mealy" de mașini de stare, această funcție de tranziție, bazându-se pe o stare curentă si un simbol curent, determină următoarea stare a automatului.

Din intrare este citit câte un simbol, până cand nu mai este nimic de citit ( poate fi gândit ca o bandă conținând un cuvânt, iar automatul citește banda cu un cap de citire ; acest cap citește un singur caracter la un moment dat). Imediat ce intrarea este epuizată, se spune că 'automatul s-a oprit'.

În functie de starea în care s-a oprit automatul, se spune că automatul acceptă, respectiv respinge, intrarea furnizată. Dacă s-a oprit într-o stare 'acceptă', atunci automatul acceptă cuvăntul. Dacă s-a oprit într-o stare 'respinge', atunci cuvântul este respins. Mulțimea tuturor cuvintelor acceptate de un automat este denumită 'limbajul recunoscut' de automat.

În general, însă, un automat nu are întotdeauna o mulțime finită sau numărabilă de stări. Spre exemplu, un automat finit cuantic are o mulțime nenumărabilă și infinită de stări, deoarece această mulțime este cea a punctelor din spațiul de proiecție complex.

Deci, automatul finit cuantic, cât și mașinile de stare finite, sunt cazuri speciale al unui concept general, acela de automat topologic, unde mulțimea de stări este un spațiu topologic, si funcțiile de tranziție sunt obținute din mulțimea funcțiilor acelui spațiu. Automatele topologice sunt denumite si M-automate și sunt augmentarea unui semiautomat ce are o mulțime dată de stări acceptate. Starea inițială este determinată de intersecția mulțimii starilor M-automatului cu mulțimea funcțiilor din acel spațiu.

În general, un automat nu trebuie neapărat sa accepte sau să respingă o intrare; o poate accepta cu o probabilitate între zero si unu. Acest lucru este iarăși ilustrat de automatul finit cuantic, care acceptă o intrare numai după o anumită probabilitate. Această idee este un caz special al unei noțiuni generale, aceea de 'automat geometric' sau 'automat metric', unde setul de stări este un spațiu metric, și limbajul recunoscut de automat este distanța față de punctul inițial. Mulțimea de stări acceptate este suficient de mică in comparație cu metrica spațiului.

Termeni folosiți

Termenii folositi în teoria automatelorse refera la simboluri si multimi de simboluri, respectiv la operatiile dintre aceste mulțimi.

Simbol sau Literă

O dată arbitrară cu un anumit înțeles și efect asupra mașinii de stare.

Alfabet sau Vocabular

Un alfabet este notat cu $\Sigma$ și reprezintă mulțimea finită de simboluri.

Ex: $\Sigma$ = { a,b }

Concatenare

Notată cu '•', numită si produs de cuvinte, constă în apropierea a doua cuvinte. Fie cuvântul x format din succesiunea de simboluri a₀a₁...a_k și cuvântul y format din succesiunea de simboluri b₀b₁...b_j atunci

x•y = a₀a₁...a_kb₀b₁...b_j, k,j ∈ N

Este o operație asociativă '•' : $\Sigma ^{*}$ → $\Sigma ^{*}$ rezultă că $\Sigma ^{*}$ este un monoid, având λ ca element unitate.

Puterea unui simbol

Notată cu $w^{k}$ este definită ca fiind concatenarea a k simboluri w

Ex: $a^{3}$ = aaa

Cuvânt

O succesiune finită de simboluri, formată prin concatenare.

Ex: a•b•a = aba

Cuvântul vid

λ este secvența formată din concatenarea a zero simboluri.

Limbaj

O mulțime de cuvinte, formată din simbolurile unui alfabet. Poate fi finită sau infinită. $L\subseteq \Sigma ^{*}$

Lungimea lui w

Fie cuvintele w,u ∈ $\Sigma ^{*}$; simbolul a ∈ $\Sigma$ și $L,K\subseteq \Sigma ^{*}$. Lungimea lui w = |w|: numărul de poziții pentru simboluri din w;

|λ| = 0.

|110010| = 6.

Alfabetul lui w

alph(w) = {a ∈ $\Sigma$ | |w|_a ≥ 1}

Puterea unui alfabet

Dacă $\Sigma$ este un alfabet, putem nota mulțimea tuturor cuvintelor de o anumită lungime folosind o notație

exponențială. Definim $\Sigma ^{k}$ ca fiind mulțimea cuvintelor formate cu simboluri din $\Sigma$ , de lungime k.

Ex: $\Sigma$ = {0,1} ; $\Sigma ^{0}$ = λ, $\Sigma ^{1}$ = {0,1}, $\Sigma ^{2}$ = {00, 01, 10, 11} ș.a.m.d.

Închidere Kleene

$\Sigma ^{*}$: Un limbaj $\Sigma$ poate fi gândit ca o submulțime a mulțimii tuturor cuvintelor posibile. Mulțimea tuturor cuvintelor posibile poate fi gândită la rându-i ca mulțimea tuturor concatenărilor posibile de succesiuni. Formal, această mulțime a tuturor succesiunilor este numită un monoid liber generat. Mai pe scurt este mulțimea tuturor cuvintelor finite ( incluzând cuvântul vid ) : $\Sigma ^{*}$ = $\Sigma ^{0}$ ∪ $\Sigma ^{1}$ ∪ $\Sigma ^{2}$ ∪ ...

Mulțimea tuturor cuvintelor finite nevide se noteaza cu $\Sigma ^{+}$

$\Sigma ^{*}$ = $\Sigma ^{+}$ ∪ { λ }

Descriere formală

Un automat este reprezentat de un 5-tuplu $\langle Q,\Sigma ,\delta ,q_{0},F\rangle$, unde:

• Q este mulțimea stărilor.
• ∑ este alfabetul acceptat de automat.
• δ este funcția de tranziție

$\delta :Q\times \Sigma \rightarrow Q.$

(Automatele nedeterministe acceptă și cuvântul vid λ).

• q₀ este starea de început, sau altfel spus, starea în care se află automatul când nici o intrare nu a fost procesată.(q₀∈ Q).
• F este mulțimea stărilor finale ale automatului. F⊆Q ; mai sunt numite și stări acceptă.

Fiind dat un simbol, $a\in \Sigma$, la intrarea automatului atunci funcția de tranziție se poate scrie ca $\delta _{a}:Q\rightarrow Q$, folosind curingul adică $\delta (q,a)=\delta _{a}(q)$ pentru orice $q\in Q$. În acest fel funcția de tranziție poate fi gândită in termeni mai simpli : Luând în considerare compunerea funcțiilor și aplicând-o în mod repetat unor funcții $\delta _{a}$, $\delta _{b}$ ș.a.m.d. Compunerea funcțiilor de tranziție formează un monoid numit monoid de tranziție, sau uneori și semigrup de transfomări.

Fiind dat un două simboluri $a,b\in \Sigma$ atunci se poate defini ${\widehat {\delta }}$, cu ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$, unde $\circ$ este compunere de funcții. Acest proces poate fi continuat în mod recursiv până se obține definirea recursivă a unei funcții ${\widehat {\delta }}_{w}$ definită pentru toate cuvintele $w\in \Sigma ^{*}$,

${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q.$

Construcția poate fi inversată: fie ${\widehat {\delta }}$, se poate construi $\delta$.

Note

1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (Ediția 2)