Język bezkontekstowy

Język bezkontekstowy (ang. context-free language) – język formalny taki, że istnieje niedeterministyczny automat ze stosem decydujący czy dany łańcuch należy do języka. Równoważnie, taki, że istnieje dlań gramatyka bezkontekstowa. W hierarchii Chomsky’ego jest zdefiniowany jako język typu 2.

Rodzina języków regularnych jest podzbiorem zbioru języków bezkontekstowych. Każdy język bezkontekstowy jest językiem kontekstowym.

Języki bezkontekstowe mają ważne znaczenie w informatyce, m.in. w budowie kompilatorów; patrz analiza składniowa.

Gramatyka bezkontekstowa

Każdy język bezkontekstowy jest generowany przez pewną gramatykę bezkontekstową. Nazwa ta bierze się od tego, że wszystkie jej reguły są postaci ${\displaystyle A\to \Gamma ,}$ gdzie ${\displaystyle A}$ jest dowolnym symbolem nieterminalnym, i którego znaczenie nie zależy od kontekstu w jakim występuje, a ${\displaystyle \Gamma }$ to dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.

Do zapisu reguł można stosować notację Backusa-Naura.

Przykład

Język słów postaci ${\displaystyle \{a^{n}b^{n}:n\in \mathbb {N} \}}$ jest generowany przez:

${\displaystyle S\to aSb,}$

${\displaystyle S\to \epsilon .}$

Słowo ${\displaystyle aaabbb}$ możemy wyprowadzić:

${\displaystyle S\to aSb\to aaSbb\to aaaSbbb\to aaabbb.}$

Przykład – język Dycka

Język „poprawnie rozstawionych nawiasów”, czyli takich wyrażeń, które mają tyle samo wystąpień znaku ${\displaystyle (}$ i znaku ${\displaystyle ),}$ i w każdym prefiksie słowa jest nie mniej ${\displaystyle (}$ od ${\displaystyle )}$ (można sprawdzić, że takie warunki rzeczywiście są równoważne temu, że nawiasy są poprawnie rozstawione) jest generowany przez:

${\displaystyle S\to \epsilon ,}$

${\displaystyle S\to (S),}$

${\displaystyle S\to SS.}$

Słowo ${\displaystyle ((())())}$ można wyprowadzić:

${\displaystyle S\to (S)\to (SS)\to (S(S))\to ((S)(S))\to (((S))())\to ((())()).}$

Ten język nazywa się językiem Dycka. Ogólnie, możemy zdefiniować język Dycka ${\displaystyle D_{n}}$ dla ${\displaystyle n}$ możliwych rodzajów nawiasów (tj. nad alfabetem ${\displaystyle \{(_{1},)_{1},(_{2},)_{2},\dots ,(_{n},)_{n}\}}$) za pomocą gramatyki

${\displaystyle S\to \epsilon }$

${\displaystyle S\to (_{1}S)_{1}}$

${\displaystyle S\to (_{2}S)_{2}}$

${\displaystyle \vdots }$

${\displaystyle S\to (_{n}S)_{n}}$

${\displaystyle S\to SS}$

Własności

Podane poniżej własności mają charakter algorytmiczny, tj. pisząc, że język ${\displaystyle X}$ jest bezkontekstowy, istnieje stała ${\displaystyle n}$, istnieje język regularny ${\displaystyle R}$ mamy na myśli także fakt, że można podać algorytm wyznaczający te obiekty, dostający na wejściu dane reprezentowane w efektywnej postaci. W efektywny sposób jest wykonywalna konwersja między gramatyką bezkontekstową a niedeterministycznym automatem ze stosem (w obydwie strony).

• Języki bezkontekstowe są zamknięte ze względu na konkatenację, sumę, domknięcie Kleene’ego, odbicie lustrzane i przecięcie z językami regularnymi: jeżeli ${\displaystyle L}$ i ${\displaystyle L'}$ są językami bezkontekstowymi oraz ${\displaystyle R}$ jest językiem regularnym, to językami bezkontekstowymi są zawsze ${\displaystyle L\cup L',}$ ${\displaystyle LL',}$ ${\displaystyle L^{*},}$ ${\displaystyle L^{R},}$ ${\displaystyle L\cap R.}$

• Postać normalna Chomsky’ego: każdą gramatykę bezkontekstową, której język nie generuje słowa pustego można sprowadzić do postaci, w której każda reguła ma postać ${\displaystyle A\to BC}$ lub ${\displaystyle A\to a,}$ gdzie ${\displaystyle A,B,C}$ to symbole nieterminalne, ${\displaystyle a}$ to symbol terminalny. Tę postać normalną wykorzystuje się w algorytmie CYK.

• Postać normalna Greibach: każdą gramatykę bezkontekstową, której język nie generuje słowa pustego można sprowadzić do postaci, w której każda reguła ma postać ${\displaystyle A\to aX,}$ gdzie ${\displaystyle A}$ to symbol nieterminalny, ${\displaystyle a}$ to symbol terminalny, ${\displaystyle X}$ to ciąg (być może pusty) symboli nieterminalnych.

• Lemat o pompowaniu: Dla każdego języka bezkontekstowego istnieje takie ${\displaystyle n,}$ że każde słowo ${\displaystyle z}$ tego języka długości większej od ${\displaystyle n}$ można zapisać w postaci ${\displaystyle uvwxy,}$ gdzie ${\displaystyle |vwx|<n,}$ przynajmniej jedno z ${\displaystyle v}$ i ${\displaystyle x}$ jest niepuste, i dla każdego ${\displaystyle k,}$ ${\displaystyle uv^{k}wx^{k}y}$ należy do tego języka.

• Lemat Ogdena: dla każdego języka bezkontekstowego istnieje takie ${\displaystyle n,}$ że każde słowo ${\displaystyle z}$ w którym oznaczymy więcej niż ${\displaystyle n}$ symboli można zapisać w postaci ${\displaystyle uvwxy,}$ gdzie ilość oznaczonych symboli w ${\displaystyle vwx}$ jest mniejsza od ${\displaystyle n,}$ przynajmniej jedno z ${\displaystyle v}$ i ${\displaystyle x}$ zawiera oznaczony symbol, i dla każdego ${\displaystyle k,}$ ${\displaystyle uv^{k}wx^{k}y}$ należy do tego języka. Lemat o pompowaniu jest szczególnym przypadkiem lematu Ogdena, w którym oznacza się wszystkie symbole.

• Twierdzenie Parikha: Niech ${\displaystyle f\colon A^{*}\to \mathbb {N} ^{A}}$ przyporządkowuje słowu wektor liczby wystąpień każdej litery w słowie (np. ${\displaystyle f(aba)=(2,1)}$ dla ${\displaystyle A=\{a,b\}}$). Wówczas dla każdego języka bezkontekstowego ${\displaystyle L\subseteq A^{*}}$ istnieje język regularny ${\displaystyle R}$ taki, że ${\displaystyle f(L)=f(R).}$ Przykład: dla ${\displaystyle L=\{a^{n}b^{n}:n\in \mathbb {N} \}}$ można wziąć ${\displaystyle R=(ab)^{*}.}$

• Twierdzenie Chomsky’ego-Schützenbergera: dla każdego języka bezkontekstowego ${\displaystyle L\subseteq A^{*}}$ istnieje liczba naturalna ${\displaystyle n,}$ język regularny ${\displaystyle R}$ nad alfabetem ${\displaystyle A_{n}=\{(_{1},)_{1},\dots ,(_{n},)_{n}\}}$ oraz homomorfizm ${\displaystyle f\colon A_{n}^{*}\to A^{*}}$ taki, że ${\displaystyle L=f(D_{n}\cap R)}$ (${\displaystyle D_{n}}$ to język Dycka).

Przecięcie języków bezkontekstowych i dopełnienie języka bezkontekstowego

Dopełnienie języka bezkontekstowego albo przecięcie dwóch języków bezkontekstowych nie musi być językiem bezkontekstowym.

Przykład: język ${\displaystyle \{a^{n}b^{n}c^{n}:n\in \mathbb {N} \}}$ nie jest bezkontekstowy (co można wykazać korzystając z lematu o pompowaniu). Język ten jednak jest przecięciem dwóch języków bezkontekstowych ${\displaystyle \{a^{n}b^{m}c^{m}:n,m\in \mathbb {N} \}}$ i ${\displaystyle \{a^{n}b^{n}c^{m}:n,m\in \mathbb {N} \}.}$

Dopełnienie języka bezkontekstowego ${\displaystyle \{a^{n}b^{m}c^{k}:n,m,k\in \mathbb {N} ,n\neq m\lor m\neq k\}}$ nie jest językiem bezkontekstowym. Gdyby było, to po przecięciu z językiem regularnym ${\displaystyle a^{*}b^{*}c^{*}}$ dostalibyśmy język bezkontekstowy (tymczasem dostajemy ${\displaystyle \{a^{n}b^{n}c^{n}:n\in \mathbb {N} \}}$).

Dla każdego ${\displaystyle n\geqslant 1}$ istnieje język, który można przedstawić jako przecięcie ${\displaystyle n+1}$ języków bezkontekstowych, ale nie można przedstawić jako przecięcie ${\displaystyle n}$ języków bezkontekstowych^[1].

Podklasy klasy języków bezkontekstowych

• Języki liniowe to języki, dla których istnieje gramatyka, w której po prawej stronie każdej reguły znajduje się co najwyżej jeden nieterminal. Nie każdy język bezkontekstowy jest językiem liniowym; za przykład może służyć ${\displaystyle \{a^{n}b^{n}c^{m}d^{m}:n,m\in \mathbb {N} \}.}$

• Języki bezkontekstowe deterministyczne to języki rozpoznawalne przez deterministyczny automat ze stosem. Są one zamknięte ze względu na dopełnienie i przecięcie z językami regularnymi. Nie każdy język bezkontekstowy jest językiem deterministycznym; za przykład może służyć ${\displaystyle \{a^{n}b^{m}c^{k}:n,m,k\in \mathbb {N} ,n\neq m\lor m\neq k\}.}$ (Gdyby był on deterministycznym językiem bezkontekstowym, to jego dopełnienie przecięte z ${\displaystyle a^{*}b^{*}c^{*}}$ – ${\displaystyle \{a^{n}b^{n}c^{n}:n\in \mathbb {N} \}}$ również takie by było. Ale ten język nie jest nawet bezkontekstowy.)

• Języki jednoznaczne to języki, dla których istnieje jednoznaczna gramatyka bezkontekstowa – gramatyka, w której każde słowo może mieć tylko jedno drzewo wyprowadzenia. Przykładem języka niejednoznacznego jest ${\displaystyle \{a^{n}b^{n}c^{m}d^{m}:n,m\in \mathbb {N} \}\cup \{a^{n}b^{m}c^{m}d^{n}:n,m\in \mathbb {N} \}.}$

Rozstrzygalność

W językach regularnych praktycznie wszystkie problemy decyzyjne są rozstrzygalne. Nie jest to już jednak prawdą w językach bezkontekstowych.

Rozstrzygalne są takie problemy jak:

• czy dane słowo należy do danego języka (algorytm CYK wykonuje ten test w czasie ${\displaystyle \Theta (n^{3})}$),
• czy istnieje jakiekolwiek słowo, które należy do danego języka,
• czy do danego języka należy co najmniej ${\displaystyle n}$ słów,
• czy dany język zawiera nieskończenie wiele słów.

Nierozstrzygalne problemy to natomiast m.in.:

• czy istnieje jakiekolwiek słowo, które nie należy do danego języka,
• czy dane dwa języki są równe,
• czy jeden język bezkontekstowy jest podzbiorem drugiego,
• czy istnieje słowo wspólne dla danych dwóch języków,
• czy dany język jest jednoznaczny,
• czy dana gramatyka jest jednoznaczna.

Dowód nierozstrzygalności istnienia wspólnego słowa

Pytanie czy przekrój 2 języków jest niepusty można zredukować do problemu odpowiedniości Posta – niech ${\displaystyle (u_{i},v_{i})}$ oznacza ${\displaystyle i}$-tą parę słów w systemie Posta. Stwórzmy dwa języki bezkontekstowe ${\displaystyle L_{1}}$ i ${\displaystyle L_{2}{:}}$

${\displaystyle L_{1}\to u_{i}b_{i},}$ dla każdego ${\displaystyle i}$ odpowiadającego parze słów w systemie Posta,

${\displaystyle L_{1}\to u_{i}L_{1}b_{i},}$

${\displaystyle L_{2}\to v_{i}b_{i},}$

${\displaystyle L_{2}\to v_{i}L_{2}b_{i},}$

gdzie ${\displaystyle b_{i}}$ są nowymi symbolami terminalnymi, niewystępującymi w żadnym ${\displaystyle u_{i}}$ ani ${\displaystyle v_{i}.}$

Wygenerowane słowo języka ${\displaystyle L_{1}}$ składa się ze słowa wygenerowanego przez pierwszy język systemu Posta, oraz (odwróconego) znaczenia tego słowa:

${\displaystyle u_{i_{1}}u_{i_{2}}u_{i_{3}}\cdots u_{i_{n}}b_{i_{n}}\cdots b_{i_{3}}b_{i_{2}}b_{i_{1}}.}$

Analogiczną postać mają słowa wygenerowane przez ${\displaystyle L_{2}.}$ Czyli jeśli istnieje słowo wspólne dla ${\displaystyle L_{1}}$ i ${\displaystyle L_{2},}$ to w systemie Posta, na podstawie którego zostały zbudowane, istnieje słowo rozwiązujące pozytywnie problem odpowiedniości w tym systemie.

Ponieważ jednak problem odpowiedniości Posta jest nierozstrzygalny, nierozstrzygalne jest też istnienie wspólnego słowa.

Dowód nierozstrzygalności jednoznaczności gramatyki

Weźmy dwa jednoznaczne języki ${\displaystyle L_{1}}$ i ${\displaystyle L_{2}}$ o rozłącznych nieterminalach, i symbolach startowych odpowiednio ${\displaystyle S_{1}}$ i ${\displaystyle S_{2},}$ Zbudujmy następującą gramatykę o symbolu startowym ${\displaystyle S{:}}$

${\displaystyle S\to S_{1},}$

${\displaystyle S\to S_{2},}$

plus wszystkie produkcje obu języków.

Gramatyka taka jest jednoznaczna wtedy i tylko wtedy, gdy nie istnieje słowo należące jednocześnie do ${\displaystyle S_{1}}$ i ${\displaystyle S_{2}.}$ Ponieważ dla każdego systemu Posta potrafimy zbudować jednoznaczne gramatyki (poprzedni dowód), rozwiązanie problemu jednoznaczności rozwiązywałoby problem odpowiedniości Posta.

A zatem problem ten jest nierozstrzygalny.

Zobacz też

• parser

Przypisy

Bibliografia

• John Hopcroft, Jeffrey Ullman: Wprowadzenie do teorii automatów, języków i obliczeń. Warszawa: Wydawnictwo Naukowe PWN, 2005. ISBN 83-01-14502-1.