Jeziki regularnih izrazov so natanko regularni jeziki

Iz MaFiRaWiki

Izrek: jeziki regularnih izrazov so natanko regularni jeziki

(\Longrightarrow )

Podan imamo nek poljuben regularni izraz in zanj moramo sestaviti končni avtomat, ki ga razpoznava. Zadošča, če najdemo nek nedeterministični končni avtomat (NKA), saj se vsak NKA da prevesti na ekvivalentni deterministični končni avtomat (DKA). Pokazali bomo, da za vsak operator v regularnem izrazu obstaja nek delni NKA (še brez končnih stanj), ki razpoznava tisti del regularnega izraza ki ga določa ta operator. To naredimo takole:

- za eno črko a v regularnem izrazu uporabimo to konstrukcijo


Slika:Slika_1.jpg


- za stik dveh črk e1e2


Slika:Slika_2.jpg


- za ekskluzivni ali med e1 + e2 (včasih se piše tudi e1 | e2)


Slika:Slika_3.jpg


- za e? (to je enakovredno kot (e + ε))


Slika:Slika_4.jpg


- e* bi zapisali kot


Slika:Slika_5.jpg


- in e+ kot


Slika:Slika_6.jpg


Prednost imajo tiste konstrukcije ki pripadajo operatorjem, ki imajo prednost v regularnem izrazu. Same po sebi pa še niso NKA, moramo jih še malo obdelati. Stanj bo končno mnogo, največ toliko kolikor je dolg podani regularni izraz (eno stanje za vsak znak oz. operator, to pa je končno mnogo). Na koncu dodamo še končno stanje in nanj pokažemo z vsemi puščicami, ki do tedaj kažejo v prazno. To kar smo dobili pa je ravno iskani NKA, ki (po konstrukciji) razpoznava jezik nad podanim regularnim izrazom. Konkreten zgled je malo nižje.


(\Longleftarrow )

Sedaj imamo podan končni avtomat M = (Q,E,q0,δ,A), ki razpoznava jezik L. Dokazati pa želimo, da obstaja tak regularni izraz (s črkami iz E), da bo ravno ustrezal jeziku L. Ta implikacija je nekoliko težja kot prejšnja, pomagali pa si bomo z indukcijo. Najprej definiramo:

L(p,q) = \{ x \in E^* ; \delta ^*(p,x) = q\}

L(p,q) je množica vseh nizov, ki končni avtomat M iz stanja p vodijo do stanja q. Če pokažemo, da za vsak jezik L(p,q) obstaja regularni izraz, potem obstaja tudi za jezik L obstaja nek regularni izraz. To res drži, saj M razpoznava unijo jezikov L(q0,q) (unija po vseh q iz A), ustrezen regularni izraz pa bi bil z uporabo operatorja + med vsemi L(q0,q. Indukcijsko pa bomo pokazali, da je L(p,q) regularen jezik. Najprej vsa stanja Q oštevilčimo z 1 do N. Nato definirajmo:

- pot skozi stanje s, ki se začne v p in konča v q, je tak x \in E*, če lahko zapišemo x=yz (y,z različna od 0) in pri tem velja: δ * (p,y) = s in δ * (s,z) = q

- za vsak J večji ali enak 0 je L(p,q,J) = {x iz E* ; x ustreza poti iz p v q in ne gre skozi stanje, ki bi bilo oštevilčeno z več kot J}

Opazimo, da je L(p,q,N) = L(p,q), saj je N najvišje oštevilčeno stanje v M. Če torej dokažemo, da je za vsak J med 0 in N L(p,q,J) regularen, potem je tudi L(p,q) regularen. Najprej pokažemo, da je L(p,q,0) regularen. To je množica vseh poti, ki grejo iz p v q, brez da bi šli skozi katerokoli drugo stanje. To je možno le v primeru p=q, to ustreza {ε}. Seveda je L(p,q,0) podmnožica jezika E \cup {ε}. Sedaj pokažemo, da če je L(p,q,K) regularen, potem je L(p,q,K+1) regularen (za vsak p,q med 1 in N ter vsak K med 0 in N-1). Opazujemo L(p,q,K+1): to je pot iz p v q, ki ne gre skozi stanje, ki je oštevilčeno višje od K+1. To se lahko zgodi na dva načina:

- pot sploh ne gre skozi stanje K+1 (v tem primeru je ta pot x tudi iz L(p,q,K) ki je regularen)

- pot gre iz p v K+1, se morda še nekajkrat vrne v K+1 in gre potem v q

Slednjo pot lahko potem zapišemo takole: x = x1yx2. Pri so x1,y in x2 izbrani tako da velja:

δ * (p,x1) = K + 1

δ * (K + 1,y) = K + 1

δ * (K + 1,x2) = q

Če vključimo morebitno vračanje poti iz K+1 nazaj v K+1 v y, potem velja, da je x1 iz L(p,K+1,K) in x2 iz L(K+1,q,K) (to zgolj pomeni, da potem v tem času ne gre skozi nobeno drugo stanje, ki je višje od K). Dalje, če je y različen od ε ga lahko zapišemo kot y=y_1y_2\ldots y_l. Pri tem je yi le eno vračanje poti, torej y_i \inL(K+1,K+1,K). Iz tega sledi, da je y iz L(K+1,K+1,K)*. Potem pa lahko tudi zapišemo:

L(p,q,K+1) = L(p,q,K)  \bigcup  L(p,K+1,K)L(K+1,K+1,K)^*L(K+1,q,K)

To pa dokazuje, da je L(p,q,K+1) regularen.

Zgled

Podan je regularni izraz (abab)|(abbb) (oz. (abab) + (abbb)). Zanj bomo konstruirali končni avtomat, ki ga razpoznava (kot v izreku). Ker ima operator | prednost pred stikom najprej naredimo skico zanj. Nato za vsako črko posebej dodajamo pripadajoča stanja (kot v izreku) na ustreznih mestih. Za (abab) zgoraj in za (abbb) spodaj. Nato dodamo še končno stanje in z vsemi praznimi puščicami pokažemo nanj. Tako dobljeni NKA izgleda takole:


Slika:Slika_7.jpg

Osebna orodja