7.6. Zártsági tulajdonságok

Ebben a fejezetben a környezetfüggetlen nyelvek zártsági tulajdonságait vizsgáljuk meg.

55. Tétel. A környezetfüggetlen nyelvek osztálya zárt a reguláris műveletekre nézve.

Bizonyítás. A bizonyítás során tételezzük fel, hogy L 1=L(G 1), L 2=L(G 2), ahol G 1=(N 1, T, S 1, H 1) és G 2=(N 2, T, S 2, H 2), valamint N 1N 2=∅. A bizonyítást az egyes műveletekre külön-külön végezzük el.

Egyesítés (unió). S legyen egy olyan nemterminális, amely eddig nem szerepelt sem N 1- ben, sem N 2- ben. A

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

környezetfüggetlen nyelvtan ekkor az L 1L 2 nyelvet generálja. A levezetés során első lépésként alkalmazható S → S 1, illetve S → S 2 szabály választásával eldöntjük, hogy melyik nyelvtan alapján szeretnénk generálni a következő szót; ezután pedig, mivel N 1 és N 2 diszjunkt halmazok, csak a megfelelő H 1, illetve H 2- beli szabályok alkalmazhatóak a levezetés során.

Konkatenáció. Legyen ismét SN 1N 2. Ekkor a

G =(N 1N 2∪{S}, T, S, H 1H 2∪{SS 1 S 2})

környezetfüggetlen nyelvtan az L 1 L 2 nyelvet generálja, hiszen az első lépésben generált S 1 S 2 mondatformában S 1- ből egy L 1- beli szó, S 2- ből pedig egy L 2- beli szó generálható egymástól függetlenül.

Kleene-csillag (konkatenáció lezárása). Legyen SN 1. Ekkor a

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

környezetfüggetlen nyelvtan az L * nyelvet generálja. ∎

A fejezet hátralevő részében további halmazműveleteket vizsgálunk.

56. Tétel. A környezetfüggetlen nyelvek osztálya nem zárt metszetképzésre.

Bizonyítás. Legyen G 1=({S 1, A}, {a, b, c}, S 1, {S 1a S 1, S 1 → A, Ab A c, A → λ}). Ekkor könnyen ellenőrizhető, hogy L(G 1)={a i b j c j |i, j ≥ 0}. Hasonlóan, legyen G 2=({S 2, B}, {a, b, c}, S 2, {S 2S 2 c, S 2 → B, Ba B b, B → λ}), így L(G 2)={a i b i c j |i, j ≥ 0}. G 1 és G 2 is környezetfüggetlen (sőt lineáris) nyelvtan, viszont L(G 1)∩L(G 2)={a i b i c i |i ≥ 0}, ami, ahogy a Bar-Hillel lemma segítségével bizonyítottuk nem környezetfüggetlen. ∎

57. Tétel. A környezetfüggetlen nyelvek halmaza nem zárt a komplementerképzésre.

Bizonyítás vázlat. a {w c w|w∈{a, b}*} nyelvről a Bar-Hillel lemmával beláthatjuk hogy nem környezetfüggetlen (lásd 7.11. példa - Bar-Hillel lemma 2. feladat), míg a komplementere környezetfüggetlen, sőt lineáris nyelv. ∎

7.34. példa - A jelölt másolatok nyelvének komplementere - Gyakorló feladat

Készítsünk környezetfüggetlen nyelvtant (vagy 2-fejű automatát) amely a {w c w|w∈{a, b}*} nyelv komplementerét fogadja el. ★


Tehát sem a lineáris, sem a környezetfüggetlen nyelvek halmaza nem zárt a metszet és a komplementerképzés műveletére.