Véges automaták

• Véges automaták
  • Determinisztikus véges automata
    • Az átmenetfüggvény kiterjesztése
  • Nemdeterminisztikus véges automata
    • Szabály alapú alternatív megközelítés
  • Redukció
    • Egylépéses redukció
    • Többlépéses Redukció
    • Elfogadott elv
  • Véges automaták és reguláris nyelvek
  • Véges automata determinizálása
  • Források

Formális nyelvek megadása nemcsak generatív eszközökkel, hanem felismerő eszközökkel is lehetséges. Ilyen eszközök az automaták, amelyek szavak feldolgozására és azonosítására alkalmasak.

Nyelvek megadására a grammatikák a szintetizáló, az automaták analitikus megközelítést alkalmaznak.

Az automaták egy szó feldolgozása után kétféle választ adhat, vagy elfogadja, vagy elutasítja a bemenetet.

• Diszkrét időintervallumokban végrehajtott lépések sorozatán keresztül működik
• A kezdőállípotból indul, az inputszó az inputszalagon helyezkedik el, az olvasófej őedig az inputszó legbaloldalibb szimbólumánál áll.
• Az automata, miután elolvasott egy szimbólumot, az olvasófejet egy pozícióval jobbra mozgatja, majd állapotot vált az állapot-átmenet függvénye szerint.
• Amennyiben az automata még nem olvasta végig a teljes inputot és elfogadó állapotba ér nem dönt még az elfogadásról/elutasításról, tovább m ̋uködik a szabályai szerint.
• Ha az automata elolvasta az inputot, akkor megáll és aktuális állapota alapján válaszol, hogy felismeri vagy elutasítja a bemeneti szót.

Determinisztikus véges automata

Egy rendezett ötös, $$A=⟨Q\Sigma ,\delta ,q_0,F⟩$$ ahol

• $Q$ az állapotok véges, nemüres halmaza
• $\Sigma$ az inputszimbólumok ábécéje
• $\delta :Q\times \Sigma \to Q$ leképzés az ún. állapot-átmenet függvény
• $q_0\in Q$ a kezdőállapot
• $F\supseteq Q$ az elfogadó állapotok halmaza

Az átmenetfüggvény kiterjesztése

Legyen $A$ egy determinisztikus véges automata.

A $\delta$ leképzés kiterjesztése az a $\hat{\delta }:Q\times {\Sigma }^{\ast }\to Q$ teljes leképzés, amelyre

• $\hat{\delta }(q,ϵ):=q$
• $\hat{\delta }(q,xa):=\delta (\hat{\delta }(q,x),a)(\forall x\in {\Sigma }^{\ast },a\in \Sigma )$

$\delta (q,u)$ tehát az az állapota az automatának, ahova a $q$ állapotból indulva az $u$ szó feldolgozása után eljut.

Ha $\hat{\delta }(q_0,u)\in F$, akkor az $u$ inputot elfogadja $A$, ha $\hat{\delta }(q_0,u)\notin F$, akkor elutasítja.

elhagyjuk.

Nemdeterminisztikus véges automata

Determinisztikus véges automata:

• A $\delta$ függvény mindenütt értelmezett és egyértékű. Azaz minden $(q,a)\in Q\times \Sigma$ párra pontosan egy olyan s állapot létezik, amelyre $\delta (q,a)=s$ fennáll.

Nemdeterminisztikus véges automata:

• Megengedjük az állapot-átmenet függvény többértékűségét, azaz $\delta$ ekkor egy $Q\times \Sigma \to P(Q)$ leképezés.
• Több kezdoállapot is megengedett (azaz a kezdőállapotok $Q_0$ halmazára $Q_0\subseteq Q$).
• Úgy interpretálhatjuk, hogy a $q\in Q$ állapotból az $a\in \Sigma$ betű olvasására a gép egy tetszoleges $\delta (q,a)$-beli új állapotba léphet, azaz adott inputra több működés lehetséges.
• Mivel $\varnothing \in P(Q)$, ezért elofordulhat, hogy az $\delta (q,a)=\varnothing$ valamely $(q,a)$-ra, ilyenkor elakad a gép.
• Akkor fogad el egy bemenetet, ha van legalább egy $F$-beli állapotban termináló működése.

A nemdeterminisztikus véges automata egy rendezett ötös, $$A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$$ ahol

• $Q$ az állapotok egy véges, nemüres halmaza
• $\Sigma$ az inputszimbólumok ábécéje
• $\delta :Q\times \Sigma \to \mathcal{P}(Q)$ leképzés, az állapot-átmenet függvény
• $Q_0⫅Q$ a kezdőállapotok halmaza
• $F⫅Q$ az elfogadó állapotok halmaza.

A determinisztikus véges automata a nemdeterminisztikus véges automata egy speciális esetének tekinthető.

Szabály alapú alternatív megközelítés

Legyen $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ egy nemdeterminisztikus véges automata-

Az átmenetek szabály alapon történő megadása:

Az $A$-hoz tartozó $M_{\delta }$ szabályrendszerhez minden $p,q\in Q,a\in \Sigma ,p\in \delta (q,a)$ esetén adjunk hozzá a $$qa\to p$$ alakú átírási szabályt, azaz $$M_{\delta }=\{qa\to p|p,q\in Q,a\in \Sigma ,p\in \delta (q,a)\}$$

Redukció

Egylépéses redukció

Láttuk, hogy az automata további műuködése mindig csak az aktuális, $q\in Q$ állapottól és a bemenet még hátralévo olvasatlan $w\in {\Sigma }^{\ast }$ suffixétol függ. Ez motiválja a következőt.

Egy $u\in Q{\Sigma }^{\ast }$ szót az $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ NDVA egy konfigurációjának nevezzük.

Legyen $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ egy véges automata és legyenek $u,v\in Q{\Sigma }^{\ast }$ konfigurációk. Az $A$ automata az $u$ szót egy lépésben a $v$ szóra redukálja, ha van olyan $qa\to p\in M_{\delta }$ szabály, és olyan $w\in {\Sigma }^{\ast }$ szó, hogy $u=qaw$ és $v=pw$ teljesül.

Többlépéses Redukció

Az $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ véges automata az $u\in Q{\Sigma }^{\ast }$ szót a $v\in Q{\Sigma }^{\ast }$ szóra redukálja, ha vagy $u=v$ vagy valamelyik $k\ge 1$-rw léteznek $w_0,\dots ,w_k$ konfigurációk, melyekre $w_{i-1}⟹w_i(1\le i\le k),w_0=u$ és $w_k=v$

Elfogadott elv

Az $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ nemdeterminisztikus véges automata által elfogadott nyelv alatt az $L(A)=\{u\in {\Sigma }^{\ast }|q_{0}u⟹p\mathrm{valamely}{q}_0\in Q_0-\mathrm{ra}\acute{\mathrm{e}}\mathrm{s}p\in F-\mathrm{re}\}$ nyelvet értjük.

Véges automaták és reguláris nyelvek

Minden $A$ nemdeterminisztikus véges automatához meg tudunk adni egy 3-tíípusú $G$ grammatikát, úgí hogy $L(G)=L(A)$ teljesül.

Minden 3-típusú $G$ grammatikához meg tudunk adni egy $A$ nemdeterminisztikus véges automatát úgy, hogy $L(A)=L(G)$ teljesül.

Véges automata determinizálása

Minden $A=⟨Q,\Sigma ,\delta ,Q_0,F⟩$ nemdeterminisztikus véges automatákhoz megkonstruálható egy $A^{\prime }=⟨Q^{\prime },\Sigma ,{\delta }^{\prime },q_0^{\prime },F^{\prime }⟩$ determinisztikus véges automata úgy, hogy $L(A^{\prime })=L(A)$ teljesül.

$$\begin{gathered} Q^{\prime }:=\mathcal{P}(Q),q_0^{\prime }:=Q_0,F^{\prime }:=\{q^{\prime }\in Q^{\prime }|q^{\prime }\cap F\ne 0\}, \\ {\delta }^{\prime }(q^{\prime },a):={\cup }_{q\in q^{\prime }}\delta (q,a) \end{gathered}$$

Tehát mind a determinisztikus véges automaták, mind a nemdeterminisztikus véges automaták reguláris (${\mathcal{L}}_3$-beli) nyelveket leíró formális eszközök.

Források

• Diasor
• Felvétel