Gramatyka bezkontekstowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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.