Gramatyka bezkontekstowa

Z Wikipedii

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
- 3.1 Zobacz też

[edytuj] 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

[edytuj] Przykłady

[edytuj] 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.

[edytuj] 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)$ .

[edytuj] 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.

[edytuj] Zobacz też

Gramatyka kontekstowa

Kategoria: Języki formalne

We provide Linux to the World

Gramatyka bezkontekstowa

Z Wikipedii

Spis treści

[edytuj] Formalna definicja

[edytuj] Przykłady

[edytuj] Przykład 1

[edytuj] Przykład 2

[edytuj] Postaci normalne

[edytuj] Zobacz też

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach