6. fejezet - Lineáris nyelvek

A Chomsky-féle nyelvcsaládok közt a 3. (reguláris) és a 2. (környezetfüggetlen) között elhelyezkedő nyelvcsalád. Definíció szerint egy nyelvtan akkor lineáris, ha környezetfüggetlen és minden szabály jobb oldalán maximum egy nemterminális áll.

6.1. példa - A kétbetűs ábécé feletti palindrómák (vagy tükörszavak) nyelvét generáló lineáris nyelvtan

Palindromák (olyan szavak amelyek visszafele olvasva megegyeznek saját magukkal) nyelve a következő lineáris nyelvtannal generáló: ({S}, {a, b}, S, {Sλ, Sa, S → b, Sa S a, Sb S b}). ★


6.2. példa - 0 n 1 n nyelv - Gyakorló feladat

Generáljuk az {0 n 1 n } nyelvet lineáris nyelvtannal. ★


A levezetéseket fagráfokkal reprezentálhatjuk itt is, hasonlóan a reguláris nyelveknél látott fákhoz, azzal a különbséggel, hogy a főág (a nemterminálisok ága) mellett mindkét oldalon vezethetünk be terminális szimbólumokat egy általános lineáris nyelvtan esetén. A következő ábrán egy ilyen levezetési fa található.

6.1. Normálforma

10. Definíció. Egy lineáris nyelvtant gyenge normálformájúnak mondunk, ha minden szabályára a következő alakok egyike teljesül A → a B, A → B a, A → a, A  → B, A → λ (aT;A, BN). ★

35. Tétel. Minden lineáris nyelv generálható gyenge normálformájú nyelvtannal.

Bizonyítás. Hasonlóan a reguláris nyelvtanok esetéhez, itt is új nemterminálisok bevezetése segítségével helyettesítjük a hosszabb szabályokat rövidebbekkel. A → λ alakúak kiküszöbölhetőek az üresszó lemma alapján, A → B alakúak is kiküszöbölhetőek a reguláris normálalaknál ismertetett módon. ∎

Az így kapott, csak A → a B, A → B a, A → a alakú szabályokat tartalmazó lineáris nyelvtanokat, erős normálformájúnak nevezzük (itt minden lépésben pontosan egy terminális kerül levezetésre).

36. Tétel. Minden lineáris nyelvtanhoz van vele ekvivalens (a generált nyelv legfeljebb az üres-szóban különbözik), amely erős normálformájú.

A fenti, levezetési fát ábrázoló ábrán a palindromák nyelvét generáló erős normálformában levő nyelvtanban példa levezetésként az a b b a b b a szót vezettük le.

6.3. példa - Erős lineáris normálalak 1. példa


Adjunk meg a G=({S,A,B},{a,b},S,H)
H={ S → ababA, A → Bbba, B → aaSbab, B → b, A → abba, A → B, B → S }

nyelvtannal ekvivalens erős lineáris normálalakú nyelvtant!
 



Megoldás:

(I.)
Első lépésben megadunk egy G
            1 nyelvtant, ami ekvivalens a G nyelvtannal és nem szerepelnek benne
Y → y
            1
            y
            2
             ...yn,

            Y → y
            1
            y
            2
             ...Yn,

            Y → Y
            1
            y
            2
             ...yn
            
n ≥ 3 alakú szabályok.
H szabályhalmaz ilyen alakú szabályait helyettesítjük új szabályokkal, a többi szabályt
pedig változtatás nélkül átvesszük a H
            1 szabályhalmazba.

Minden Y → y
            1
            y
            2
             ...yn
            
n ≥ 3 alakú szabályhoz
vezessünk be Z
            1
            ,Z
            2
            , ...,Z
            
               n-1
 új
nemterminálisokat, ahol Zi
            
 szerepe az, hogy belőle vezetjük le az y
            
               i+1

             ...yn
            
 szót! Ezek
után az összes Y → y
            1
            y
            2
             ...yn
            
n ≥ 3 alakú
szabályt helyettesítsük a következő szabályokkal:

Y → y
            1
            Z
            1
            ,

            Z
            1
             → y
            2
            Z
            2
            ,

.
.
.

Z
            
               n-2

             → y
            
               n-1

            Z
            
               n-1

            ,

            Z
            
               n-1

             → yn.

Minden Y → y
            1
            y
            2
             ...Yn
            
n ≥ 3 alakú szabályhoz
vezessünk be Z
            1
            ,Z
            2
            , ...,Z
            
               n-2
 új
nemterminálisokat, ahol Zi
            
 szerepe az, hogy belőle vezetjük le az y
            
               i+1

             ...Yn
            
 szót! Ezek
után az összes Y → y
            1
            y
            2
             ...Yn
            
n ≥ 3 alakú
szabályt helyettesítsük a következő szabályokkal:

Y → y
            1
            Z
            1
            ,

            Z
            1
             → y
            2
            Z
            2
            ,

.
.
.

Z
            
               n-3

             → y
            
               n-2

            Z
            
               n-2

            ,

            Z
            
               n-2

             → y
            
               n-1

            Yn.

Minden Y → Y
            1
            y
            2
             ...yn
            
n ≥ 3 alakú szabályhoz
vezessünk be Z
            1
            ,Z
            2
            , ...,Z
            
               n-2
 új
nemterminálisokat, ahol Zi
            
 szerepe az, hogy belőle vezetjük le az  Y
            1
            y
            2 ...yn-i
            
 szót!
                Tehát az összes Y → Y
            1
            y
            2
             ...yn
            
n ≥ 3 alakú
szabályt helyettesítsük a következő szabályokkal:

Y → Z
            1
            yn,

            Z
            1
             → Z
            2
            y
            
               n-1

            ,

.
.
.

Z
            
               n-3

             → Z
            
               n-2

            y
            3
            ,

            Z
            
               n-2

             → Y
            1
            y
            2
            .

Jelen esetben:
G
            1
            =({S,A,B,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5
            ,Z
            6
            ,Z
            7
            ,Z
            8},{a,b},S,H
            1).

            H
            1
            ={ S → aZ
            4
            , Z
            4
             → bZ
            5
            , Z
            5
             → aZ
            6
            , Z
            6
             → bA, A → Z
            7
            a, Z
            7
             → Z
            8
            b, Z
            8
             → Bb, B → aaSbab,

            B → b, A → aZ
            1
            , Z
            1
             → bZ
            2
            , Z
            2
             → bZ
            3
            , Z
            3
             → a, A → B, B → S }

(II.)Második lépésben megadunk egy G
            2 nyelvtant, ami
ekvivalens a G
            1 nyelvtannal és lineáris normálalakú.
G
            1 nyelvtanból indulunk ki. A H
            1 szabályhalmaz
Y → y
            1
            y
            2
             ...y
            
               k-1

            Yky
            
               k+1

             ...yn
            
n ≥ 3
alakú szabályait helyettesítjük új szabályokkal, a többi szabályt pedig
változtatás nélkül átvesszük a H
            2 szabályhalmazba.
Minden Y → y
            1
            y
            2
             ...y
            
               k-1

            Yky
            
               k+1

             ...yn
            
n ≥ 3
alakú szabályhoz vezessünk be Z
            1
            ,Z
            2
            , ...,Z
            
               n-1
 új nemterminálisokat!
Ezek után az összes Y → y
            1
            y
            2
             ...y
            
               k-1

            Yky
            
               k+1

             ...yn
            
n ≥ 3
alakú szabályt helyettesítsük a következő szabályokkal:

Y → y
            1
            Z
            1
            ,


            Z
            1
             → y
            2
            Z
            2
            ,

.
.
.

Z
            
               k-2

             → y
            
               k-1

            Z
            
               k-1

            ,

            Z
            
               k-1

             → Zkyn,

            Zk → Z
            
               k+1

            y
            
               n-1

            ,

.
.
.

Z
            
               n-2

             → Z
            
               n-1

            y
            
               k+2

            ,

            Z
            
               n-1

             → Yky
            
               k+1

            .

Jelen esetben:
G
            2
            =({S,A,B,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5
            ,Z
            6
            ,Z
            7
            ,Z
            8
            ,Z
            9
            ,Z
            10
            ,Z
            11
            ,Z
            12},{a,b},S,H
            2).

            H
            2
            ={ S → aZ
            4
            , Z
            4
             → bZ
            5
            , Z
            5
             → aZ
            6
            , Z
            6
             → bA, A → Z
            7
            a, Z
            7
             → Z
            8
            b, Z
            8
             → Bb, B → aZ
            9
            , Z
            9
             → aZ
            10
            ,

            Z
            10
             → Z
            11
            b, Z
            11
             → Z
            12
            a, Z
            12
             → Sb, B → b, A → aZ
            1
            , Z
            1
             → bZ
            2
            , Z
            2
             → bZ
            3
            , Z
            3
             → a, A → B, B → S }

(III.) Harmadik lépésben megadjuk az eredeti nyelvtannal ekvivalens G' erős lineáris normálalakú nyelvtant.
Ehhez két lépésre van szükség. Első lépésben meghatározunk egy U(Z) halmazt minden
olyan Z nemterminálishoz, mely levezethető legalább egy másik nemterminálisból a G
            2 nyelvtanban és
szerepel olyan H
            2 halmazban lévő szabály bal oldalán,
amelynek jobb oldalán egy terminális vagy pedig egy terminális és egy nemterminális betű áll.
Az U(Z) halmaz tartalmazni fogja az összes olyan nemterminálist,
melyből egy vagy több lépésben levezethető a Z betű.

Jelen esetben:
U(B)={A},U(S)={B,A}.
Második lépésben a H' szabályhalmazba átvesszük a H
            2 szabályhalmaz
mindazon szabályait, melyek jobb oldalán egy terminális betű vagy pedig egy
terminális és egy nemterminális található, majd hozzávesszük mindazon szabályokat,
melyeket úgy kapunk, hogy a már átvett szabályok bal oldalán szereplő betűt
a hozzá tartozó U halmaz elemeivel helyettesítjük.

Formálisan:
H'=(H
            2∪{W → p|Z → p∈ H
            2
            ,W∈ U(Z)})∖{X → Y|X,YN}.
Jelen esetben:
G'=({S,A,B,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5
            ,Z
            6
            ,Z
            7
            ,Z
            8
            ,Z
            9
            ,Z
            10
            ,Z
            11
            ,Z
            12},{a,b},S,H').

            H'={ S → aZ
            4
            , B → aZ
            4
            , A → aZ
            4
            , Z
            4
             → bZ
            5
            , Z
            5
             → aZ
            6
            , Z
            6
             → bA, A → Z
            7
            a, Z
            7
             → Z
            8
            b, Z
            8
             → Bb, B → aZ
            9
            ,

            A → aZ
            9
            , Z
            9
             → aZ
            10
            , Z
            10
             → Z
            11
            b, Z
            11
             → Z
            12
            a, Z
            12
             → Sb, B → b, A → b, A → aZ
            1
            , Z
            1
             → bZ
            2
            , Z
            2
             → bZ
            3
            ,
Z

            3
             → a } ★
 

6.4. példa - Erős lineáris normálalak 2. feladat


Adjunk meg a G=({S,A,B},{x,y,z},S,H)
H={ S → Bxxx, B → xyAyx, A → B, A → S, A → z }

nyelvtannal ekvivalens erős lineáris normálalakú nyelvtant!
 



Megoldás:
(I.)
G
            1
            =({S,A,B,Z
            1
            ,Z
            2},{x,y,z},S,H
            1).

            H
            1
            ={ S → Z
            1
            x, Z
            1
             → Z
            2
            x, Z
            2
             → Bx, B → xyAyx, A → B, A → S, A → z }
(II.)
G
            2
            =({S,A,B,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5},{x,y,z},S,H
            2).

            H
            2
            ={ S → Z
            1
            x, Z
            1
             → Z
            2
            x, Z
            2
             → Bx, B → xZ
            3
            , Z
            3
             → yZ
            4
            , Z
            4
             → Z
            5
            x, Z
            5
             → Ay, A → B, A → S, A → z }
(III.)
U(B)={A},U(S)={A}.

            G'=({S,A,B,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5},{x,y,z},S,H').

            H'={ S → Z
            1
            x,A → Z
            1
            x, Z
            1
             → Z
            2
            x, Z
            2
             → Bx, B → xZ
            3
            , A → xZ
            3
            , Z
            3
             → yZ
            4
            , Z
            4
             → Z
            5
            x, Z
            5
             → Ay, A → z } ★
 

6.5. példa - Erős lineáris normálalak 3. feladat


Adjunk meg a G=({S,A},{x,y,z},S,H)
H={ S → xSx, S → A, A → yAy, A → z }

nyelvtannal ekvivalens erős lineáris normálalakú nyelvtant!
 




Megoldás:
(I.)
 Mivel a G nyelvtanban nincsenek Y → y
            1
            y
            2
             ... yn, Y → y
            1
            y
            2
             ... Yn, Y → Y
            1
            y
            2
             ... yn
            
n ≥ 3
alakú szabályok, ezért G
            1
            =G.

(II.)
 G
            2
            =({S,A,Z
            1
            ,Z
            2},{x,y,z},S,H
            2).

            H
            2
            ={ S → xZ
            1
            , Z
            1
             → Sx, S → A, A → yZ
            2
            , Z
            2
             → Ay, A → z }
(III.)
U(A)={S}.

            G'=({S,A,B,Z
            1
            ,Z
            2},{x,y,z},S,H').

            H'={ S → xZ
            1
            , Z
            1
             → Sx, A → yZ
            2
            , S → yZ
            2
            , Z
            2
             → Ay, A → z, S → z } ★
 

6.6. példa - Erős lineáris normálalak 4. feladat


Adjunk meg a G=({S,X,Y},{x,y,z},S,H)
H={ S → Xxx, S → yyY, S → zzz, X → xS, Y → Sy, X → S, Y → S }

nyelvtannal ekvivalens erős lineáris normálalakú nyelvtant!
 



Megoldás:

(I.)
G
            1
            =({S,X,Y,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4},{x,y,z},S,H
            1).

            H
            1
            ={ S → Z
            1
            x, Z
            1
             → Xx, S → yZ
            2
            , Z
            2
             → yY, S → zZ
            3
            , Z
            3
             → zZ
            4
            , Z
            4
             → z, X → xS, Y → Sy, X → S, Y → S }

(II.) Mivel a G
            1 nyelvtanban nincs Y → y
            1
            y
            2
             ... y
            
               k-1

            Yky
            
               k+1

             ... yn
            
n ≥ 3 alakú szabály, ezért G
            2
            =G
            1.

(III.)
U(S)={X,Y}.

            G'=({S,A,B,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4},{x,y,z},S,H').

            H'={ S → Z
            1
            x,X → Z
            1
            x,Y → Z
            1
            x, Z
            1
             → Xx, S → yZ
            2
            ,X → yZ
            2
            , Y → yZ
            2
            , Z
            2
             → yY, S → zZ
            3
            ,

            X → zZ
            3
            , Y → zZ
            3
            , Z
            3
             → zZ
            4
            , Z
            4
             → z, X → xS, Y → Sy } ★
 

6.7. példa - Erős lineáris normálalak 5. feladat


Adjunk meg a G=({S,A,B},{x,y},S,H)
H={ S → yyAxx, A → xxB, B → Syy, S → xxyy }

nyelvtannal ekvivalens erős lineáris normálalakú nyelvtant!
 



Megoldás:
(I.)
G
            1
            =({S,A,B,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5},{x,y},S,H
            1).

            H
            1
            ={ S → yyAxx, A → xZ
            1
            , Z
            1
             → xB, B → Z
            2
            y, Z
            2
             → Sy, S → xZ
            3
             S → xZ
            4
             S → yZ
            5
             Z
            5
             → y }
 
(II.)
G
            2
            =({S,A,B,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5
            ,Z
            6
            ,Z
            7
            ,Z
            8},{x,y,z},S,H
            2).

            H
            2
            ={ S → yZ
            6
            , Z
            6
             → y,Z
            7
             Z
            7
             → Z
            8
            x, Z
            8
             → Ax, A → xZ
            1
            , Z
            1
             → xB, B → Z
            2
            y, Z
            2
             → Sy, S → xZ
            3
            , S → xZ
            4
            ,

            S → yZ
            5
            , Z
            5
             → y }

(III.)
Mivel a G
            2 nyelvtan már erős lineáris normálalakú, ezért G'=G
            2. ★

 

6.8. példa - Erős lineáris normálalak 6. feladat


Adjunk meg a G=({S,A,B},{x,y},S,H)
H={ S → Bx, B → yA, S → A, A → S, S → z }
nyelvtannal ekvivalens erős lineáris normálalakú nyelvtant!
 



Megoldás:

(I.)
Mivel a G nyelvtanban nincsenek Y → y
            1
            y
            2
             ...yn, Y → y
            1
            y
            2
             ...Yn, Y → Y
            1
            y
            2
             ...yn
            
n ≥ 3
alakú szabályok, ezért G
            1
            =G.


(II.)
Mivel a G
            1 nyelvtanban nincs Y → y
            1
            y
            2
             ...y
            
               k-1

            Yky
            
               k+1

             ...yn
            
n ≥ 3 alakú szabály, ezért G
            2
            =G
            1.


(III.)
U(S)={A}.

            G'=({S,A,B},{x,y,z},S,H').

            H'={ S → Bx, A → Bx, B → yA, S → z, A → z } ★
 

6.9. példa - Erős lineáris normálalak 7. feladat


Adjunk meg a G=({S,A,B},{0,1,+},S,H)
H={ S → 1S0, S → A, S → B, A → 0A1, A → B, B → +, B → S }

nyelvtannal ekvivalens erős lineáris normálalakú nyelvtant!
 



Megoldás:

(I.)
Mivel a G nyelvtanban nincsenek Y → y
            1
            y
            2
             ...yn, Y → y
            1
            y
            2
             ...Yn, Y → Y
            1
            y
            2
             ...yn
            
n ≥ 3
alakú szabályok, ezért G
            1
            =G.


(II.)
G
            1
            =({S,A,B,Z
            1
            ,Z
            2},{0,1,+},S,H
            1)
H
            1
            ={ S → 1Z
            1
            , Z
            1
             → S0, S → A, S → B, A → 0Z
            2
            , Z
            2
             → A1, A → B, B → +, B → S }


(III.)
U(A)={S,B},U(B)={S,A},U(S)={B,A}.

            G'=({S,A,B,Z
            1
            ,Z
            2},{0,1,+},S,H').

            H'={ S → 1Z
            1
            ,B → 1Z
            1
            ,A → 1Z
            1
            , Z
            1
             → S0, A → 0Z
            2
            ,S → 0Z
            2
            ,B → 0Z
            2
            , Z
            2
             → A1, B → +,S → +,A → + } ★
 

Most egy pillanatra lépjünk vissza: a reguláris nyelvek speciális lineáris nyelvek, amelyek generálhatók olyan lineáris nyelvtannal, hogy minden Au B v alakú szabályában v=λ (azaz a nyelvtan jobb-lineáris). Itt jegyezzük meg, hogy a szakirodalomban előforduló jobb-lineáris nyelvtan mellett előfordul a bal-lineáris kifejezés is (ez megfelel a mi reguláris nyelvtan definíciónk szimmetrikus alakjának): ha a szabályok alakja csak A → v és A → B v lehet, ahol A, BN, vT *. Érdekes kérdés hogy milyen a bal-lineáris nyelvek és a reguláris (vagyis jobb-lineáris) nyelvek viszonya.

37. Tétel. A bal-lineáris nyelvtanokkal generált nyelvek osztálya egybeesik a reguláris nyelvek osztályával.

Bizonyítás. Legyen G=(N, T, S, H) bal-lineáris nyelvtan, legyen N={S, A 1, A 2, …, A n }. Az általánosság csorbítása nélkül feltehetjük, hogy S nem szerepel egyetlen szabály jobb oldalán sem. Szerkesszük meg a G '=(N ', T, S ', H ') nyelvtant úgy, hogy N '={S ', B 1, …, B n } és a H '- beli szabályok a következők:

- S ' → vH ', ha S → vH és vT *,

- S ' → v B k H ', ha A k vH és vT *,

- B j v B k H ', ha A k A j vH és vT *,

- B j vH ', ha SA j vH és vT *.

Az így kapott G ' nyelvtan nyilván reguláris, és belátható, hogy L(G)=L(G '): Legyen wL(G). Ha S → wH, akkor S ' → wH '. Ha pedig létezik egy SA i,1 v 1A i,2 v 2 v 1⇒…⇒A i,m-1 v m-1v 1v m v m-1v 1 alakú levezetés G- ben, ahol v 1, v 2, …, v m T *, akkor G '- ben ezzel analóg módon megadható egy Sv m B i, m-1v m v m-1 B i, m-2⇒…⇒v m v 2 B i, 1v m v m-1v 2 v 1 alakú levezetés, tehát wL(G '). Megfordítva ugyanígy belátható, hogy L(G ')⊆L(G). ∎

Fordított konstrukcióval pedig éppen az bizonyítható, hogy minden reguláris nyelv generálható bal-lineáris módon is. (Ez egyébként automatanyelven megfelel annak, mintha egy végállapotból visszafelé haladva fogadnánk el a szót olyan módon, hogy végül a kezdőállapotba érkezzünk.)

Itt jegyezzük meg az előző tétel és konstrukciók egy azonnali következményét:

A reguláris nyelvek halmaza zárt a tükrözésre nézve, ahol egy w=a 1 a 2a n szó tükörképén a w -1=a n a 2 a 1 szót értjük (a 1, a 2, …, a n T). Egy L nyelv tükörképén pedig az L 1={w|∃vL, w=v -1} nyelvet.