Bezkontextová gramatika

Z Wikipedie, otevřené encyklopedie

V lingvistice a informatice označuje pojem bezkontextová gramatika (CFG) formální gramatiku, ve které mají všechna pravidla tvar

V → w

kde V je neterminál a w je řetězec terminálů a/nebo neterminálů. Název „bezkontextová“ vychází ze skutečnosti, že neterminál se může přepsat na w bez ohledu na okolní kontext. Jazyky generované bezkontextovými gramatikami se nazývají bezkontextové. Bezkontextová gramatika je speciálním případem gramatiky kontextové (kontext je prázdný).

[editovat] Příklad

Tato bezkontextová gramatika generuje aritmetické výrazy s proměnnými x, y, z:

S → x | y | z | S + S | S - S | S * S | S/S | (S)

Může například vygenerovat řetězec „( x + y ) * x - z * y / ( x + x )“.