Gramatyka bezkontekstowa

Ten artykuł od 2013-09 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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

${\displaystyle A\to \Gamma ,}$

gdzie:

${\displaystyle A}$ – dowolny symbol nieterminalny, jego znaczenie nie zależy od kontekstu, w jakim występuje;

${\displaystyle \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

Gramatyką bezkontekstową nazywa się czwórkę uporządkowaną ${\displaystyle (T,N,P,S),}$ gdzie:

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

Przykłady

Przykład 1

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

Przykład 2

Język ${\displaystyle \{w:w\in \{a,b\}^{*}\wedge w=w^{R}\},}$ który jest językiem wszystkich palindromów nad alfabetem ${\displaystyle \{a,b\},}$ może być wygenerowany przez następującą gramatykę:

${\displaystyle (\{a,b\},\{S\},\{S\to 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.