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
[edytuj | edytuj kod]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
[edytuj | edytuj kod]- 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
[edytuj | edytuj kod]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.