Gramatyka bezkontekstowa

Gramatyka bezkontekstowagramatyka 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

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
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

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.