„Formális nyelvtan” változatai közötti eltérés

[nem ellenőrzött változat][nem ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
a Visszaállítottam a lap korábbi változatát: Peti610bot (vita) szerkesztéséről VolkovBot szerkesztésére
Opa (vitalap | szerkesztései)
67. sor:
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ák 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 hierachia]]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üggetelen nyelvtanok a jól ismert algoritmusokat megvalósító [[LL elemző]]k és [[LR elemző]]k segítségével elemezhetők hatékonyan.