környezetfüggetlen nyelvtan (CFG)

Kapcsolódó fogalmak: 
generálóképesség
Kapcsolódó fogalmak: 
záró (vagy terminális) szimbólum
Kapcsolódó fogalmak: 
nem záró szimbólum
Rövid szöveges bemutatás: 
A nyelvtani formalizmusok mindegyike rendelkezik egy generálóképességgel, mely megadja, hogy milyen komplexitású nyelvtant tudunk leírni a segítségükkel. Ezek a nyelvtani formalizmusok hierarchiába szervezhetőek, tehát egy osztály minden olyan nyelvtant ki tud fejezni, melyet egy nála gyengébb osztály is kitud és még néhány nyelvtant. Ebben a hierarchiában a környezetfüggetlen nyelvtan a harmadik szinten áll. A nyelvtani leírásban az A -> B formalizmust kell követni. Bal és jobboldalon is állhat záró és nem záró szimbólum is. A környezetfüggetlen nyelvtan egyetlen kikötése, hogy a bal oldalon egyetlen nem záró szimbólum állhat. A lényege, hogy a szabályok biztosítják minden egyes nem záró szimbólum átírását a jobb oldalra egy tetszőleges környezetbe.