5.2. Reguláris kifejezések

Legyen T={a 1, …, a n } tetszőleges nem üres és véges halmaz. Ha a T ábécét kibővítjük a benne nem szereplő ∅, λ, +, ⋅, *, (, ) jelekkel: V=T∪{∅, λ, +, ⋅, *, (, )}, akkor a V ábécé felett értelmezhetjük a reguláris kifejezések halmazát a következő induktív definícióval:

Elemi kifejezés:

- ∅ reguláris kifejezés,

- λ reguláris kifejezés,

- minden aT reguláris kifejezés.

Indukciós lépések:

- ha p és r reguláris kifejezések, akkor (p+r) is az,

- ha p és r reguláris kifejezések, akkor (pr) is az,

- ha r reguláris kifejezés, akkor r * is az.

Továbbá, minden reguláris kifejezés előáll az elemi kifejezésekből az indukciós lépések véges sokszori alkalmazásával.

A konkatenáció ⋅ műveleti jelét sokszor, ahogy eddig is, elhagyjuk.

A reguláris kifejezések segítségével nyelveket írhatunk le:

az elemi kifejezésekkel elemi nyelveket:

- ∅ (üres halmaz) jelöli az {} üres nyelvet,

- λ jelöli a {λ} kezdő nyelvet,

- a jelöli az {a} egyszavas alapnyelvet.

Az indukciós lépéssel pedig:

- (p+r) jelöli az L p L r nyelvet,

- (pr) jelöli az L p L r nyelvet,

- r * jelöli az L r * nyelvet,

ahol L p és L r a p és az r reguláris kifejezések által jelölt nyelvek.

Két reguláris kifejezést ekvivalensnek nevezünk, ha ugyanazt a nyelvet írják le.

A T feletti nyelvek közt, tehát, a következő műveleteket (reguláris műveleteknek) hívjuk:

(i) összedás: nem más mint a két nyelv halmazelméleti uniója;

(ii) szorzás: a két nyelv konkatenációja;

(iii) iteráció: L iteráltján vagy más néven lezártján értjük és L *- al jelöljük az L *={p 1 p 2⋅⋅⋅p k |p 1, …, p k L, k ≥ 1}∪{λ} nyelvet. Vagy ahogy már korábban is definiáltuk, , ahol L 0={λ}, L i =L L i-1.

Az L T  = {L|LT *} halmazt a rajta értelmezett ezen három művelettel T feletti nyelvalgebrának hívjuk. A nyelvalgebrában érvényesek az absztrakt algebrából ismert, vagy azokhoz hasonló műveleti tulajdonságok:

L 1L 2=L 2L 1 (összeadás kommutatívitása);

(L 1L 2)∪L 3=L 1∪(L 2L 3) (összeadás asszociativitása);

L∪∅=L (additív egységelem létezése);

(L 1 L 2)L 3=L 1(L 2 L 3) (szorzás asszociativitása);

L{λ}={λ}L=L (multiplikatív egységelem létezése);

(L 1L 2)L 3=L 1 L 3L 2 L 3 (baloldali disztributivitás);

L 1(L 2L 3)=L 1 L 2L 1 L 3 (jobboldali diszributivitás);

{λ}*={λ} ;

*={λ};

L L *=L * L ;

L *={λ}∪L L * ;

(L 1L 2)*=(L 1 * L 2 *)* (unió kiváltása).

Két kivétellel minden felsorolt azonosság egyszerű számítással adódik a definíciók alapján. Ezért csak ezt a két összefüggést fogjuk bizonyítani.

Mutassuk meg először, hogy . Ehhez azt kell belátnunk, hogy a baloldali halmaznak pontosan azok az elemei mint a jobboldalinak.

A baloldali halmaznak és a jobboldali halmaznak is eleme az üresszó, így csak az üresszótól különböző elemek vizsgálatára kell szorítkoznunk. A baloldal az üres szón kívül tartalmazza azokat a p szavakat, melyek előállnak valamely n ≥ 1- re p=p 1⋅⋅⋅p n alakban, ahol p 1, …, p n L. Ha minden tényező az üresszó, akkor p=λ, s ezzel az esettel már nem kell tovább foglalkoznunk. Tehát feltehető, hogy van olyan 1 ≤ i ≤ n, hogy p i λ, azaz pλ. Legyen valamely u ≥ 0 nemnegatív egészre n=u k+v, ahol 0 ≤ v<k. Ekkor p=q 1 q 2, ahol vagy q 1=λ (ekkor u=0) vagy pedig q 1=p 1⋅⋅⋅p u k , ahol p 1, …, p u k L (ha u≠0), s ugyanekkor vagy q 2=λ (ekkor v=0), vagy q 2=p u k+1⋅⋅⋅p u k+v , ahol p u k+1, …, p u k+v L (ha v≠0). Mindenképp fennáll, hogy q 1∈(L k )*, illetve q 2L v , 0 ≤ v<k, azaz p=q 1 q 2∈(L k )* L v . Tehát p eleme mindkét oldalnak, amivel a két oldal egyenlőségét kimutattuk.

Igazoljuk most az (L 1L 2)*=(L 1 * L 2 *)* egyenlőséget. Itt is igaz, hogy a baloldali halmaznak és a jobboldali halmaznak is eleme az üresszó, így csak az üresszótól különböző elemek vizsgálatára kell szorítkoznunk. Hasonló a helyzet mint az előző esetben. Mindkét oldal az üresszón kívül pontosan azokat a p szavakat tartalmazza, melyek előállnak valamely n ≥ 1- re p=p 1⋅⋅⋅p n alakban, ahol p 1, …, p n L 1L 2. A két halmaz tehát egyenlő.

A reguláris kifejezésekben a fent említett nyelvazonosságok miatt (pl. asszociativitás) zárójeleket hagyhatunk el a leírt nyelv egyértelműségét megtartva. További zárójeleket hagyhatunk el, ha megállapodunk abban a szokásos precedenciában, hogy a * művelet (ahogy a hatványozás szokott lenni) a legerősebb, majd következik a szorzás (konkatenáció) és az összeadás (unió) a leggyengébb.

A reguláris kifejezésekkel a reguláris nyelvek egy alternatív definícióját adhatjuk meg.

Reguláris nyelvnek hívjuk az üres nyelvet, továbbá mindazon nyelveket, amelyek elemi nyelvekből a reguláris műveletek véges számú alkalmazásával előállíthatók. (Így például reguláris nyelvek: ∅, {λ}, {a 1}, T *, ({a 1}{a 2})*∪{a 3}.) Később igazolni fogjuk, hogy a reguláris nyelv fogalmának korábbi nyelvtannal történő definíciója ezzel a fogalommal ekvivalens. A reguláris kifejezések tehát megmutatják, hogy a reguláris nyelv hogyan áll elő az elemi nyelvek és az alapműveletek segítségével. Egy reguláris kifejezés egyértelműen definiál egy nyelvet, fordítva viszont egy reguláris nyelvet leíró reguláris kifejezés általában nem egyértelműen meghatározott. (Például L{λ}=∅* L=({λ}+{λ})L=⋅⋅⋅.) Ezért külön érdekes, hogy hogyan lehet eldönteni az F T nyelvalgebrában, hogy két különböző reguláris kifejezés ugyanazt a reguláris nyelvet állítja-e elő. Később látni fogjuk, hogy ez a kérdés eldönthető. Sőt, ha pontosan megmondjuk, hogy mit is értünk egy reguláris nyelvet megadó minimális reguláris kifejezésen (például lehet ez alatt érteni (a karakterszámra) a legrövidebbet), akkor annak meghatározására is megadható algoritmus.

Itt jegyezzük meg, hogy az unió és konkatenáció műveletek tartják a végességet, vagyis ha * művelet nem szerepel egy reguláris kifejezésben, akkor az általa leírt nyelv véges. Ily módon éppen a véges nyelvek egy jellemzését adhatjuk meg, hiszen minden véges nyelv megadható a szavai között + jelekkel, mint reguláris kifejezéssel megadott nyelv. A következőkben néha nem teszünk különbséget egy reguláris kifejezés és az általa leírt nyelv között, vagyis magára a nyelvre is hivatkozunk a reguláris kifejezéssel. Amennyiben nem okoz félreértést, az unió jelet (∪), illetve az összeadás jelet (+), is használhatjuk ugyanabban a szerepben. A következő alfejezetben ugyancsak speciális reguláris kifejezéseket fogunk megvizsgálni.

5.2.1. Reguláris kifejezések ekvivalenciája

A reguláris kifejezések között vannak ekvivalensek, vagyis ugyanazt a halmazt (reguláris nyelvet) általában több, egymástól különböző reguláris kifejezés is megadja. Ez alapján az ekvivalencia reláció alapján az ekvivalens formulákat felhasználhatjuk formulák átalakítására.

Néhány ilyen ekvivalencia például:

  • (pq) kifejezés jelentése ugyanaz, mint (qp) kifejezésé;

  • (pq)∪r kifejezés jelentése ugyanaz, mint p∪(qr) kifejezésé;

  • (pq)(rt) kifejezés ugyanazt jelenti, mint a (p rp tq rq t);

  • r r * pedig ekvivalens r * r kifejezéssel.

Az unió művelet kommutativitása és asszociativitása miatt zárójeleket hagyhatunk el, és tekinthetjük az unió műveletet akár kettőnél több argumentumúnak is.

5.2. példa - Nyelv megadása reguláris kifejezéssel 1. feladat


 Adjuk meg reguláris kifejezéssel azt a nyelvet a {0,1} ábécé felett, amely azon szavakból áll,
 amelyek tartalmazzák részszóként a 010 szót!


 Megoldás: L=(0+1)*010(0+1)* ★
 


5.3. példa - Nyelv megadása reguláris kifejezéssel 2. feladat


 Adjuk meg reguláris kifejezéssel azt a nyelvet a {0,1} ábécé felett, amely azon szavakból áll,
 amelyek tartalmazzák részszóként a 000 vagy az 111 szót!


 Megoldás: L=(0+1)*(000+111)(0+1)* ★
 


5.4. példa - Nyelv megadása reguláris kifejezéssel 3. feladat


 Adjuk meg reguláris kifejezéssel azt a nyelvet a {0,1} ábécé felett, amely azon 1-esre végződő
 szavakból áll, amelyek nem tartalmazzák részszóként a 00 szót!


 Megoldás: L=(1+01)* ★
 


5.5. példa - Nyelv megadása reguláris kifejezéssel 4. feladat


 Adjuk meg reguláris kifejezéssel azt a nyelvet a {0,1} ábécé felett, amely azon szavakból áll,
 melynek 3. betűje 0!


 Megoldás: L=(00+01+10+11)0(0+1)* ★
 


5.6. példa - Nyelv megadása reguláris kifejezéssel 5. feladat


 Adjuk meg reguláris kifejezéssel azt a nyelvet a {0,1} ábécé felett, amely azon szavakból áll,
 melyek tartalmaznak legalább három 1-est!


 Megoldás: L=(0+1)*1(0+1)*1(0+1)*1(0+1)* ★
 


5.7. példa - Nyelv megadása reguláris kifejezéssel 6. feladat


 Adjuk meg reguláris kifejezéssel azt a nyelvet a {0,1} ábécé felett, amely azon szavakból áll,
 melyek 5-tel osztható 1-est tartalmaznak!


 Megoldás: L=(0*10*10*10*10*10*)* ★
 


5.2.2. A kifejezésfa

A kifejezéseket, illetve a formulákat, amik atomokból (tovább nem bontható egységek), illetve műveletekből állnak szokás fa formájában is ábrázolni. A fa levélelemeiben az atomok (itt most a terminálisok és az üresszó) a többi csomópontban pedig a műveletek szerepelnek. Minden műveletnek megfelelő csúcsból pontosan annyi darab él indul ki a további részkifejezésekhez, ahány argumentumú az operátor. Példaként az egész számokat leíró reguláris kifejezés fa alakban:

5.2.3. Unió-normálforma reguláris kifejezésekhez

A normálformák fontos szerepet játszanak a számítástudomány sok területén, pl. a logikában a konjunktív-, diszjunktív- normálformákról, illetve prenex alakú formulákról beszélhetünk. Ezekben a formulákban a műveletek sorrendjére van valamilyen megszorításunk. Lényeges viszont az, hogy minden formulához létezik vele ekvivalens amely normálformában van. Normálformát értelmezhetünk a reguláris kifejezésekre is.

Egy reguláris kifejezésről akkor mondjuk, hogy unió-normálformában van, ha a kifejezésfájában unió művelet csak a fa gyökerében szerepelhet (megengedve bármekkora aritású unió műveletet).

Ekkor igaz a következő eredmény:

A következő ekvivalenciák véges sokszori alkalmazásával bármely (reguláris) kifejezés normálformára hozható:

(1) (pr)* → (p * r *)*,

(2) p(qr) → p qp r,

(3) (pq)rp rq r,

(4) (pq)(rt) → p rp tq rq t.

Tehát egy unió-normálformájú kifejezés véges sok uniómentes kifejezés uniója (a normálformát 2004-ben vezette be Nagy Benedek).

Lássuk végül, hogyan néz ki a tizes számrendszerben felírt egész számokat leíró reguláris kifejezés normálformája. Mivel a kifejezés meglehetősen hosszú, bevezetünk egy rövidítést:

S≡(0*1*2*3*4*5*6*7*8*9*)*.

Így a harminc tagú unió (hogy a + előjelet ne keverjük a reguláris unió művelettel, ez utóbbit itt ∪- val jelöljük):

0S∪1S∪2S∪3S∪4S∪5S∪6S∪7S∪8S∪9S

+0S∪+1S∪+2S∪+3S∪+4S∪+5S∪+6S∪+7S∪+8S∪+9S

-0S∪-1S∪-2S∪-3S∪-4S∪-5S∪-6S∪-7S∪-8S∪-9S

5.8. példa - Reguláris kifejezés unió-normálformára alakítása - 1. feladat

(a+b)(c+d+e)≡ a c+a d+a e+b c+b d+b e


5.9. példa - Reguláris kifejezés unió-normálformára alakítása - 2. feladat

((a b+c *)d *)*)≡ (a b d *+c * d *)*≡ ((a b d *)*(c * d *)*)*

ez már uniómentes, de egyszerűsíthető: ((a b)* c * d *)*


5.10. példa - Reguláris kifejezés unió-normálformára alakítása - 3. feladat

(a *+b)*(c+d)*≡ ((a *)* b *)*(c * d *)*)≡ (a * b *)*(c * d *)*


5.11. példa - Reguláris kifejezés unió-normálformára alakítása - 4. feladat

(a+b a b)(b b+a b a b a)*≡ (a+b a b)((b b)*(a b a b a)*)*a((b b)*(a b a b a)*)*+b a b((b b)*(a b a b a)*)*


5.12. példa - Reguláris kifejezés unió-normálformára alakítása - 5. feladat

(p+m+λ)(0+1)(0+1)*≡ (p0+m0+0+p1+m1+1)(0+1)*≡ (p0+m0+0+p1+m1+1)(0*1*)*p0(0*1*)*+m0(0*1*)*+0(0*1*)*+p1(0*1*)*+m1(0*1*)*+1(0*1*)*