Gramatyka bezkontekstowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Gramatyka bezkontekstowa to gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci:

A \rightarrow \Gamma

gdzie A jest dowolnym symbolem nieterminalnym i jego znaczenie nie zależy od kontekstu, w jakim występuje, a \Gamma to 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ą nazywamy czwórkę uporządkowaną (T, N, P, S)\,, gdzie:

  • T\, jest skończonym zbiorem symboli terminalnych
  • N\, jest skończonym zbiorem symboli nieterminalnych
  • P\, jest skończonym zbiorem reguł typu L \rightarrow R, gdzie L \in N oraz R \in (T \cup N)^*
  • S \in N jest wyróżnionym elementem początkowym

Przykłady[edytuj | edytuj kod]

Przykład 1[edytuj | edytuj kod]

Gramatyka (\{a,b\},\{S\}, \{S \rightarrow aSb | \epsilon\}, S) generuje język \{a^nb^n : n \in \mathbb{N}\}. Ten język nie jest regularny.


Przykład 2[edytuj | edytuj kod]

Język \{w : w \in \{a, b\}^* \wedge w=w^R\}, który jest językiem wszystkich palindromów nad alfabetem \{a,b\}, może być wygenerowany przez następującą gramatykę:
(\{a,b\},\{S\}, \{S \rightarrow aSa| bSb | a | b |\epsilon\}, S) .

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.