|
== 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ő"„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ű nyelvtan|kétértelmű]]nek nevezik.
Tegyük fel például, hogy egy ábécéhez a '<math>a</math>' és a '<math>b</math>' szimbólumok tartoznak, a kezdő szimbólum pedig legyen az '<math>S</math>' és adottak a következő szabályok:
: 2. <math>S \longrightarrow ba</math>
Kezdő szimbólumunk a "„<math>S</math>"”, 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 '<math>S</math>' szimbólumot a '<math>aSb</math>'-al helyettesítjük, eredményül tehát a "„<math>aSb</math>"” jelsorozatot kapjuk. Ha most ismételten az 1-es szabály alkalmazását választjuk, akkor helyettesítjük az '<math>S</math>' szimbólumot a '<math>aSb</math>'-al, és akkor a "„<math>aaSbb</math>"” jelsorozatot kapjuk. Ezt az eljárást addig ismételhetjük, amíg az ábécé szimbólumai megengedik (esetünkben '<math>a</math>' és '<math>b</math>'). Befejezve a példát, most válasszuk a 2-es szabályt, helyettesítsük az '<math>S</math>' szimbólumot a '<math>ba</math>' jelsorozattal, eredményül pedig a "„<math>aababb</math>",” jelsorozatot kapjuk, és ezzel be is fejeztük.
Az adott szimbólumokat használva a fentieket sokkal egyszerűbb formában is leírhatjuk: <math>S \longrightarrow aSb \longrightarrow aaSbb \longrightarrow aababb</math>.
Egyértelmű, hogy a fenti nyelvtan meghatározza a <math>\left \{ a^{n}b^{n}c^{n} | n > 0 \right \}</math> nyelvet, ahol <math>a^{n}</math> jelöli azt a jelsorozatot, amely n darab <math>a</math>-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 rendszer]]ekkel (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ánákalkalmazá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 hierachiahierarchia]]ké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 nyelvtan]]ok'' és a ''[[szabályos nyelvtan]]ok''. Azok a nyelvek, amelyek valamilyen nyelvtannal leírhatók azok az úgynevezett ''[[környezetfüggetlen nyelv]]ek'' illetőleg a ''[[szabályos nyelv]]ek''. Habár kevésbé hatékonyak, mint a megkötés nélküli nyelvtanok, amelyek tényleges le tudnak írni bármilyen nyelvet, amelyek a [[Turing-gép]]ekkel 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üggetelenkö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.
<center>
|-
|1. nyelvosztály
|[[környezet függőkörnyezetfüggő nyelvtan|környezet függőkörnyezetfüggő]]
|[[környezet függőkörnyezetfüggő nyelv|környezet függőkörnyezetfüggő]]
|Korlátos nem determinisztikus Turing-gép
|<math>\alpha A\beta \rightarrow \alpha\gamma\beta</math>
==== Környezetfüggetlen nyelvtanok ====
A [[környezetfüggetlen nyelvtan]]ok 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 <math>\left \{ a^{n}b^{n} | n > 0 \right \}</math> (bármely pozitív számú 'a'-t azonos számú 'b' követ) nyelv, amelynek <math>G2</math> a nyelvtana és az <math>N=\left \{S\right \}</math>, <math>\Sigma=\left \{a,b\right \}</math>, és <math>S</math> a kezdő szimbólumok határoznak meg, valamint a követekezőkövetkező produkciós szabályok:
: 1. <math>S \longrightarrow aSb</math>
==== 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ét fajtakétfajta nyelv közötti alapvető különbség az <math>\left \{ a^{n}b^{n} | n > 0 \right \}</math> (környezetfüggetlen) és az <math>\left \{ a^{n}b^{m} | n,m > 0 \right \}</math> (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 [[elméleti automatautomata|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.
| 