Véges determinisztikus és nemdeterminisztikus automatak.Ekvivalenciajuk és kapcsolatuk a regularis nyelvekkel. Mealy- és Moore-automatak.

Véges determinisztikus és nemdeterminisztikus automaták.Ekvivalenciájuk és kapcsolatuk a reguláris nyelvekkel. Mealy- és Moore-automaták.

Véges automaták, mint felismerõk

Véges automaták: formális nyelvek ( ezen belül reguláris nyelvek ) felismerõinek viszonylag egyszerû matematikai modelljei.

Szemléltetés:

a₁ a_{2 ......} a_n-1 a_n

bemenõ szalag

(rajta egy szó a megengedett jelekbõl.)

Véges állapotú

vezérlõmû

(véges belsõ

állapottal)

Mûködés:

Az automata beolvas egy jelet balról jobbra a bemenõ szalagról. Ettõl és az aktuális belsõ állapotától függõen egy másik belsõ állapotba kerül. ( Determinisztikus automata esetén ez az állapot egyértelmûen meghatározott )

Indulás: kezdõ állapotból

Befejezés: ha kiürült a bemenõ szalag.

- Ha az automata befejezéskor végállapotba kerül felismerte a szót.

- Az automata által felismert nyelv: az automata által felismert szavak halmaza.

Példa: 3-mal osztható számok:

0,3,6,9

A₀

2,5,8 2,5,8

1,4,7

A₂

A₁

2,5,8

0,3,6,9 0,3,6,9

A₀: kezdõállapot

A₀: végállapot

Állapotok halmaza: A₀, A₁, A₂

Mûködés a = 1104 szó esetén:

1 1 0 4

A₀ A₁ A₂ A₂ A₀

Végállapotba került: a 3-mal osztható.

Automaták (determinisztikus) általános definíciója:

A = < A,T,a₀,F,d >

|A| < ¥ : belsõ állapotok halmaza

|T| < ¥ : bemenõ jelek halmaza (bemenõ abc)

a₀ A             : kezdõállapot

F A              : végállapotok halmaza

d: A×T A : átmenetfüggvény

Példa: (Elõbbi)

d(A₀,1)= A₁

d(A₁,1)= A₂

d(A₂,0)= A₂

d(A₂,4)= A₀

Kérdés: A₀ F

Definíció: d kiterjesztése:

d': A×T^* A

( Bemenõ jelek sorozatára mondja meg, hogy milyen állapotba jutunk. )

d'(a,e) = a a A

d'(a,pt) = d d'(a,p),t) , p T^*, t T

Megjegyzés: Tehát a,b A, w T^* esetén d'(a,w)=b azt jelenti, hogy az a állapotból az automata w szót elolvasva b állapotba jut.

Más definíció: q:= t₁ t₂ ... t_k t_i T

d' (a,q) = b Û c₀, c₁,..., c_k A c₀=a, c_k=b és d(c₀, t₁) = c₁, d(c₁, t₂)= c₂, ... ,d( c_k-1, t_k)= c_k .

Definíció: Az u T^* szót az A automata elfogadja, ha d'(a₀,u) F

Definíció: A által elfogadott nyelv:

L(A):=

Definíció: A ₁ ekvivalens A ₂-vel, ha L(A ₁ ) = L(A ₂ )

Példa: A₂ := < , , q₀ , , d >

d(q₀,a)= q₁ d(q₀,b)= s

d(q₁,a)= q₁ d(q₁,b)= q₂

d(q₂,a)= q₁ d(q₂,b)= q₂

d(s,a)= s d(s,b)= s

bemenõ jelek

Megadás:

1., Táblázattal: a b

q₀ q₁ s d

állapotok

q₁ q₁ q₂

q₂ q₁ q₂

s s s

2., Átmeneti diagrammal:

Ez egy irányított gráf, melyben állapot egy csúcsnak felel meg.

p q él létezik (p,q A ) , ha a T d(q,a)=q .

Ekkor p q élre ráírjuk a-t.

( p q élet "színezzük" a-val. )

Végállapot jele:

Kezdõállapot jele: bemutató nyíl

a

q₀ a q₁ q₂

a b a b b

s

b

Mely szavakat fogadja el ?

- az üres szót,

- a-val kezdõdõ és a-val végzõdõ szavakat.

Ekvivalens automata:

a

a

q₀ a q₁ q₂

b b

Példa: A:= < , , a₀ , , d >

a X_a a

d a b a,b,c,d

d            b c a b

a₀ X_b s

d

c b c

d X_c

c

Mely szavakat fogadja el ?

Melyekben a d-n kívül kettõ, vagy több egyforma betû nem szerepelhet egymás mellett.

d a b c d

a₀ X_a X_b X_c a₀

X_a s X_b X_c a₀

X_b X_a s X_c a₀

X_c X_a X_b s a₀

s s s s s

Példa: A:= < , , q₀ , , d >

d a b a

q₀ b

q₀ q₁ q₂ a b

q₀                                        q₀

q₁ q₀ q₂ a

q₂ q₁ q₀ b

Mely szavakat fogadja el ?

Ahol a szó végén nem áll páros számú azonos betû.

Lemma (Bar-Hillel)

Legyen adott L nyelv, melyet egy determinisztikus véges automata felismer.

Ekkor n N ha a L szóra d(a ³ n , akkor a elõállítható a=uvw alakban, ahol d(uv) n , d(v) ³ 1 és i= 0,1,2,.. term. számra: uvⁱw L.

Példa:

u₁ := abc ca ab u₂ := abc caca ab

u v w u v² w

Megjegyzés: n konstansnak választható az L-t felismerõ automata belsõ állapotainak száma.

Köv.1.: Legyen A determinisztikus automata és belsõ állapotainak száma: n.

Az A által felismert nyelv nem üres Û n-nél rövidebb szó, melyet A felismer.

Köv.2.: Van olyan algoritmus, mely eldönti egy véges determinisztikus automatáról, hogy az általa felismert nyelv üres-e.

Köv.3.: Van olyan környezetfüggetlen nyelv, amelyhez ezt a nyelvet felismerõ véges             determinisztikus automata.

Példa: G₁ = < , , s , >

G₁ környezetfüggetlen

L(G₁) =

Állítás: A véges determinisztikus automata L(A) = L(G₁)

Bizonyítás: Indirekt

T.f.h. ilyen A. Ekkor a Bar-Hillel-lemma alapján megfelelõen nagy m-re:

a^m b^m = uvw , ahol d(v) ³ 1 és tetszõleges i= 0,1,2,...-re uvⁱw L(G₁).

De: - ha v a és b betût is tartalmaz, akkor uv²w L(G₁) , mert a betûk sorrendje megbomlik.

(pl.: aaa abb bb aaa abbabb bb )

u v w u v² w

- ha v csak a betût tartalmaz, akkor uw L(G₁) (i=0) , mert a szóban kevesebb a van, mint b.

- ha v csak b betût tartalmaz, hasonlóan.

Nemdeterminisztikus véges

automaták

Különbség: Egy belsõ állapotból több olyan él is indulhat, mely azonos betûvel van "színezve".

Szó felismerése: (ugyan az, mint véges det. automatáknál)

u szót az automata felismeri, ha a gráfban irányított út kezdõállapotból indul,             végállapotba jut és az élek rendre u betûivel vannak színezve.

Pontos definíció: ( nemdet. aut. )

A = < A , T , a₀ , F , d >

A: belsõ állapotok véges, nem üres halmaza

T: bemenõ abc

a₀: kezdõállapot (a₀ A )

F A végállapotok halmaza

d: A x T 2^A , azaz d(q,a)= , ahol a T és q, p₁, ... p_l A

Mûködés:

! u= t₁ t₂ ... t_k T^* szó.

Az automata pillanatnyi állapota : q

1. lépés: d(q,t₁) =

2. lépés: lehetséges állapotok halmaza:

d(p₁, t₂)È d(p₂, t₂)È È d(p_l, t₂)

....

Végigolvassuk az u szót és ha végül a lehetséges állapotok halmazában van végállapot, akkor A felismerte u-t.

Definíció: d kibõvítése szóra:

d' : A x T^* 2^A

1., d'(q,e q A

2., d'(q,wa)= q A , w T^* , a T

Definíció: Az automata által felismert nyelv:

L(A):=

Példa:

d 0 1 1

0 q₁ 0

q₀ 0

q₀                                        1

q₁ 0 0

q₂ 0 q₂ 0

Mûködése a 0101 szóra:

1., d(q₀,0) =

2., d'(q₀,01) = d(q_1, 1)Èd(q_2, 1) = 0 È

3., d'(q₀,010) = d(q_1, 0) =

4., d'(q₀,0101) =d(q_0, 1)Èd(q_1, 1) = È

Mivel q₀ Ï F, a szót az automata nem fogadja el.

Definíció: G_A :=

G_ND :=

Tétel: G_A = G_ND

Bizonyítás:

G_A G_ND

Triviális, hiszen determinisztikus automata felfogható speciális nemdeterminisztikus automataként.

G_ND G_A

Konstruktív bizonyítás:

Legyen A:= < A,T,a₀,F,d > véges, nemdeterminisztikus automata.

Ehhez konstruálunk egy vele ekvivalens véges determinisztikus automatát.

Legyen A' := < Q,T,t₀,F',d' > véges determinisztikus automata a következõ:

q := 2^A ( A részhalmazai )

T uaz.

t₀ :=

F' :=

d d'(H,a)=H' , ha H,H' Q, a T

H = p_i A és H' r_i A és = d(p₁,a)È d(p₂,a)È È d(p_l,a)

Azaz d'(H,a) := d(p_i,a)

Ekkor belátható ( u hosszára vonatkozó teljes indukció és d d' T^*-ra vonatkoztatott kiterjesztése alapján), hogy:

p_i A , H 2^A , u T^* esetén.

Belátjuk, hogy egy u T^* szót pontosan akkor fogadja el az A nemdeterminisztikus automata, amikor A' determinisztikus automata elfogadja.

u L(A) Û d(a₀,u) F ¹ Û

|| d' def. szerint

d'(,u)

|| t₀ def. szerint

d'(t₀,u)

Û d'(t₀,u) F ¹ Û d'(t₀,u) F' Û u L (A')

F' def. szerint

Példa :

A₂ := < , ,q₀, , d > véges nemdet. aut.

d a b a a

q₀ q₀ b q₁ a

q₁ 0 b

A₂': Q = 0, , ,

¯ ¯ ¯ ¯

t[0] t[q₀] t[q₁] t[q₀ ,q₁]

T =

t₀ = B t[q₀]

F' = ¹

A₂' = < ,,t[q₀] , , d' >

d' a b

t[0] t[0] t[0]

t[q₀] d(q₀,a)= t[q₀]                d(q₀,b)= t[q₀,q₁]

t[q₁] d(q₁,a)= t[q₀,q₁]                               d(q₁,b)=0 t[0]

t[q₀ ,q₁] d(q₀,a)È d(q₁,a)=È t[q₀,q₁] d(q₀,b)Èd(q₁,b) =

È t[q₀,q₁ ]

a b a

t[0] t[q₀] t[q₀] t[q₀,q₁]

a b

a

b b

Egyszerûsítve:

t[q₀] t[q₀,q₁ ]

b a,b

a

Minden szót felismer, amely tartalmaz b betût.

Példa: 2., A₃ := < , , A, , d >

d 0 1

0 0

A A B

1

B

0 1

A₃' < , , t[A], , d'>

d 0 1

t[0] t[0] t[0]

t[A] d(A,0)= t[A,B] d(A,1)= t[B]

t[B] d(B,0)= t[B] d(B,1)= t[A]

t[A,B]              d(A,0)Èd(B,0)= d(A,1)Èd(B,1)=

È È

t[A,B] t[A,B]

t[0] t[A] t[B] t[A,B]

elhagyható

Tétel: G₃ = G_A, azaz A nemdeterminisztikus (ill.: a determinisztikus) véges automaták osztálya megegyezik a reguláris nyelvek osztályával.

Bizonyítás: 1. irány: G₃ G_ND(=G_A) , azaz belátjuk, hogy ha L reguláris nyelv, akkor található véges nemdet. automata felismeri L nyelvet.

Legyen L reguláris nyelv, melyet a G = < T,N,S,P > nyelvtan generál.

Az A nemdet. automata definíciója:

A = < A,T,a₀,F,d >, ahol

- A := NÈ , E Ï TÈN

- a₀ := S

- d(B,a)= , B,D_i A , a T ha P-ben szerepel az alábbi szabály: B aD_i

E , ha P-ben szerepel a B a szabály.

- d(E,a)=0 a T

- F=, ha P-ben nem szerepel az S e szabály, F= különben.

Könnyen megfontolható, hogy ez az automata L(G)-t ismeri fel.

Példa: w := a_i1 ... a_ik L.

Ekkor P-ben szerepelnek az alábbi szabályok:

S a_i1A₁ ; A₁ a_i1A₂ ; ... ; A_k-2 a_i(k-1)A_k-1 ; A_k-1 a_ik

Tehát az automata definíciója szerint:

A₁ d(S,a_i1), A₂ d(A₁,a_i2), ... , A_k-1 d(A_k-2,a_i(k-1))

E d(A_k-1,a_ik) Þ E d(a,a_i1 ... a_ik) Þ E d(S,w), azaz w L(A), mivel E végállapot.

Példa G:=< ,S,P >

P : S aS bS aA

A bB

B a

A hozzá tartozó automata: A < ,S, d >

b

S a A b B a E

a

L(G) = L(A) = w w w aba

Bizonyítás (folytatás)

G_A G ₃

Azaz minden L nyelvhez, melyet egy véges det. automata felismer, minden olyan reguláris grammatika, mely az L nyelvet generálja.

Bizonyítás

A := < A,T,a₀,F,d > véges det. automata, mely L-t felismeri. Ehhez konstruáljuk a következõ G:= <T,N,S,P> reguláris grammatikát, ahol:

T := T

N := A

S := a₀

P : - minden d(q,a) =p -hez tartalmaz egy q ap szabályt. (q,p A, A T)

- Ha d(q,a)=p esetén p F, akkor tartalmaz még egy q a szabályt is.

Állítás Ekkor L(G) = L(A) - e

Ui. 1. w = ai1.....aik L(A)

Ekkor az állapotok sorozata: d(a₀,a₁)=qi, d(q_i1,a_i2)=q_i2, ......, d(q_ik-1,a_ik)=q_ik F

G szabályainak megadása miatt léteznek az alábbi szabályok: q₀ a_i1q_i1, ..... , q_ik-1 a_ik

Tehát w levezethetõ G-ben.

A levezetés: q₀ ¾ a_i1q_i1 ¾ a_i1a_i2q_i2 ¾ ... ¾ a_i1...a_ik-1q_ik-1 ¾ a_i1...a_ik=w

Azaz w L(G).

2. Visszafelé hasonlóan okoskodva: w L(G) Þ w L(A)

Megjegyzés

Ha e L(A), akkor az elõzõvel ekvivalens olyan grammatikát kell készíteni, ahol a₀' az új kezdõ szimbólum, mely nem szerepel szabály jobb oldalán és az új szabály: a₀' e

Példa A = < ,q₀, d>

a a

q₀ a q₁ b q₂

b

b

Milyen szavakat fogad el ? Szó végén nem állhat páros számú azonos betû.

A grammatika, mely ezt a nyelvet generálja: G:= < ,q₀,P >

P : q₀ aq₁ q₀ a

q₀ bq₂ q₀ b

q₁ aq₀

q₁ bq₂ q₁ b

q₂ aq₁ q₁ a

q₂ bq₀

Véges automaták, mint formális nyelvek átalakítói

a₁ a₂ ............................. a_k-1 a_k bemenõ szalag

olvasófej

véges állapotú

vezérlõmû

írófej

kimenõ szalag                           b₁ b₂ ............................. b_k-1 b_k

Mûködés:

- kezdõállapotból indul

- elolvas egy jelet a bemenõ szalagról (balról jobbra)

- új belsõ állapotba kerül és leír egy jelet a kimenõ szalagra (balról jobbra)

Befejezõdés:

- nincs definiált következõ lépés

- elolvasta a bemenõ szót

Mealy - automata

(A kimenõ jel függ a belsõ állapottól és a beolvasott jeltõl egyaránt.)

M: = <A, V, W, d l, q0 >, ahol: - A: belsõ állapotok véges, nem üres halmaz

- V: bemenõ ábécé (V ¹ Æ, véges halmaz)

- W: kimenõ ábécé (W ¹ Æ, véges halmaz)

- d átmenetfüggvény d:A V A

- l kimeneti függvény l: A V w

- q₀: kezdõállapot q₀ A.

Mûködés: a₁a₂......a_k bemenõ szóra

1. lépés: q₁:= d(q₀,a₁) új belsõ állapot meghatározása

b₁:=l(q₀,a₁) elsõ kimenõ jel meghatározása

2. lépés: q₂:= d(q₁,a₂)

b₂:=l(q₁,a₂)

:

:

Eredmény:

b₁b₂.....b_k = l(q₀a₁)l(q₁,a₂).......l(q_k-1,a_k) W* szó

Definíció: M automata az a = a₁....a_k bemeneti szót b = b₁....b_k kimeneti szóvá fordította le. Jelölése: b=M(a

Definíció: Az M automata az L₁ formális nyelvet L₂-vé alakítja (fordítja le), ha

L₂ =

Megadás: - táblázattal

- gráffal

Példa M₁:=< d l, q₀>

d(q₀,a)= q₀ l(q₀,a)=0

d(q₀,b)= q₁ l(q₀,b)=1

d(q₁,a)= q₁ l(q₁,a)=1

d(q₁,b)= q₀ l(q₁,b)=0

Táblázattal:

Gráffal: b/0

q₀ q₁

b/1

a/0 a/1

Mûködés:

- kimeneti szó n. betûje 1, ha a bemeneti szóban az elsõ n betû között páratlan b szerepel

- 0 különben

Példa baabbab

Moore - automata

(A kimeneti jel csak a belsõ állapottól függ.)

N:=< A, V, W, d l, q₀>, ahol: - A: belsõ állapotok véges, nem üres halmaza

- V: bemenõ ábécé

- W: kimenõ ábécé

- d átmenetfüggvény d:A V A

- l kimeneti függvény l: A W

- q_0: kezdõállapot q₀ A

Mûködés: a₁.... a_k V* bemeneti szóra

0., b₀:=l(q₀) 1. kimeneti jel meghatározása

1., q₁:=d(q₀,a₁) új belsõ állapot meghatározása

b1:=l(q₁) 2. kimeneti jel meghatározása

:

:
k., q_k :=d(q_k-1,a_k)

b_k :=l(q_k)

Megjegyzés: Kimeneti szóban egy betûvel több van, mint a bemeneti szóban.

Jelölés: N(w w bemenõ szóból átalakított kimeneti szó.

Megadás: - táblázattal

- gráffal

Példa N₁:=< d l, q₀>

d(q₀,a) = q₁

d(q₀,b) = q₂ l(q₀) = 0

d(q₁,a) = q₁

d(q₁,b) = q₂ l(q₁) = 1

d(q₂,a) = q₁

d(q₂,b) = q₂ l(q₂) = 0

Táblázattal:

Gráffal: a

a q₁,1

q₀,0 b

b a

q₂,0

b

Mûködés:

- Kimeneti szó elsõ betûje 0

- Többi betûnél: bemenõ a-t egyesre, b-t nullára cseréljük.

Definíció M:=<A, V, W, d l, q₀> Mealy - automata

N:=<A', V, W, d l', q₀'> Moore - automata

M és N ekvivalensek, ha minden w bemeneti szóra: bM(w) = N(w), ahol b:=l '(q₀').

Tétel Tetszõleges Mealy-automatához létezik vele ekvivalens Moore-automata.

Tétel Tetszõleges Moore-automatához létezik vele ekvivalens Mealy-automata.

Tétel L V* reguláris nyelv. M Mealy-automata, V bemenõ ábécével. Ekkor M(L) reguláris