Gramatyka bezkontekstowa – gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci:
gdzie: – dowolny symbol nieterminalny, jego znaczenie nie zależy od kontekstu, w jakim występuje; – dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.
Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową.
Formalna definicja Gramatyką bezkontekstową nazywa się czwórkę uporządkowaną gdzie: jest skończonym zbiorem symboli terminalnych, jest skończonym zbiorem symboli nieterminalnych, jest skończonym zbiorem reguł typu gdzie oraz jest wyróżnionym elementem początkowym.
Przykłady Przykład 1 Gramatyka generuje język Ten język nie jest regularny.
Przykład 2 Język który jest językiem wszystkich palindromów nad alfabetem może być wygenerowany przez następującą gramatykę:
Postaci normalne Każdy język bezkontekstowy nie zawierający słowa pustego może być wyrażony za pomocą gramatyki w postaci normalnej Greibach oraz postaci normalnej Chomskiego.
Linki zewnętrzne Grammar, context-free , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-04-23].
Kategoria:Języki formalne Kategoria:Gramatyka generatywna