Benutzer-Werkzeuge

Webseiten-Werkzeuge


glossar:kontextfreie_grammatik

kontextfreie Grammatik

engl.: context-free grammar

Bedeutung

Seien T und N zwei disjunkte Alphabete. Die Elemente von T nennen wir Terminalsymbole, die von N Nichtterminalsymbole.

Sei ⊓ eine endliche Teilmenge von N × (N ∪ T )* ; die Elemente von ⊓ heißen Produktionen oder Regeln.

Sei S ∈ N; S heißt Startsymbol oder Axiom. Dann heißt Γ = (N, T , Π, S) eine kontextfreie Grammatik, kurz kfG.

Bemerkungen

  • Mit kfGn lassen sich genau die Sprachen definieren, die man auch mit Syntaxdiagrammen definieren kann.
glossar/kontextfreie_grammatik.txt · Zuletzt geändert: 2015/10/05 16:55 (Externe Bearbeitung)