Loading [MathJax]/jax/output/HTML-CSS/jax.js

Wyrażenia regularne. Automat minimalny

W tym wykładzie określimy rodzinę języków regularnych wolnego monoidu A oraz pewien formalny opis tych języków zwany wyrażeniami regularnymi.
Dla języka rozpoznawalnego L wprowadzimy pojęcie automatu minimalnego rozpoznającego L i prawej kongruencji syntaktycznej, która odgrywa istotną rolę w problemach związanych z automatem minimalnym.

Wyrażenia regularne

Definicja 1.1

Niech A będzie skończonym alfabetem. Rodzina REG(A) języków regularnych nad alfabetem A to najmniejsza, w sensie inkluzji, rodzina R języków zawartych w A taka, że:

(1) R, aA{a}R
(2) jeśli X,YR, to XY,XYR
(3) jeśli XR, to X=n=0XnR

Wprost z definicji wynika, że {1}=R oraz że dla dowolnego języka regularnego zachodzi równość XR jest

X+=n=1Xn=XXR.

Wprowadzona w ten sposób definicja rodziny języków regularnych wymaga uzasadnienia faktu, iż definiowany obiekt, definiowana rodzina, istnieje. Zauważmy więc, że warunki 1-3 definicji 1.1 (patrz definicja 1.1.) spełnia na przykład rodzina P(A) wszystkich podzbiorów A, a zatem klasa takich rodzin nie jest pusta. Ponadto łatwo możemy stwierdzić, że jeśli rodziny R1,R2 spełniają warunki 1-3 powyższej definicji, to rodzina R1R2 również spełnia te warunki. Stąd możemy wyprowadzić wniosek, że najmniejsza rodzina spełniającą te warunki, to przecięcie

REG(A)=R,

po wszystkich rodzinach R spełniających warunki 1-3 definicji 1.1. (patrz definicja 1.1.)

Zauważmy, że w świetle powyższej definicji fakt, że XREG(A) oznacza, że X można uzyskać z liter alfabetu i zbioru pustego poprzez zastosowanie wobec tych "elementarnych klocków" skończonej liczby działań: sumy, katenacji i gwiazdkowania. Na odwrót, każdy zbiór otrzymany w ten sposób jest elementem rodziny REG(A). Ta obserwacja prowadzi do pojęcia wyrażeń regularnych, formalnego zapisu języków regularnych.

Definicja 1.2

Niech A będzie alfabetem, a zbiór {+,,,(,)} alfabetem rozłącznym z A. Słowo α(A{+,,,(,)}) jest wyrażeniem regularnym nad alfabetem A wtedy i tylko wtedy, jeśli:

(1) α=
(2) α=aA(α jest literą)
(3) α jest w postaci (β+γ),(βγ),γ, gdzie β,γsą wyrażeniami regularnymi nad alfabetem A.

Przyjmujemy oznaczenia:

=1 oraz αα=α+.

Rodzinę wyrażeń regularnych nad alfabetem A oznaczamy symbolem WR. Łatwo zauważyć związek pomiędzy wyrażeniami regularnymi oraz wprowadzoną wcześniej rodziną REG(A), regularnych języków wolnego monoidu A. Związek ten ustala poniższa definicja.

Definicja 1.3

Wartościowaniem wyrażenia regularnego nazywamy odwzorowanie

||:WRP(A)

określone następująco:

(1) ∣=
(2) a∣={a}
(3) (α+β)∣=∣αβ

           (αβ)∣=∣αβ

           α∣=∣α

Odwzorowanie określające wartość wyrażenia regularnego nie jest, jak można zauważyć, iniekcją. Oznacza to, że różne wyrażenia regularne mogą mieć tę samą wartość, czyli określać ten sam język regularny. Prostym przykładem tego faktu są wyrażenia regularne a oraz (a). Zwróćmy uwagę na wartość wyrażenia regularnego oznaczonego symbolem 1.

Jest mianowicie
1∣=∣∣=∣=={1}

Wprowadza się następującą relację równoważności w rodzinie wyrażeń regularnych.

Definicja 1.4

Wyrażenia regularne α,β nazywamy równoważnymi i oznaczamy α=β, jeśli α∣=∣β.

Problem równoważności wyrażeń regularnych jest rozstrzygalny i jest PSPACE-zupełny. Wrócimy do tego problemu w kolejnych wykładach.

Oto przykłady równoważnych wyrażeń regularnych

α1+α2=α2+α1(α1+α2)+α3=α1+(α2+α3)(α1α2)α3=α1(α2α3)(α1+α2)α3=α1α3+α2α3α1(α2+α3)=α1α2+α1α3(α)=α(α1α2)=(α1+α2)(α++1)=α

gdzie α,α1,α2,α3WR.

Wprost z definicji wyrażenia regularnego wynika następujaca równoważność:

Fakt 1.1

LREG(A)L=∣α dla pewnego αWR.

Wyrażenia regularne dają bardzo wygodne narzędzie zapisu języków należących do rodziny REG(A). Np. język nad alfabetem {a,b} złożony ze wszystkich słów zaczynających się lub kończących na literę a zapisujemy jako a(a+b)+(a+b)a.
Z kolei wyrażenie regularne a+b+ oznacza język L={anbm:n,m1}. Dla dalszego uproszczenia zapisu przyjmiemy w naszym wykładzie następującą umowę. Jeśli język L jest wartością wyrażenia regularnego α, czyli L=∣α, to będziemy zapisywać ten fakt jako L=α. Będziemy zatem mówić w dalszym ciągu wykładu o języku α. Z tych samych powodów, dla dowolnego alfabetu A={a1,.....,an} będziemy używać zapisu A w miejsce a1+.....+an.

Zauważmy na koniec rozważań o wyrażeniach regularnych, że dość prosty w zapisie język L={anbn:n1} nie należy do rodziny REG(A) i nie można go zapisać przy pomocy wyrażeń regularnych.

Kończąc ten fragment wykładu poświęcony wyrażeniom regularnym warto wspomnieć o problemie "star height", czyli głębokości zagnieżdżenia gwiazdki w wyrażeniu regularnym. Mając wyrażenia regularne α,α1,α2WR głębokość zagnieżdżenia gwiazdki definiuje się jako liczbę sh(α) równą 0, gdy α jest literą z alfabetu lub zbiorem pustym, równą max{i,j}, gdy α=α1α2 lub α=α1α2 i sh(α1)=i, sh(α2)=j oraz równą i+1 dla α=(α1). Głębokość zagnieżdżenia gwiazdki dla języka regularnego L określa się jako najmniejszą liczbę sh(L)=sh(α), gdzie α jest wyrażeniem regularnym reprezentującym język L. Głębokość zagnieżdżenia gwiazdki jest więc jakby miarą złożoności pętli występujących w automacie rozpoznającym język L. Ustalono, że dla alfabetu złożonego z jednej litery głębokość zagnieżdżenia gwiazdki jest równa co najwyżej 1 oraz że dla alfabetu o co najmniej dwóch literach dla dowolnej liczby kN można wskazać język regularny L taki, że sh(L)=k. Problemem otwartym pozostaje określenie algorytmu określającego głębokość zagnieżdżenia gwiazdki dla dowolnego języka w klasie języków regularnych.

Prawa kongruencja syntaktyczna i kongruencja syntaktyczna

Opis języka regularnego za pomocą wyrażeń regularnych jest bardzo wygodny, ale nie jedyny. W kolejnych wykładach będziemy wprowadzać inne reprezentacje języków regularnych, takie jak automaty czy gramatyki. Pojęcia, które wprowadzimy teraz, są również narzędziami dla opisu i badań własności języków regularnych. W szczególności służą do konstrukcji możliwie najprostszego automatu rozpoznającego dany język regularny, zwanego automatem minimalnym.

Definicja 2.1.

Niech LA będzie dowolnym językiem. W monoidzie A wprowadzamy następujące dwie relacje:

(1) prawą kongruencję syntaktyczną PrL, przyjmując
dla dowolnych słów u,vA
uPrLv wtedy i tylko wtedy, gdy spełniony jest warunek
wAuwLvwL,
(2) kongruencję syntaktyczną PL, przyjmując
dla dowolnych u,vA
uPLv wtedy i tylko wtedy, gdy spełniony jest warunek
w1,w2Aw1uw2Lw1vw2L.

Łatwo stwierdzić, że nazwy wprowadzonych relacji pokrywają się z ich własnościami, to znaczy relacja PrL jest rzeczywiście prawą kongruencją, a PL kongruencją.

Przykład 2.1.

Niech A={a,b} będzie alfabetem.

(1)Dla języka L=a+b+ relacja
(a) PrL ma 4 klasy równoważności: L,AbaA+b+,a+,1,
(b) PL ma 5 klas równoważności: L,AbaA,b+,a+,1.
(2) Dla języka L={anbn:n1} obie relacje mają nieskończony indeks
(a) dla PrL klasami równoważności są zbiory
Li={anbni:ni,n1} dla iN0, Ai=0Li.
(b) dla PL klasami równoważności są zbiory
Li={anbni:ni,n1} dla iN0,
Li={anibn:ni,n1} dla iN,
A[i=1(LiLi)L0].

Udowodnimy następujące własności relacji PrL oraz PL.

Twierdzenie 2.1.

Prawa kongruencja syntaktyczna PrL jest największą w sensie inkluzji spośród wszystkich

prawych kongruencji ρ takich, że
L=wL[w]ρ

Kongruencja syntaktyczna PL jest największą w sensie inkluzji spośród wszystkich

kongruencji ρ takich, że
L=wL[w]ρ

Dowód

Dowód przeprowadzimy dla prawej kongruencji syntaktycznej. Uzasadnienie tezy dla kongruencji PL przebiega podobnie. Niech ρ będzie dowolną prawą kongruencją spełniającą założenia i niech uρv. Zatem dla każdego wA jest

uwρvw(uwLvwL)uPrLv.

W konsekwencji ρPrL. W szczególności więc dla dowolnego uA ma miejsce inkluzja [u]ρ[u]PrL. Zatem LwL[w]PrL. Aby udowodnić inkluzję w stronę przeciwną ustalmy dowolne uL i niech v[u]PrL. Przyjmując w=1 w definicji (patrz definicja 2.1.) relacji PrL otrzymamy równoważność uLvL. A więc vL.

Wniosek 2.1.

Jeśli język L jest regularny, to relacja PrL jest największą w sensie inkluzji spośród wszystkich prawych kongruencji takich, że język L jest sumą jej pewnych klas równoważności, a relacja PL jest największą w sensie inkluzji spośród wszystkich kongruencji spełniających analogiczny warunek. Obie relacje mają skończony indeks, czyli dzielą wolny monoid A na skończoną liczbę klas równoważności.

Pojęcie, które wprowadzimy teraz - monoid syntaktyczny języka - wiąże teorię języków formalnych, a w szczególności teorię języków rozpoznawalnych, z teorią półgrup. Związek ten stanowi podstawę dla bardziej zaawansowanych problemów teorii języków i automatów wykraczających poza ramy tego wykładu.


Definicja 2.2.

Niech LA będzie dowolnym językiem. Monoidem syntaktycznym języka L nazywamy strukturę ilorazową

M(L)=A/PL.

Dualnie, tworząc iloraz S(L)=A+/PL, wprowadza się pojęcie półgrupy syntaktycznej języka L. Oba wprowadzone tu pojęcia zilustrowane będą w trakcie dalszych rozważań.

Automat minimalny

Określenie języka rozpoznawalnego postuluje istnienie automatu o skończonej liczbie stanów, działającego w odpowiedni sposób. Należałoby zatem wskazać algorytm budowy takiego automatu dla języka rozpoznawalnego. Oczywiście interesuje nas algorytm prowadzący do automatu o możliwie najprostszej postaci. Najprostsza postać, w tym kontekście, oznacza najmniejszą liczbę stanów.

Definicja 3.1.

Automat A=(S,A,f,s0,T) rozpoznający język L nazywamy automatem minimalnym, jeśli posiada najmniejszą liczbę stanów spośród wszystkich automatów rozpoznających język L.

Kwestią istnienia takiego automatu minimalnego zajmujemy się teraz. W kolejnym wykładzie przedstawimy algorytmy konstrukcji automatu minimalnego.

W poniższym twierdzeniu występuje automat ilorazowy APrL określony przez prawą kongruencję PrL.


Twierdzenie 3.1.

Dla dowolnego automatu A=(S,A,f,s0,T) rozpoznającego język LA istnieje jedyny epimorfizm φ:AAPrL taki, że φ(s0)=[1]PrL.

Dowód

Prawa kongruencja automatowa A ma skończony indeks i L=uL[u]A. Zatem z twierdzenia (patrz Twierdzenie 2.1.) wynika, że

APrL=APrL.

Istnienie epimorfizmu φ wynika z twierdzenia 1.1, wykład 3. Epimorfizm ten określony jest dla dowolnego stanu sS równością φ(s)=f([1]PrL,w)=[w]PrL, gdzie w jest słowem takim, że f(s0,w)=s.

Jest to jedyny epimorfizm spełniający warunki tezy dowodzonego twierdzenia. Dla każdego epimorfizmu ψ takiego, że ψ:AAPrL i ψ(s0)=[1]PrL mamy
sS
ψ(s)=ψ(f(so,w))=f(ψ(s0),w)=f([1]PrL,w)=[w]PrL,

gdzie f(s0,w)=s. Tak więc ψ=φ.

Zatem udowodnione twierdzenie zapewnia nas o istnieniu automatu minimalnego, co formułujemy w następującym wniosku.

Wniosek 3.1.

Niech LA będzie dowolnym językiem. Automat

APrL=(A/PrL,A,f,[1]PrL,T),

gdzie T={[w]PrL:wL}, jest automatem minimalnym rozpoznającym język L. Oznaczać go będziemy symbolem AL.

Rysunek 1

Następne twierdzenie charakteryzuje monoid przejść automatu minimalnego i podaje kolejny warunek równoważny na to, żeby język L był rozpoznawany przez automat.

Twierdzenie 3.2.

Niech LA będzie dowolnym językiem.

1. Dla dowolnego języka LREC(A) monoid przejść automatu minimalnego AL jest izomorficzny z monoidem syntaktycznym M(L) języka L, czyli

M(AL)M(L).

2. (tw. J.Myhill'a) Język LA jest rozpoznawalny wtedy i tylko wtedy, gdy M(L) jest monoidem skończonym.

Dowód

Dla dowodu punktu 1 wykażemy, że

PL=KerτAL,

gdzie zgodnie z definicją dla dowolnych w,uA

τAL(w)([u]PrL)=f([u]PrL,w)=[uw]PrL.
(u,w)KerτALvAτAL(u)([v]PrL)=τAL(w)([v]PrL)[vu]PrL=[vw]PrLv,zAvuzLvwzL[u]PL=[w]PL(u,v)PL.

Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ma postać: czyli M(AL)M(L).
Dla dowodu punktu 2 załóżmy, że język L jest rozpoznawalny. Zatem

L=wL[w]ρ,
gdzie ρ jest kongruencją o skończonym indeksie.

Z twierdzenia (patrz twierdzenie 2.1.) wnioskujemy, że ρPL. Oznacza to, że indeks relacji PL jest niewiększy od indeksu ρ, a co za tym idzie, M(L)=A/PL jest monoidem skończonym.

Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm kanoniczny
k:AA/PL=M(L).
Pokażemy, że spełnia on warunki z punktu 4. twierdzenia 1.2 z wykładu 3 (patrz twierdzenie 1.2. wykład 3). M(L) jest skończony, więc pozostaje do wykazania

równość

L=k1(k(L)).
W tym celu wystarczy oczywiście udowodnić inkluzję k1(k(L))L.

vk1(k(L))k(v)k(L)uL:k(v)=k(u)k(L)uL:[v]PL=[u]PLuL:vLuL.
Czyli vL i L=k1(k(L)).


Z twierdzenia 3.1 (patrz twierdzenie 3.1.) wynika, że określenie klas abstrakcji prawej kongruencji syntaktycznej PrL prowadzi do określenia minimalnego automatu rozpoznającego język L. Prezentowane poniżej twierdzenia wskazują sposób konstrukcji prawej kongruencji syntaktycznej dla języka L.

Twierdzenie 3.3.

Niech LA będzie dowolnym językiem,
a ΘLA×A relacją równoważności o dwóch klasach równoważności L i AL. Przez ρi dla iN oznaczmy zstępujący ciąg relacji określony następująco:

ρ1=ΘL, a dla i=2,... przyjmijmy

ρi={(u,w)A×A:(ua,wa)ρi1aA{1}}.

Wtedy ρi=PrL.

Dowód

Na początku uzasadnimy, że ρi jest prawą kongruencją na A. Załóżmy więc, że słowa x,yA są w relacji xρiy. Wybierzmy dowolne słowo zA i niech k oznacza długość tego słowa. Z założenia wynika, iż xρi+ky, co w świetle definicji ciągu relacji ρi implikuje, że xzρiyz. Ponieważ i jest dowolne wnioskujemy ostatecznie, że xzρiyz, co kończy dowód faktu, że ρi jest prawą kongruencją.

Dowiedziemy teraz równości
ρi=PrL.

Dla uzasadnienia inkluzji ρiPrL zauważmy, że jeśli xρiy, to dla dowolnego zA mamy xzρiyz, a w szczególności xzρ1yz. Z definicji relacji ρ1 dla dowolnego zA prawdziwa jest równoważność

xzLyzL.

A więc xPrLy. Inkluzję w stronę przeciwną pokażemy, dowodząc indukcyjnie ze względu na i=1,2,..., że dla dowolnych x,yA prawdziwa jest następująca implikacja

xPrLyxρiy.

Załóżmy zatem, że xPrLy. Z definicji PrL wynika, że dla dowolnego zA prawdziwa jest równoważność

xzLyzL.

Przyjmując z=1 otrzymujemy żądaną własność dla ρ1. Załóżmy teraz, że prawdziwa jest implikacja

xPrLyxρiy.

dla i=1,...,n1 oraz dla dowolnych x,yA. Stąd, że PrL jest prawą kongruencją, wnioskujemy, że dla dowolnego aA{1} spełniona jest relacja xaPrLya. Korzystając z założenia indukcyjnego, mamy xaρn1ya dla dowolnego aA{1}. A to oznacza z definicji ρi, że xρny i kończy dowód.

Kolejne twierdzenie charakteryzuje relację PrL dla języka rozpoznawalnego i orzeka, iż w przypadku języka rozpoznawalnego ciąg relacji ρi, aproksymujacych PrL, jest skończony. Równoważność dwóch pierwszych warunków poniższego twierdzenia nazywana bywa często w literaturze twierdzeniem A.Nerode.

Twierdzenie 3.4.

Następujące warunki są równoważne:

(1) Język L jest rozpoznawalny.
(2) Relacja PrL ma skończony indeks.
(3) Ciąg relacji ρi stabilizuje się, co oznacza, że istnieje iN takie, że
ρi=ρi+1=....
Dla najmniejszego takiego i prawdziwa jest równość ρi=PrL.

Dowód

Dowód poprowadzimy według następujacego schematu:

123

12

PrL jest największą w sensie inkluzji relacją spełniająca warunki punktu 2 z twierdzenia 1.3 z wykładu 3 (patrz twierdzenie 1.2 wykład 3). Z tego samego twierdzenia wynika skończoność indeksu.

12

Relacja PrL jest prawą kongruencją, ma skończony indeks oraz

L=wL[w]PrL.

Z twierdzenia 1.2 z wykładu 3 (patrz twierdzenie 1.2 wykład 3) wynika więc, że język L jest rozpoznawalny.

23 Dowód poprowadzimy nie wprost. Załóżmy więc, że dla każdego iN jest ρiρi+1. Oznacza to, że dla każdego iN indeksy relacji ρi tworzą ciąg silnie rosnący, to znaczy spełniają zależność indρi<indρi+1. Ponieważ indρ1=2, to dla każdego iN prawdziwa jest nierówność indρi>i. A to prowadzi do wniosku, że dla dowolnego iN

indPrL=indρi>i.

Zatem indeks relacji PrL jest nieskończony, co jest sprzeczne z założeniem.

23

Udowodnimy indukcyjnie ze względu na j, że każda z relacji ρj dla j=1,...,i ma skończony indeks. Oczywiście indρ1=2. Załóżmy teraz, że relacja ρj ma skończony indeks. Z definicji relacji ρj+1 wynika, że jej klasy równoważności powstają przez podział klas równoważności [w]ρj na skończoną liczbę klas relacji ρj+1 (skończona jest liczba możliwych do spełnienia warunków prowadzących do podziału). Oznacza to, że indeks relacji ρj+1 jest również skończony, a więc relacja PrL ma również skończony indeks.

Wykorzystamy powyżej udowodnione własności do konstrukcji automatu minimalnego rozpoznającego język L. Warto zauważyć, iż punktem wyjścia dla tej konstrukcji jest język L zadany, na przykład, poprzez wyrażenie regularne.

Przykład 3.1.

Niech do języka L należą wszystkie słowa nad alfabetem A={a,b} zaczynające się lub kończące literą a. Skonstruujemy minimalny automat akceptujący język L.

ρ1: L=aA+Aa,AL=bAb+b+1
ρ2: aAa+a,bAa,bAb+b+1,
ρ3: aAa+a,bAa,bAb+b,1,

Ponieważ ρ3=ρ4, to PrL=ρ3 i automat minimalny ma 4 stany.
Przyjmujemy s0=[1], s1=bAa, s2=aAa+a, s3=bAb+b oraz T={s1,s2}, a automat minimalny AL=(A/ρ3,f,s0,T)

przedstawiony jest przy pomocy grafu:
Rysunek 2

Przykład 3.2.

Dla języka L={w{a,b}:#aw=2k,#bw=2l+1,k,l0} określimy ciąg relacji ρi, a następnie relację PrL. Umożliwi nam to, w świetle powyższych rozważań, zbudowanie automatu minimalnego rozpoznającego ten język. Poniżej wypisane są klasy równoważności relacji ρ1 oraz ρ2, ρ3=ρ2, co kończy proces obliczania relacji ρi i daje równość ρ2=PrL.

ρ1: L,AL
ρ2: L,L1,L2,L3, gdzie
L1={w{a,b}:#aw=2k,#bw=2l,k,l0},
L2{w{a,b}:#aw=2k+1,#bw=2l+1,k,l0},
L3={w{a,b}:#aw=2k+1,#bw=2l,k,l0},

Przyjmując s0=L1=[1], s1=L3, s2=L2, s3=L oraz T={s3}

automat minimalny AL=(A/ρ2,f,s0,T) przedstawiony jest przy pomocy grafu:
Rysunek 3

Powyższe twierdzenia podają również sposób konstrukcji monoidu syntaktycznego języka L.