5.11. Zártsági tulajdonságok

A reguláris nyelvek zártak a reguláris műveletekre nézve, ami a reguláris kifejezésekkel való megadásukra emlékezve magától értetődő.

Ezzel szemben, ha csak a reguláris nyelvtanokkal, vagy véges automatákkal tudnánk leírni ezeket a nyelveket a probléma nem tűnne ilyen egyszerűnek.

A következő tétel bizonyításában konstrukciót adunk a nyelvműveletekkel előállított nyelvek nyelvtanokkal történő előállítására.

32. Tétel. A reguláris nyelvek osztálya zárt a reguláris műveletekre nézve, azaz tetszőleges G 1=(N 1, T, S 1, H 1) és G 2=(N 2, T, S 2, H 2) reguláris nyelvtanokhoz megkonstruálhatók olyan nyelvtanok amelyek L(G 1)∪L(G 2), L(G 1)L(G 2), illetve (L(G 1))* nyelveket generálnak.

Bizonyítás. A bizonyítás során az általánosság csorbítása nélkül feltehetjük, hogy N 1N 2=∅.

Unió (egyesítés). Legyen S olyan új nemterminális, amely eddig nem szerepelt sem N 1- ben, sem pedig N 2- ben. A

G +=(N 1N 2∪{S}, T, S 0, H 1H 2∪{S  → S 1, S  → S 2})

reguláris nyelvtan ekkor az L 1L 2 nyelvet generálja. A G + nyelvtanban az S mondatszimbólumra két szabály alkalmazható, vagy a G 1 vagy a G 2 mondatszimbólumát vezetjük be, ezután viszont N 1 és N 2 diszjunktsága miatt csak a választott nyelvtan szabályai lesznek alkalmazhatóak.

Konkatenáció. Legyen

G =(N 1N 2, T, S 1, H 2∪{A  → v B | Av BH 1, BN 1}∪{A  → v S 2 | AvH 1, vT *}).

Világos hogy ez a nyelvtan reguláris, másrészt pontosan akkor amikor az első nyelvtanban befejeződne egy levezetés, az új nyelvtanban az első nyelvbeli levezetett szó után megjelenik a második nyelvtan mondatszimbóluma a mondatformában, így G az L(G 1)L(G 2)- t generálja.

Kleene iteráció (a konkatenáció lezárása). Legyen SN 1, továbbá legyen H ' az a szabályrendszer, amiben helyettesítjük a H 1 minden A → v ( AN 1, vT *) szabályát az A → v S szabállyal. Az így kapott H ' szabályhalmazzal és S- sel képezett

G *=(N 1∪{S}, T, S, HH '∪{S  → λ, SS 1})

nyelvtan az (L(G 1))* nyelvet generálja és reguláris. ∎

A bizonyításban használt konstrukciók, illetve az alapnyelveket generáló egyszerű reguláris nyelvtanok (pl. ({S}, {a, b, c}, S, {Sa})) segítségével bármily reguláris kifejezéshez legyárthatjuk azt a reguláris nyelvtant, amely a kifejezéssel leírt nyelvet generálja.

A továbbiakban halmazműveletekre való zártságot fogunk bizonyítani determinisztikus elfogadó automatát felhasználva.

33. Tétel. A reguláris nyelvek halmaza zárt a metszet műveletre.

Bizonyítás. Legyen adott két reguláris nyelv az őket elfogadó determinisztikus automatákkal: F A=(Q, T, q 0, d, F) és F A '=(Q ', T, q' 0, d ', F ') ekkor megkonstruáljuk azt az automatát, amely az L(F A)∩L(F A ') nyelvet fogadja el: legyen

F A =(Q×Q ', T, (q 0, q' 0), d , F×F '),

ahol d ((q, q '), a)=(d(q, a), d '(q ', a)) minden qQ, q '∈Q ', aT esetén.

Az automata állapotpárokkal dolgozik, a pár első tagja F A- t, a második tagja F A '- t szimulálja, elfogadni pontosan akkor fog, ha mindkét szimulált automata egyszerre fogadna el. ∎

34. Tétel. A reguláris nyelvek halmaza zárt a komplementerképzés műveletre.

Bizonyítás. Legyen adott a reguláris nyelv a teljesen definiált determinisztikus elfogadó automatával, F A=(Q, T, q 0, d, F)- el. Ekkor egy wT * szót az automata pontosan akkor fogad el, ha d *(q 0, w)∈F. Legyen tehát F A c =(Q, T, q 0, d, QF), ekkor minden szóra pontosan ugyanaz a futás lesz, ami az eredeti F A automatában, azzal a különbséggel, hogy éppen akkor fog a futás végén az új automata elfogadni, amikor a régi nem fogadott el, és fordítva. ∎

5.49. példa - Reguláris nyelvtan megadása reguláris kifejezéshez 1. feladat


Adjuk meg az L=a*b ∪ b*a  reguláris kifejezéssel
megadott nyelvet generáló reguláris nyelvtant!
Megoldás:

(I.) A feladat megoldásához első lépésben vezessünk be minden terminális betűhöz
egy reguláris nyelvtant, mely kizárólag az adott terminálist generálja.

Jelen esetben a kiinduló nyelvtanok a következők:
Ga=({A},{a,b},A,{A  → a}),
Gb=({B},{a,b},B,{B  → b}).

(II.) Ezek után a kifejezésben belülről kifelé haladva építjük fel a nyelvtant a következőképpen:
1. Adott G=(N,T,S,H) nyelvtan esetén az L(G)
                  *
               
 nyelvet generáló nyelvtant megkaphatjuk,
ha az összes A →  p alakú szabály mellé - ahol p∈ T
               *, - bevezetjük az A →  pS alakú szabályt is,
valamint bevezetjük az S
               2 új mondatszimbólumot és az S
               2 → λ, S
               2 →  S szabályokat.

Jelen esetben:
Ga*
                  
=
({A,S},{a,b},S,{A →  a,A →  aA, S → λ,S →  A}),
Gb*
                  
=
({B,S},{a,b},S,{B →  b,B →  bB, S → λ,S →  B}).

2. Adott G
               1
               =(N,T,S,H) és G
               2
               =(N',T,S
               2
               ,H') nyelvtanok esetén - ahol N ∩ N'=∅ az
L(G)=L(G
               1)L(G
               2) konkatenált nyelvet generáló nyelvtan előállításához
első lépésben az összes H-beli A →  p szabályt - ahol p ∈ T*
               
 - az A →  pS
               2 szabályra cseréljük.
Az így kapott szabályhalmazt jelöljük H ''-vel. Ezek után G=(N∪ N',T
               ,S,H''∪ H').

Jelen esetben:

Ga*b=({A,S,B},{a,b},S,{A →  aB,A →  aA, S →  B, S →  A,B →  b}),

Gb*a=({B,S,A},{b,a},S,{B →  bA,B →  bB, S →  A,S →  B,A →  a}).

3. Adott G
               1
               =(N,T,S,H) és G
               2
               =(N',T,S
               2
               ,H') nyelvtanok esetén - ahol 
 NN '=
 - az L(G)=L(G
               1)∪ L(G
               2) nyelvet generáló nyelvtan előállításához
G=(N∪ N'∪ {S
               3}, T, S
               3
               , H∪ H'∪ {S
               3
                →  S, S
               3
                →  S
               2}) nyelvtan megfelelő lesz,
ahol S
               3 nem eleme az N, N', T halmazok egyikének sem.
Jelen esetben a 2. pontban megadott Ga*b és Gb*a
               
 nyelvtanok esetén nem teljesül az a feltétel,
miszerint a nemterminálisok halmazai diszjunktak, ezért az egyik nyelvtanban először át kell
jelölni a nemterminálisokat.
Legyen például
G'a*b=({C,S
               2
               ,D},{a,b},S
               2
               ,{C →  aD,C →  aC, S
               2
                →  D,S
               2
                →  C,D →  b})!

Természetesen a nemterminálisok átjelölése nem befolyásolja a generált nyelvet, azaz
L(G'a*b
               
)=L(Ga*b
               
).
Ezek után már meg tudjuk adni a
G
               
                  a
                  *
                  bb
                  *
                  a
               
=({C,S
               2
               ,D,B,S,A,S
               3},{a,b},S
               3
               , {C →  aD, C →  aC, 
               S
               2
                →  D, S
               2
                →  C, D →  b, B →  bA,
B →  bB, S →  A, S →  B, A →  a, S

               3
                → S
               2
               , S
               3
                →  S})
reguláris nyelvtant, mely pontosan az L nyelvet generálja. ★
 


5.50. példa - Reguláris nyelvtan megadása reguláris kifejezéshez 2. feladat


Adjuk meg az L=(ab)
                  *
               
 reguláris kifejezéssel megadott nyelvet generáló reguláris nyelvtant!
 


Megoldás:
(I.)
Ga=({A},{a,b},A,{A → a}),

               Gb=({B},{a,b},B,{B → b}),

(II.)
 1. G
               
                  ab
               

               =({A,B,S},{a,b},S,{A → a, B → b,S → A,S → B}),
 2. G
               (ab)*
               

               =({A,B,S,S
               2},{a,b},S
               2
               ,{A → a, A → aS, B → b, B → bSS → A, S → B, S
               2
                → λ, S
               2
                → S}). ★
 


5.51. példa - Reguláris nyelvtan megadása reguláris kifejezéshez 3. feladat


Adjuk meg az L=ab*c reguláris kifejezéssel megadott nyelvet generáló reguláris nyelvtant!
 


Megoldás:
(I.)
Ga=({A},{a,b,c},A,{A → a}),

               Gb=({B},{a,b,c},B,{B → b}),

               Gc=({C},{a,b,c},C,{C → c}).
(II.)
 1. Gb*
                  
=
({B,S},{a,b,c},S,{B → b, B → bB, S → λ, S → B})
 2. Gab*
                  
=
({A,B,S},{a,b,c},A,{A → aS, B → b, B → bB, S → λ, S → B})
 3. Gab*c=({A,B,S,C},{a,b,c},A,{A → aS, B → bC, B → bB, S → C, S → B, C → c}). ★
 


5.52. példa - Reguláris nyelvtan megadása reguláris kifejezéshez 4. feladat


Adjuk meg az L=(ab*
               
)
                  *
               
 reguláris kifejezéssel megadott nyelvet generáló reguláris nyelvtant!
 


Megoldás:
(I.)
Ga=({A},{a,b},A,{A → a}),

               Gb=({B},{a,b},B,{B → b}).

(II.)
 1. Gb*
                  
=
({B,S},{a,b},S,{B → b, B → bB, S → λ, S → B}),
 2. Gab*
                  
=
({A,B,S},{a,b},A,{A → aS, B → b, B → bB, S → λ, S → B}),
 3. G
               (ab*
                  
)
                     *
                  

               
=({A,B,S,S
               2},{a,b},S
               2
               ,{A → aS, B → b, B → bA, B → bB, S → λ,
 
               S → A, S → B, S
               2
                → λ, S
               2
                → A}). ★
 


5.53. példa - Reguláris nyelvtan megadása reguláris kifejezéshez 5. feladat


Adjuk meg az L=a*b∪ b*
               
 reguláris kifejezéssel megadott nyelvet generáló reguláris nyelvtant!


Megoldás:

(I.)
Ga=({A},{a,b},A,{A → a}),

               Gb=({B},{a,b},B,{B → b}).

(II.)
 1. Ga*
                  
=
({A,S},{a,b},S,{A → a, A → aA, S → λ, S → A}),
 2. Ga*b=({A,S,B},{a,b},S,{A → aB, A → aA, S → B, S → A, B → b}),
 3. Gb*
                  
=
({B,S},{a,b},S,{B → b, B → bB, S → λ, S → B}),
 4. G'b*
                  
=
({D,Z},{a,b},Z,{D → b, D → bD, Z → λ, Z → D}),
 5. G
               
                  a
                  *
                  bb
                  *
               

               =({A,S,B,D,Z,S
               2},{a,b},S
               2
               ,{A → aB, A → aA, S → B, S → A, B → b, 
               D → b, D → bD,
 Z → λ, Z → D, S

               2
                → S, S
               2
                → Z}). ★


5.54. példa - Reguláris nyelvtan megadása reguláris kifejezéshez 6. feladat


Adjuk meg az L=a*
               
b*
               
c*
               
 reguláris kifejezéssel megadott nyelvet generáló reguláris nyelvtant!
 


Megoldás:
(I.)
Ga=({A},{a,b,c},A,{A → a}),

               Gb=({B},{a,b,c},B,{B → b}),

               Gc=({C},{a,b,c},C,{C → c}).
(II.)
 1. Ga*
                  
=
({A,S},{a,b,c},S,{A → a, A → aA, S → λ,S → A}),
 2. Gb*
                  
=
({B,S},{a,b,c},S,{B → b, B → bB, S → λ, S → B}),
 3. G'a*
                  
=
({A,S
               2},{a,b,c},S
               2
               ,{A → a, A → aA, S
               2
                → λ, S
               2
                → A}),
 4. G
                  a
                  *b
                  *
               

               =({A,S
               2
               ,B,S,S
               3},{a,b,c},S
               3
               ,{A → a, A → aA, S
               2
                → λ, S
               2
                → A, 
               B → b, B → bB, S → λ,
 S → B, S

               3
                → S
               2
               , S
               3
                → S}),
 5. Gc*
                  
=
({C,S},{a,b,c},S,{C → c, C → cC, S → λ, S → C}),
 6. G'c*
                  
=
({C,S
               4},{a,b,c},S
               4
               ,{C → c, C → cC, S
               4
                → λ, S
               4
                → C}),
 7. G
                  a
                  *b
                  *c
                  *
               

               =({A,S
               2
               ,B,S,S
               3
               ,C,S
               4
               ,S
               5},{a,b,c},S
               5
               ,{A → a, A → aA, S
               2
                → λ, S
               2
                → A, 
               B → b, B → bB,
 S → λ, S → B, S

               3
                → S
               2
               , S
               3
                → S, C → c, C → cC, S
               4
                → λ, S
               4
                → C,
               S
               5
                → S
               3
               , S
               5
                → S
               4}). ★


5.55. példa - Reguláris nyelvtan megadása reguláris kifejezéshez 7. feladat


Adjuk meg az L=(abc)
                  *
               
(ba)
                  *
               
 reguláris kifejezéssel megadott nyelvet generáló reguláris nyelvtant!
 


Megoldás:
(I.)
Ga=({A},{a,b,c},A,{A → a}),

               Gb=({B},{a,b,c},B,{B → b}),

               Gc=({C},{a,b,c},C,{C → c}).
(II.)
 1. Gab=({A,B},{a,b,c},A,{A → aB, B → b}),
 2. Gba=({B,A},{a,b,c},B,{B → bA, A → a}),
 3. G
                  a
                  bc
               
=({A,B,C,S},{a,b,c},S,{A → aB, B → b, C → c, S → A, S →  C}),
 4. G(a
                  bc)*
               
=({A,B,C,S,S
               2},{a,b,c},S
               2
               ,{A → aB,  
               B → b, B → bS, C → c, C → cS, S → A, S → C,
 S

               2
                → λ, S
               2
                → S}),
 5. G
               (ba)
                     *
                  

               
=({B,A,S},{a,b,c},S,{B → bA, A → a, A → aB, S → λ, S → B}),
 6. G'
               (ba)
                     *
                  

               
=({D,C,Z},{a,b,c},Z,{D → bC, C → a, C → aD, Z → λ, Z → D}),
 7. G(a
                  bc)*(ba)*
               
=({A,B,C,S,S
               2
               ,D,C,Z},{a,b,c},S
               2
               , {A → aB, B → bZ, B → bS, C → cZ, C → cS,
 S → A, S → C, S

               2
                → Z,
               S
               2
                → S, D → bC, C → a, C → aD, Z → λ, Z → D}). ★
 


5.56. példa - Reguláris nyelvtan megadása reguláris kifejezéshez 8. feladat


Adjuk meg az L=(a*ba*
               
aa)
                  *
               
 reguláris kifejezéssel megadott nyelvet generáló reguláris nyelvtant!


Megoldás:
(I.)
Ga=({A},{a,b},A,{A → a}),

               Gb=({B},{a,b},B,{B → b}).

(II.)
 1. Ga*
                  
=
({A,S},{a,b},S,{A → a,A → aA, S → λ,S → A}),
 2. Ga*b=({A,S,B},{a,b},S,{A → aB,A → aA, S → B,S → A,B → b}),
 3. G'a*
                  
=
({C,Z},{a,b},Z,{C → a,C → aC, Z → λ,Z → C}),
 4. Ga*ba*
                  
=
({A,S,B,C,Z},{a,b},S,{A → aB, r;aA,S → B,S → A,B → bZ,
 
               C → a, C → aC, Z → λ, Z → C}),
 5. G'a=({E},{a,b},E,{E → a}),
 6. Gaa=({A,E},{a,b},A,{A → aE,E → a}),
 7. G'aa=({F,E},{a,b},F,{F → aE,E → a}),
 8. G
                  a
                  *
                  b
                  a
                  *a
                  a
               
=({A,S,B,C,Z,F,E,S
               2},{a,b},S
               2
               ,{A → aB, A → aA,S → B,S → A, 
               B → bZ, C → a,C → aC,
 Z → λ, Z →  C, F → aE,E → a,S

               2
                → S, S
               2
                → F}),
 9. G(a
                  *
                  b
                  a
                  *a
                  a)*
               
=({A, S, B, C, Z, F, E, S
               2
               , S
               3},{a,b}, S
               3
               , {A → aB, A → aA, 
               S → B, S → A, B → bZ,
  C → aS

               2
               , C → aC, Z →  S
               2
               , Z → C, F → aE, E → aS
               2
               ,
               S
               2
                → S, S
               2
                → F, S
               3
                → λ, S
               3
                → S
               2}). ★