Gramatyka bezkontekstowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

A \rightarrow \Gamma,

gdzie:

A – dowolny symbol nieterminalny, jego znaczenie nie zależy od kontekstu, w jakim występuje;
\Gamma – 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ą (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
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
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.