Kontextfreie Grammatik

Einfache Sprache

Mit eine Kontextfreien Grammatik kann man Sprachen beschreiben, die aus rekursiven Regeln entstehen.

Def. Kontextfreie Grammatik

Eine Kontextfreie Grammatik $\mathcal G$ ist eine Struktur bestehend aus $(T, V, S, P)$, wobei

• $T$ eine endliche nicht-leere Menge von Terminalsymbolen,
• $V$ eine endliche Menge an Variablen mit $V\cap T = \emptyset$,
• $S\in V$ eine Startvariable und
• $P\subset V\times (T\cup V)^*$ eine endliche Menge von Produktionregeln.

Im Kontext von kontextfreien Sprachen schreiben wir $\Sigma := T\cup V$ und $A\to \alpha$ für eine Produktion $\langle A, \alpha\rangle$.

Die zwei grundlegendsten Verfahren um die Zugehörigkeit von Zeichenkette zu einer KFG zu testen. Beide verwenden die Produktionsregeln. Jedoch einmal von der Startvariable zur Zeichenkette, Rekursive Inferenz, und einem umgekehrt, Ableitung.