Eine kontextfreie Grammatik (engl. Context-Free Grammar, CFG) ist ein formales System, das verwendet wird, um die Syntax einer Sprache zu beschreiben. Sie ist ein zentraler Begriff in der Theorie formaler Sprachen und wird insbesondere in der Informatik, der Linguistik und der künstlichen Intelligenz eingesetzt. Die Bezeichnung „kontextfrei“ bedeutet, dass die Produktion von Symbolen in der Grammatik nicht vom Kontext abhängt, in dem sie verwendet werden.
Eine kontextfreie Grammatik besteht aus folgenden Komponenten:
- Terminale (Terminalsymbolen): Dies sind die tatsächlichen Wörter oder Symbole, die in der Sprache verwendet werden.
- Nonterminale (Nonterminalsymbolen): Diese repräsentieren Konzepte oder Kategorien, die durch eine Reihe von Regeln in Terminale übersetzt werden können.
- Produktionsregeln: Diese Regeln definieren, wie Nonterminale durch eine Folge von Terminalen und/oder Nonterminalen ersetzt werden können.
Die kontextfreie Grammatik ist besonders wichtig in der Theorie der formellen Sprachen und wird beispielsweise bei der Entwicklung von Compilern und Interpretern verwendet, um die Syntax von Programmiersprachen zu definieren. In der künstlichen Intelligenz spielt sie eine Rolle bei der Verarbeitung natürlicher Sprache, da sie hilft, die Struktur von Sätzen und die Beziehungen zwischen Wörtern zu analysieren.
Ein Beispiel für eine einfache kontextfreie Grammatik könnte wie folgt aussehen:
- Nonterminale: S (Satz), NP (Nomenphrase), VP (Verbphrase), V (Verb), N (Nomen)
- Terminale: „Hund“, „rennt“, „Katze“, „schläft“
- Produktionsregeln:
- S → NP VP
- NP → N
- VP → V NP
- N → „Hund“ | „Katze“
- V → „rennt“ | „schläft“
Diese Grammatik ermöglicht es, Sätze wie „Der Hund rennt“ oder „Die Katze schläft“ zu generieren. Die kontextfreie Grammatik ist somit ein grundlegendes Werkzeug, um die Struktur von Sprachen zu definieren und zu analysieren, was in vielen Anwendungen der künstlichen Intelligenz von zentraler Bedeutung ist.