8.3. INSDEL nyelvosztályok

Ebben az alfejezetben a beszúró-törlő rendszerekkel definiálható nyelvosztályok és a hagyományos (Chomsky-féle) nyelvosztályok közti relációkat fogunk megvizsgálni.

A különböző beszúró-törlő rendszerekkel definiálható nyelvekkel kapcsolatosan először három alapvető tényt közlünk.

A különböző súlyokkal definiált nyelvosztályokra a definíció alapján teljesül a következő:

11. Lemma.

minden 0 ≤ nn', 0 ≤ mm', 0 ≤ pp' és 0 ≤ qq' esetén. Ebben a jelölésrendszerben n, m, p, q ∈ℕ ∪ {*}, és minden n ∈ ℕ esetén n ≤ *.

Amiatt, hogy formálisan definiált rendszerekről van szó, teljesül a következő

12. Lemma.

Vagyis, a beszúró-törő rendszerek számításait, generatív nyelvtanok, vagy Turing-gépek segítségével is szimulálhatjuk.

Továbbá,

13. Lemma.

Vagyis a törlőszabályok használata nélkül, monoton (vagy környezetfüggő) nyelvtannal, illetve lineárisan korlátozott automatával is szimulálható a beszúró(-törlő) rendszer számítása.

Ennél sokkal érdekesebb, hogy minden reguláris nyelv előállítható ily módon:

24. Tétel.

REG

Bizonyítás: Legyen L egy reguláris nyelv, amit M = (Q, T, q0, δ, F) minimális determinisztikus véges automata fogad el. Definiáljuk a τw : QQ leképezést minden wT* szóra:

τw (q) = q', pontosan akkor, ha (q,w) ⊢* (q', λ), q, q'Q.

Nyilvánvaló, hogy ha x1, x2T* olyan, hogy τx1 = τx2, akkor minden u, vT* párra ux1v pontosan akkor L-beli, ha ux2v is az.

A τ leképezés véges sok féle lehet, hiszen Q véges, legyen a számuk n0.

Legyen a B = (T, T, A, I, ∅) beszúró-törlő rendszer a következőképpen definiálva:

A = {wL ∣ ∣w∣ ≤ n0 - 1}

és

I = {(w, v, λ) ∣ ∣w∣ ≤ n0 - 1, 1 ≤∣v∣ ≤ n0, ∣wv∣ ≤ n0, és τw = τwv}.

A τw, valamint az A és I definícióiból következik, hogy L(B) ⊆ L fennáll.

Az LL(B) részt indirekten bizonyítjuk. Tegyük fel tehát, hogy ez nem teljesül, tehát van olyan x szó, amelyre xL és xL(B). Jelölje a továbbiakban x a legrövidebb ilyen tulajdonságú szót. Nyilvánvaló, hogy xA, és így ∣x∣ ≥ n0. Legyen x = zz' úgy, hogy z az x n0 hosszúságú prefixe, vagyis ∣z∣ = n0, ekkor z'T*. Ekkor z = a1a2 ... an0 (a1, a2, ..., an0T), így z-nek n0 + 1 különböző prefixe van: λ, a1, a1a2, ..., a1a2 ... an0. Mivel csak n0 különböző τw leképezés van, van a z-nek két olyan különböző prefixe, u1 és u2, hogy τu1 = τu2. Az általánosság csorbítása nélkül feltehetjük, hogy ∣u1 ∣ < ∣u2∣. Ekkor, ha u2 helyére u1-et helyettesítjük az x szó elején, megkapunk egy x' szót, ami ugyancsak L nyelvbeli. Mivel viszont ∣x'∣< ∣x∣, és feltevésünk szerint x a legrövidebb olyan szó, amely L-beli, de nem szerepel L(B)-ben, az x'L(B) fennáll. Viszont ∣u2∣ - ∣u1∣ < ∣u2∣ ≤ n0, így ha u2 = u1u3, akkor (u1, u3, λ) ∈ I beszúrási szabály szerepel a B rendszerben. Emiatt B-ben x'x fennáll, vagyis xL(B). Ezt az ellentmondást csak az indirekt feltevésünk okozhatta, tehát az nem igaz, vagyis LL(B).

Ezzel a tételnek a REG részét bizonyítottuk.

A tartalmazás valódiságának belátásához, vegyük a 33. példát. Ez alapján a nem reguláris

QED.

Ezzel szemben van olyan lineáris nyelv amely nincs az osztályban:

14. Lemma. Az L = {anbann ≥ 1} lineáris nyelvre,

Bizonyítás: Ha egy L' végtelen nyelv benne van az családban, akkor végtelen sok wL' szó van, hogy w = uxv, ahol x ≠ λ és uvL'. Mivel a tételben szereplő L nyelv végtelen, de nem rendelkezik ezzel a tulajdonsággal, nem lehet az nyelvcsaládban.

QED.

Viszont már is tartalmaz nem szemilineáris, tehát nem környezetfüggetlen nyelvet (a konstrukció elég hosszú, így ezen állítás bizonyítását itt mellőzzük).

Viszont,

25. Tétel.

Bizonyítás: A bizonyítás konstruktív, bármely a feltételnek eleget tevő beszúró-törlő rendszerhez definiálunk egy olyan környezetfüggetlen nyelvtant, ami ugyanazt a nyelvet generálja.

Vegyünk egy B = (V, T, A, I, ∅) beszúró-törlő rendszert (n, 1; 0, 0) súlyokkal valamilyen n ≥ 1 értékre. Mivel törlésre nincs lehetőség, az A axiómahalmazból eltávolítható minden nem T*-beli axióma (nem állítható elő belőlük egyetlen terminális szó sem), illetve I-ből minden olyan szabályt is eltávolíthatunk, ami tartalmaz nem T-beli szimbólumokat. Így, a továbbiakban feltesszük, hogy V = T.

Konstruáljunk egy G = (N, T, S, H) környezetfüggetlen nyelvtant, ahol

N = {S} ∪ {(λ, a), (a,b), (a, λ) ∣ a, bT},

H = {S → (λ, a1)(a1,a2)(a2,a3)...(ak-1,ak)(ak, λ) ∣ a1a2... akA, k ≥ 1, aiT, 1 ≤ i ≤ k}

∪ {(a,b) → (a, a1)(a1,a2) ... (ak,b) ∣ (a, a1a2 ... ak,b) ∈ I,

vagy (a, a1a2 ... ak, λ) ∈ I, vagy (λ, a1a2... ak,b) ∈ I,

vagy (λ, a1a2 ... ak, λ) ∈ I, k ≥ 1, aiT, 1 ≤ ik, a,bT}

∪ {(λ,a) → (λ,a1)(a1,a2) ... (ak,a) ∣ (λ, a1a2 ... ak,a) ∈ I,

vagy (λ, a1a2 ... ak, λ) ∈ I, k ≥ 1, aiT, 1 ≤ ik, aT}

∪ {(a,λ) → (a,a1)(a1,a2) ... (ak,λ) ∣ (a, a1a2 ... ak,λ) ∈ I,

vagy (λ, a1a2 ... ak,λ) ∈ I, k ≥ 1, aiT, 1 ≤ ik, aT}

∪ {(λ,a) → a, (a,λ) → λ ∣ aT}

∪ {(a,b) → ba,bT}.

Az Sx alakú szabályok és a H terminálisokat bevezető szabályai segítségével levezethetjük az axiómahalmaz szavait. A H megfelelő szabályai éppen az I szabályait szimulálják. Az (a,b) nemterminális szimbólumok, az aktuális mondatformában az eredeti beszúró-törlő rendszer eredeti levezetésében szereplő szó egymás melletti betűpárjait jelzik, míg a (λ,a), és (a,λ) nemterminálisok lehetővé teszik az (u, x, v) beszúrószabály alkalmazásának szimulálását azokban az esetekben, ahol u = λ, vagy v = λ, illetve az aktuális mondatforma végén. Ezek alapján belátható, hogy L(B) = L(G), és ennek megfelelően L(B) ∈ CF.

QED.

35. Példa. Tekintsük a 33. példában használt B = ({a,b},{a,b},{ab}, {(a,ab,b)}, ∅) rendszert. Ekkor legyen G = (N, T, S, H), ahol:

N = {S, (λ,a), (λ,b), (a,a), (a,b), (b,a), (b,b), (a,λ), (b,λ)},

T = {a,b},

H = {S → (λ,a)(a,b)(b,λ), (a,b) → (a,a)(a,b)(b,b), (λ,a) → a, (λ,b) → b,

(a,λ) → λ, (b,λ) → λ, (a,a) → a, (a,b) → b, (b,a) → a, (b,b) → b}.

42. Feladat. Tekintsük a 40. feladatban szereplő B beszúró-törlő rendszert. Készítsük el a tételben megadott konstrukciónak megfelelően azt a környezetfüggetlen nyelvtant, amely ekvivalens B-vel.

A csak beszúrást használó rendszerek leíróereje tehát bár sok rendkívül összetett, nem környezetfüggetlen nyelv definiálására is elég, nem elegendő néhány viszonylag egyszerű lineáris nyelv definiálására.

Itt a környezet hossza alapján a definiálható nyelvosztályokra egy végtelen hierarchiát is felírhatunk:

FIN ⊊ ... ⊊ CS.

További érdekes eredmények, melyeket bizonyítás nélkül mutatunk be a REG és CF nyelvosztályok és a beszúró-törlő rendszerek kapcsán [Verlan]:

26. Tétel. Fennállnak a következő relációk:

1. REG.

2. CF.

3. CF.

Korlátlan súlyú beszúró-törlő rendszereket használva könnyen jellemezhetjük a rekurzívan felsorolható nyelveket, sőt az egész RE nyelvosztályt definiálhatjuk már relatíve kis súlyokkal is. A következőkben néhány ilyen eredményt mutatunk be, az első esetben a bizonyítást is mutatjuk.

27. Tétel.

Bizonyítás: Legyen LT* az a nyelv, amit a Kuroda normálformájú 0. típusú G = (N, T, S, H) nyelvtan generál. Ekkor konstruáljuk a B beszúró-törlő rendszert a következőképpen:

B = (NT ∪ {E, K1, K2}, T, {SEE}, I, D),

I = {(X, K1x, α1α2) ∣ XxH, x ∈ (NT)*, α1, α2NT ∪ {E}}

∪ {(XY, K2UZ, α1α2) ∣ XYUZH, α1, α2NT ∪ {E}}

D = {(λ, XK1, λ) ∣ XN} ∪ {(λ, XYK2, λ) ∣ X,YN} ∪ {(λ, EE, λ)}.

A beszúró szabályoknál mindig beszúrunk egy K1, vagy egy K2 szimbólumot, attól függően, hogy környezetfüggetlen, vagy nem környezetfüggetlen szabályt szimulálunk: egy vagy két nemterminálist írnánk át a levezetésben. Továbbá mindig ellenőrizzük, hogy a beszúrt szimbólumok után két olyan jel következik, ami nem K1 és/vagy K2. Azért, hogy ez kezdetben is fennálljon az axiómában a mondatszimbólumot két E követi. Ezek az utolsó törlő szabály alkalmazásával bármikor törölhetőek. A K1 és a K2 olyan szimbólumok a már átírt nemterminálisok jelölésére szolgálnak, amik a törlésekkor játszanak fontos szerepet: a K1 az előtte levő nemterminális szimbólumot, míg a K2 az előtte levő két nemterminális szimbólumot tudja magával együtt kitörölni. Azért, hogy nehogy egy már ilyen a generálásban felhasznált nemterminálist újra felhasználhassunk, vagyis környezetként újra figyelembe vehessünk, írjuk utánuk a megfelelő K szimbólumot. A beszúró szabályok csak ott használhatóak, ahol még nincs ilyen jel a kiválasztott nemterminális(ok) után.

Így a beszúró szabályok éppen a H szimulálására képesek. A törlő szabályokkal pedig eltávolíthatjuk a feleslegessé vált nemterminálisokat. Ezek alapján L(G) = L(B). Mivel tetszőleges RE-beli nyelv generálható megadott alakú nyelvtannal, az rendszerekkel is minden rekurzívan felsorolható nyelv generálható.

QED.

Elméleti szempontból fontos, hogy milyen minimális súlyok elegendőek arra, hogy az adott korlátokat teljesítő rendszerek már a teljes RE leírására képesek legyenek. A már tudottan RE nyelvcsalád definiálására képes beszúró-törlő rendszereket a következő tételben mutatjuk be.

28. Tétel. A következő beszúró-törlő nyelvcsaládok megegyeznek a rekurzívan felsorolható nyelvek RE családjával:

Világos, hogy a 11. Lemma miatt minden olyan rendszer, ahol valamely egy vagy több paraméter értéke nagyobb az előző listában ismertetettnél, ugyancsak az RE leírására képes.

Ezen eredmények bizonyítása általában a rekurzívan felsorolható nyelvosztályhoz, a mondatszerkezetű nyelvtanokra vonatkozó Kuroda, Penttonen, vagy Geffert normálalak szimulálásával történik.

Látható, hogy már viszonylag kis súlyokkal is előállítható, minden RE-beli nyelv. Érdekesek a környezetfüggetlen rendszerekre vonatkozó eredmények, illetve az (1,1;1,1) súlyrendszer használata is.

A beszúró-törlő rendszerek egy olyan formális számítási modell családot alkotnak, amelynek kísérleti megvalósításáról nem tudunk. Ezért inkább elméleti jelentőségűnek tarjuk ezeket az eredményeket, hiszen a formális (esetleg természetes) nyelvek (egy részének) ilyen módszerekkel, azaz a beszúrás és a törlés alapműveletekkel történő előállítása, ugyancsak jó alternatívát jelenthet a generatív módszerek (pl. generatív nyelvtanok, ahol átíró, helyettesítő szabályok alkalmazásával generálhatjuk a nyelv szavait) mellett, hasonlóan pl. a 5.2. alfejezetben bemutatott ragasztórendszerekhez is (ahol a ragasztás volt a szóképzés alapművelete) és a H-rendszerekhez (7. fejezet), ahol a szétvágás és összeillesztés műveletekkel folyik a nyelv előállítása.