Formális nyelvtan

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

A formális nyelvtan informatikai értelemben egy absztrakt struktúra, amely pontosan leír egy formális nyelvet. A formális nyelveket, valamint az emberi nyelveket leíró nyelvtanok között bizonyos analógiák figyelhetők meg. A formális nyelvek és formális nyelvtanok vizsgálatának egyik legjelentősebb úttörője Noam Chomsky, akinek a munkássága egyaránt hatott a formális nyelvek és a természetes nyelvek kutatására is.

A formális nyelvtanok két fő kategóriába oszthatók: generatív és analitikus nyelvtanok.

Röviden, egy analitikus nyelvtan leírja, hogyan olvassuk a nyelvet, amíg egy generatív nyelvtan azt írja le, hogyan írjuk.

Generatív nyelvtanok

Egy generatív nyelvtan a jelsorozatok transzformációs szabályait leíró szabályok halmazából áll. A nyelvet alkotó jelsorozatok létrehozásához szükséges, hogy legyen egy egyedi „kezdő” szimbólum, ezután csak a szabályokat kell egymás után alkalmazni (bárhányszor, tetszés szerinti sorrendben) a kezdő szimbólum átalakítására. A nyelv azokból a jelsorozatokból áll, amelyeket az említett módon elő lehet állítani. A szabályok alkalmazásának megengedett lehetőségei közül bármilyen különleges sorrend alkalmazásával az átalakításokkal létrehozhatók jelsorozatok, de ha ezek közül a jelsorozatok közül egyet is többféleképpen is elő lehet állítani, akkor a nyelvtant kétértelműnek nevezik.

Tegyük fel például, hogy egy ábécéhez a ' a {\displaystyle a} ' és a ' b {\displaystyle b} ' szimbólumok tartoznak, a kezdő szimbólum pedig legyen az ' S {\displaystyle S} ' és adottak a következő szabályok:

1. S ⟶ a S b {\displaystyle S\longrightarrow aSb} 2. S ⟶ b a {\displaystyle S\longrightarrow ba}

Kezdő szimbólumunk a „ S {\displaystyle S} ”, de ezután kiválaszthatjuk, hogy melyik szabályt alkalmazzuk a jelsorozat következő elemének előállításához. Ha az 1-es szabályt választjuk, akkor annak alapján az ' S {\displaystyle S} ' szimbólumot a ' a S b {\displaystyle aSb} '-al helyettesítjük, eredményül tehát a „ a S b {\displaystyle aSb} ” jelsorozatot kapjuk. Ha most ismételten az 1-es szabály alkalmazását választjuk, akkor helyettesítjük az ' S {\displaystyle S} ' szimbólumot a ' a S b {\displaystyle aSb} '-vel, és akkor a „ a a S b b {\displaystyle aaSbb} ” jelsorozatot kapjuk. Ezt az eljárást addig ismételhetjük, amíg az ábécé szimbólumai megengedik (esetünkben ' a {\displaystyle a} ' és ' b {\displaystyle b} '). Befejezve a példát, most válasszuk a 2-es szabályt, helyettesítsük az ' S {\displaystyle S} ' szimbólumot a ' b a {\displaystyle ba} ' jelsorozattal, eredményül pedig a „ a a b a b b {\displaystyle aababb} ” jelsorozatot kapjuk, és ezzel be is fejeztük.

Az adott szimbólumokat használva a fentieket sokkal egyszerűbb formában is leírhatjuk: S ⟶ a S b ⟶ a a S b b ⟶ a a b a b b {\displaystyle S\longrightarrow aSb\longrightarrow aaSbb\longrightarrow aababb} .

A nyelvtan által meghatározott nyelv nem lesz más, mint az összes olyan jelsorozat halmaza, amelyeket ezzel az eljárással elő tudunk állítani: { b a , a b a b , a a b a b b , a a a b a b b b , . . . } {\displaystyle \left\{ba,abab,aababb,aaababbb,...\right\}} .

Formális definíció

Noam Chomsky az 1950-es években javasolta először a generatív nyelvtanok klasszikus formalizálását, ami szerint egy G nyelvtan a következő komponensekből áll:

( Σ ∪ N ) ∗ {\displaystyle (\Sigma \cup N)^{*}} beli jelsorozat ⟶ {\displaystyle \longrightarrow } ( Σ ∪ N ) ∗ {\displaystyle (\Sigma \cup N)^{*}} -beli jelsorozat (ahol ∗ {\displaystyle {}^{*}} a Kleene-csillag és ∪ {\displaystyle \cup } az unió művelet) azzal a megkötéssel, hogy a szabály bal oldalának (bal oldali rész a ⟶ {\displaystyle \longrightarrow } előtt) legalább egy nem-terminális szimbólumot tartalmaznia kell.

Gyakran a G {\displaystyle G} formális nyelvtan jelölésé a ( N , Σ , P , S ) {\displaystyle (N,\Sigma ,P,S)} négyessel történik.

A G = ( N , Σ , P , S ) {\displaystyle G=(N,\Sigma ,P,S)} , formális nyelvtannal meghatározott nyelvet jelölik a L ( G ) {\displaystyle {\boldsymbol {L}}(G)} szimbólummal is. Ezzel meghatároznak minden olyan, a Σ {\displaystyle \Sigma } halmazból generálható jelsorozatot, amelyeket a P {\displaystyle P} halmazban lévő produkciós szabályok egymásutáni alkalmazásával a S {\displaystyle S} kezdő szimbólumot kezdőként alkalmazva létrehozható, addig, amíg a nem-terminális szimbólumok készlete rendelkezésre áll.

Példa

A következő példáknál a formális nyelvet a halmaz-felépítő jelölés használatával határozzuk meg.

Például, tételezzük fel a G {\displaystyle G} nyelvtanról, hogy a következőkből áll:

N = { S , B } {\displaystyle N=\left\{S,B\right\}} , Σ = { a , b , c } {\displaystyle \Sigma =\left\{a,b,c\right\}} , P {\displaystyle P} pedig a következő produkciós szabályokat tartalmazza:

1. S ⟶ a B S c {\displaystyle S\longrightarrow aBSc} 2. S ⟶ a b c {\displaystyle S\longrightarrow abc} 3. B a ⟶ a B {\displaystyle Ba\longrightarrow aB} 4. B b ⟶ b b {\displaystyle Bb\longrightarrow bb} ,

és az S {\displaystyle S} nem-terminális szimbólum a kezdő szimbólum.

Néhány példa arra, hogyan származtathatók a jelsorozatok a L ( G ) {\displaystyle {\boldsymbol {L}}(G)} nyelvben:

(a jelsorozatok előállításánál használt produkciós szabály azonosítója a zárójelben van, a helyettesíthető rész pedig vastagon szedett).

Egyértelmű, hogy a fenti nyelvtan meghatározza a { a n b n c n | n > 0 } {\displaystyle \left\{a^{n}b^{n}c^{n}|n>0\right\}} nyelvet, ahol a n {\displaystyle a^{n}} jelöli azt a jelsorozatot, amely n darab a {\displaystyle a} -ból áll. Következésképpen, az egész nyelv bármilyen pozitív számú 'a'-t követő azonos számú 'b'-ből és azonos számú 'c'-ből álló jelsorozatból áll.

A generatív formális nyelvtanok identikusak a Lindenmayer rendszerekkel (L-rendszerek), kivéve, hogy az L-rendszerekben nincsen különbség a terminálisok és s nem-terminálisok között, valamint az L-rendszerek megszorítást tartalmaznak a szabályok alkalmazásának sorrendjére, és az L-rendszerek nem állnak le, ezért végtelen jelsorozat szekvenciákat generálnak.

A Chomsky-féle hierarchia

Amikor az 1950-es években Noam Chomsky először formalizálta a generatív nyelvtanokat, akkor négy típusba sorolta be azokat. Ezek a csoportok ma Chomsky-féle hierarchiaként ismertek. Az egyes típusok között a különbség a produkciós szabályok szigorúságában jelenik meg. Két fontos típus a környezetfüggetlen nyelvtanok és a szabályos nyelvtanok. Azok a nyelvek, amelyek valamilyen nyelvtannal leírhatók azok az úgynevezett környezetfüggetlen nyelvek illetőleg a szabályos nyelvek. Habár kevésbé hatékonyak, mint a megkötés nélküli nyelvtanok, amelyek ténylegesen le tudnak írni bármilyen nyelvet, amelyek a Turing-gépekkel elfogadhatóak, ezen megkötések miatt inkább az ilyen nyelvtanok hatékonyan elemzők segítségével valósíthatók meg. Például, a környezetfüggetlen nyelvtanok a jól ismert algoritmusokat megvalósító LL elemzők és LR elemzők segítségével elemezhetők hatékonyan.

  Nyelvtanok Nyelvek Automaták Produkciós szabályok
0. nyelvosztály Rekurzívan megszámlálható Rekurzívan megszámlálható Turing-gép Nincs megkötés
1. nyelvosztály környezetfüggő környezetfüggő Korlátos nem determinisztikus Turing-gép α A β → α γ β {\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }
2. nyelvosztály környezetfüggetlen környezetfüggetlen Nem determinisztikus veremautomata A → γ {\displaystyle A\rightarrow \gamma }
3. nyelvosztály Szabályos Szabályos Véges determinisztikus automata A → a {\displaystyle A\rightarrow a} és

egyébként A → a B {\displaystyle A\rightarrow aB}
vagy A → B a {\displaystyle A\rightarrow Ba}

Környezetfüggetlen nyelvtanok

A környezetfüggetlen nyelvtanok esetében, a produkciós szabályok bal oldalán csak egy egymagában álló nem-terminális szimbólum lehet. Az előzőekben meghatározott nyelv nem volt környezetfüggetlen nyelv. Környezetfüggetlen nyelv viszont a { a n b n | n > 0 } {\displaystyle \left\{a^{n}b^{n}|n>0\right\}} (bármely pozitív számú 'a'-t azonos számú 'b' követ) nyelv, amelynek G 2 {\displaystyle G2} a nyelvtana és az N = { S } {\displaystyle N=\left\{S\right\}} , Σ = { a , b } {\displaystyle \Sigma =\left\{a,b\right\}} , és S {\displaystyle S} a kezdő szimbólumok határoznak meg, valamint a következő produkciós szabályok:

1. S ⟶ a S b {\displaystyle S\longrightarrow aSb} 2. S ⟶ a b {\displaystyle S\longrightarrow ab} Reguláris (szabályos) nyelvtanok

A reguláris nyelvtanokban, a bal oldalon szintén csak egy egyedülálló nem-terminális szimbólum állhat, de most a jobb oldalra is megkötést kell tenni: lehet üres, lehet egyetlen terminális szimbólum és lehet egy egyedül álló terminális szimbólumot követő nem-terminális szimbólum. (Néha egy tágabb meghatározás használatos: megengedett egy eset a következők közül: vagy terminálisok hosszabb jelsorozata vagy egy egyedül álló, önálló nem-terminális.)

Az előzőekben meghatározott nyelv nem reguláris, de a { a n b m | m , n > 0 } {\displaystyle \left\{a^{n}b^{m}|m,n>0\right\}} nyelv (bármilyen pozitív számú 'a'-kat követő bármilyen pozitív számú 'b'-k, ahol a számok különbözőek is lehetnek) már reguláris, és meghatározható a G 3 {\displaystyle G3} nyelvtannal, ami az N = { S , A , B } {\displaystyle N=\left\{S,A,B\right\}} , Σ = { a , b } {\displaystyle \Sigma =\left\{a,b\right\}} , és a S {\displaystyle S} kezdő szimbólummal, valamint a következő produkciós szabályokkal van meghatározva:

1. S ⟶ a A {\displaystyle S\longrightarrow aA} 2. A ⟶ a A {\displaystyle A\longrightarrow aA} 3. A ⟶ b B {\displaystyle A\longrightarrow bB} 4. B ⟶ b B {\displaystyle B\longrightarrow bB} 5. B ⟶ ϵ {\displaystyle B\longrightarrow \epsilon }

A gyakorlatban a reguláris nyelvtanok leírására reguláris kifejezéseket (szabályos kifejezéseket) használnak.

Szabályos- és környezetfüggetlen nyelvek összehasonlítása

A produkció szabályok különbözősége oldaláról a kétfajta nyelv közötti alapvető különbség az { a n b n | n > 0 } {\displaystyle \left\{a^{n}b^{n}|n>0\right\}} (környezetfüggetlen) és az { a n b m | n , m > 0 } {\displaystyle \left\{a^{n}b^{m}|n,m>0\right\}} (szabályos) között az, hogy a környezetfüggetlen nyelv esetén az 'a'-k és a 'b'-k száma azonos kell, hogy legyen. Ennélfogva, bármilyen automata segítségével történő környezetfüggetlen nyelv felismerésének megkísérlésekor elengedhetetlenül szükséges, hogy több információt kell figyelembe venni, mint a szabályos nyelv esetében. A továbbiakban nem kell foglalkoznunk az 'a'-k vagy a 'b'-k számával, viszont fel kell tételeznünk, hogy a számuk nullánál nagyobb.

A részleteket lásd a környezetfüggetlen nyelv és szabályos nyelv szócikkek alatt.

A generatív nyelvtanok egyéb formái

A formális nyelvtanok eredeti Chomsky-féle hierarchiájának legtöbb kiterjesztésének és változatának kifejlesztését a nyelvészek és a számítógép-tudomány képviselői nemrégen végezték el, mindketten általában azzal a céllal, hogy az elemzők teljesítményét megnöveljék. Természetesen ezek a célok sajátságos eredményeket hoztak: minél kifejezőbb nyelvtani formalizmusok, az automatizált eszközök egyre nehezebben használhatók az elemzéseknél. A nyelvtanok néhány formája ezen sajátos eredményekre tekintettel került kifejlesztésre:

Analitikus nyelvtanok

Habár a rendelkezésre álló elemző algoritmusokkal foglalkozó irodalom igen terjedelmes, ezek közül az algoritmusok közül a legtöbb azt feltételezi, hogy az elemzendő nyelv leírása egy generatív formális nyelvtant jelent, és az a cél, hogy átalakítsa ezt a generatív nyelvtant egy működő elemzővé. Egy másik lehetséges megközelítés a nyelvet elsődlegesen egy analitikus nyelvtannal formalizálja, amely sokkal közvetlenebb kapcsolatot biztosít az elemző és az elemzendő nyelv struktúrája között. Az analitikus nyelvtanokkal történő formalizálást mutatja be a következő néhány példa:

Nemzetközi katalógusok