Maradéknyelv, myhill-nerode tétel, minimális-, redukált-, faktor automata,

• Maradéknyelv, myhill-nerode tétel, minimális-, redukált-, faktor automata,
  • Maradéknyelv
    • Nyelv adott szóra vonatkozó maradéknyelve
    • Automata adott állapotra vonatkozó maradéknyelve
  • Myhill Nerode tétel
    • Példa
  • Minimális automata
    • Minimális automata készítése
  • Redukált automata
  • Faktorautomata
  • Összegzés
  • Források

Maradéknyelv

Nyelv adott szóra vonatkozó maradéknyelve

Az $A$ és $A^{\prime }$ automaták ekvivalensek, ha $L(A)=L(A^{\prime })$.

Adott $L\subset {\Sigma }^{\ast }$ nyelv $p\in {\Sigma }^{\ast }$-ra szóra vonatkozó maradéknyelve $L_p$, ahol $L_p:=\{v\in {\Sigma }^{\ast }|pv\in L\}$

$L_p$ tehát azokat a szavakat tartalmazza, amelyekkel $p$-t jobbról kiegészítve $L$-beli szót kapunk.

Automata adott állapotra vonatkozó maradéknyelve

Legyen $A=⟨Q,\Sigma ,\delta ,q_0,F⟩$ véges determinisztikus automata.

Az L(A, q) \coloneqq {v \in \Sigma^* \vert\ qv \implies p, p \in F} nyelvet az $A$ automata $q\in Q$ állapotra vonatkozó maradék nyelvének nevezzük.

Alternatív definíció: $L(A,q):=\{v\in {\Sigma }^{\ast }|\delta (q,v)\in F\}$

Az $L(A,q)$ tehát azokat a szavakat tartalmazza, amelyek hatására az automata $q$-ból indítva végállapotba kerül.

Azaz, $L(A,q)$ lenne az elfogadott nyelv, ha a kezd˝oállapotot q-ra változtatnánk.

Tulajdonságai:

• $L(A,q{)}_w=L(A,\delta (q,w))(w\in {\Sigma }^{\ast })$
• $L(A,q_0)=L(A)$
• $ϵ\in L(A,q)⟺q\in F$

Myhill Nerode tétel

$$L\in {\mathcal{L}}_3⟺|\{L_p{\}}_{p\in {\Sigma }^{\ast }}|<\infty$$ ahol $\Sigma$ az $L$ nyelv ábécéje.

Példa

$L=\{a^n{b}^n|n\in \mathbb{N}\}$.

Ekkor $L_{a^k}=\{a^{n-k}{b}^n|n\ge k\}(k\in \mathbb{N})$

$b^i\in L_{a^k}⟺i=k$.

Tehát ez a végtelen sok maradéknyelv páronként különböző, így $L\notin {\mathcal{L}}_3$

ZH-n jól használható determinisztikus automata kreálására!

Minimális automata

Mivel $A_L^{MN}$ állapothalmaza $\{L_u{\}}_{u\in {\Sigma }^{\ast }}$, ezért az alábbi következményt kapjuk:

Az $A_L^{MN}$ automata állapotszáma kisebb vagy egyenlő, mint a tetszőleges, az $L$ nyelvhez adott véges, determinisztikus automata állapotszáma.

Az $A$ véges determinisztikus automata minimális állapotszámú, ha nincs olyan $A$-val ekvivalens $A^{\prime }$ véges determinisztikus automata, aminek kevesebb állapota van mint $A$-nak. Egy $L$ nyelv minimális automatája alatt egy $L$-et felismerő minimális véges determinisztikus automatát értünk.

Minimális automata készítése

Cél: Adott automatához minél kevesebb állapotú, vele ekvivalens, azaz az eredeti automata által felismert nyelvet elfogadó automatát megadni. Két lépésben fogjuk ezt elérni:

1. Összefüggővé alakítás:

Nyilván átmeneteikkel együtt elhagyhatók azok az állapotok, melyekbe nem tud eljutni az automata. Az átmenetdiagramon ez annak felel meg, hogy nincs a kezd˝oállapotból irányított út a csúcsba.

2. Ekvivalens állapotok összevonása:

Ha két állapotból pontosan ugyanazon szavak hatására kerül az automata végállapotba, akkor az elfogadás szempontjából mindegy, hogy a m˝uködés során a két állapotba kezül melyikbe került az automata. Ezek az állapotok nyilván összevonhatók.

Redukált automata

Legyenek $q,q^{\prime }\in Q$ állapotok. $q$-t és $q^{\prime }$-t nevezzük megkülönbözhetetlennek, ha $L(A,q)=L(A,q^{\prime })$

Egy véges determinisztikus automata redukált, ha nincsenek megkülönböztethetetlen állapotai.

Faktorautomata

Legyenek $A=⟨Q,\Sigma ,q_0,F⟩$ és $A^{\prime }=⟨Q^{\prime },\Sigma ,{\delta }^{\prime },q_0^{\prime },F^{\prime }⟩$ véges, determinisztikus automaták. A két automata izomorf, ha van olyan $\phi :Q\to Q^{\prime }$ bijekció, melyre

• $\phi (q_0)=q_0^{\prime }$
• $\phi (F):={\cup }_{q\in F}\{\phi (q)\}=F^{\prime }$
• $\forall q\in Q,t\in \Sigma$ esetén $\phi (\delta (q,t))={\delta }^{\phi (q),t}$

Tétel:

Az $A$ determinisztikus véges automata $A/$~ faktorautomatája

1. ekvivalens $A$-val
2. redukált
3. ha $A$ összefüggő, akkor izomorfia erejéig az egyetlen összefüggő, redukált $A$-val ekvivalens automata.

Összegzés

Tehát egy A véges determinisztikus automatához minimális automatát készíthetünk úgy, hogy

1. az elérhetetlen állapotait elhagyjuk ezzel előállítva egy $A$-val ekvivalens összefüggő automatát,
2. majd a már összefüggő automata $i\sim$ relációnak meghatározása segítségével a fenti módon algoritmikusan előállítunk egy redukált automatát.

• Az így kapott automata, összefüggő, redukált és ekvivalens $A$-val, ezért korábbi tételünk alapján izomorf az $A/\sim$-vel,
• mivel az $A_L^{MN}$ automata, ahol $L=L(A)$ szintén összefüggő, redukált (minden minimális automata redukált kell legyen) és $A$-val ekvivalens, ezért $A_L^{MN}$ ugyanezen tétel alapján szintén izomorf a faktorautomatával,
• mivel $A_L^{MN}$ minimális automata, ezért a faktorautomata és az $i\sim$ által algoritmikusan meghatározott automata is minimális automata, tételünk szerint ezek izomorfak egymással.

Források

• Diasor