Gramatyka bezkontekstowa - Wikipedia, wolna encyklopedia

Wolna encyklopedia

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 $Γ$ to dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.

Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową.

Spis treści

1 Formalna definicja
2 Przykłady
- 2.1 Przykład 1
- 2.2 Przykład 2
3 Postaci normalne
4 Zobacz też

Formalna definicja

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

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

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.

Zobacz też

Gramatyka kontekstowa

Źródło: „haslo,Gramatyka_bezkontekstowa”

Kategoria: Języki formalne