Język bezkontekstowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Język bezkontekstowy (ang. context-free language) to 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.

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

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

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

Przykład[edytuj | edytuj kod]

Język słow postaci \{a^nb^n:n \in {\mathbb N}\} jest generowany przez:

S\rightarrow aSb
S\rightarrow \epsilon

Słowo aaabbb możemy wyprowadzić:

S \rightarrow aSb \rightarrow aaSbb \rightarrow aaaSbbb \rightarrow aaabbb

Przykład – język Dycka[edytuj | edytuj kod]

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

S\rightarrow \epsilon
S\rightarrow (S)
S\rightarrow SS

Słowo ((())()) można wyprowadzić:

S \rightarrow (S) \rightarrow (SS) \rightarrow (S(S)) \rightarrow ((S)(S)) \rightarrow (((S))()) \rightarrow ((())())

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

S\rightarrow \epsilon
S\rightarrow (_{1} S )_{1}
S\rightarrow (_{2} S )_{2}
\vdots
S\rightarrow (_{n} S )_{n}
S\rightarrow SS

Własności[edytuj | edytuj kod]

Podane poniżej własności mają charakter algorytmiczny, tj. pisząc, że język X jest bezkontekstowy, istnieje stała n, istnieje język regularny 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 L i L' są językami bezkontekstowymi oraz R jest językiem regularnym, to językami bezkontekstowymi są zawsze L \cup L'\,, L L'\,, L^*\,, L^R\,, 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ć A \to BC lub A \to a, gdzie A,B,C to symbole nieterminalne, 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ć A \to aX, gdzie A to symbol nieterminalny, a to symbol terminalny, X to ciąg (być może pusty) symboli nieterminalnych.
  • Lemat o pompowaniu: Dla każdego języka bezkontekstowego istnieje takie n, że każde słowo z tego języka długości większej od n można zapisać w postaci uvwxy, gdzie |vwx|<n, przynajmniej jedno z v i x jest niepuste, i dla każdego k, uv^kwx^ky należy do tego języka.
  • Lemat Ogdena: dla każdego języka bezkontekstowego istnieje takie n, że każde słowo z w którym oznaczymy więcej niż n symboli można zapisać w postaci uvwxy, gdzie ilość oznaczonych symboli w vwx jest mniejsza od n, przynajmniej jedno z v i x zawiera oznaczony symbol, i dla każdego k, uv^kwx^ky 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 f: A^* \to {\mathbb N}^A przyporządkowuje słowu wektor liczby wystąpień każdej litery w słowie (np. f(aba)=(2,1) dla A=\{a,b\}). Wówczas dla każdego języka bezkontekstowego L \subseteq A^* istnieje język regularny R taki, że f(L)=f(R). Przykład: dla L=\{a^n b^n \colon n \in {\mathbb N}\} można wziąć R=(ab)^*.
  • Twierdzenie Chomsky'ego-Schützenbergera: dla każdego języka bezkontekstowego L \subseteq A^* istnieje liczba naturalna n, język regularny R nad alfabetem A_{n} = \{(_{1}, )_{1}, \dots, (_{n}, )_{n}\} oraz homomorfizm f:A_{n}^* \to A^* taki, że L=f(D_n \cap R) (D_n to język Dycka).

Przecięcie języków bezkontekstowych i dopełnienie języka bezkontekstowego[edytuj | edytuj kod]

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

Przykład: język \{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 \{a^n b^m c^m: n,m \in {\mathbb N}\} i \{a^n b^n c^m: n,m \in {\mathbb N}\}.

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

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

Podklasy klasy języków bezkontekstowych[edytuj | edytuj kod]

  • 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ć \{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ć \{a^n b^m c^k: n,m,k \in {\mathbb N}, n \neq m \or m \neq k\}. (Gdyby był on deterministycznym językiem bezkontekstowym, to jego dopełnienie przecięte z a^*b^*c^*\{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 \{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ść[edytuj | edytuj kod]

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

Pytanie czy przekrój 2 języków jest niepusty można zredukować do problemu odpowiedniości Posta – niech (u_i,v_i) oznacza i-tą parę słów w systemie Posta. Stwórzmy dwa języki bezkontekstowe L_1 i L_2:

L_1 \rightarrow u_i b_i, dla każdego i odpowiadającego parze słów w systemie Posta
L_1 \rightarrow u_i L_1 b_i
L_2 \rightarrow v_i b_i
L_2 \rightarrow v_i L_2 b_i

Gdzie b_i są nowymi symbolami terminalnymi, niewystępującymi w żadnym u_i ani v_i.

Wygenerowane słowo języka L_1 składa się ze słowa wygenerowanego przez pierwszy język systemu Posta, oraz (odwróconego) znaczenia tego słowa:

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 L_2. Czyli jeśli istnieje słowo wspólne dla L_1 i 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[edytuj | edytuj kod]

Weźmy dwa jednoznaczne języki L_1 i L_2 o rozłącznych nieterminalach, i symbolach startowych odpowiednio S_1 i S_2, Zbudujmy następującą gramatykę o symbolu startowym S:

S \rightarrow S_1
S \rightarrow 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 S_1 i 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ż[edytuj | edytuj kod]

Przypisy

Bibliografia[edytuj | edytuj kod]

  1. Hopcroft, John; Ullman, Jeffrey: Wprowadzenie do teorii automatów, języków i obliczeń.