Język bezkontekstowy

Z Wikipedii

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.

Każdy język regularny jest bezkontekstowy. Każdy język bezkontekstowy jest językiem kontekstowym.

Spis treści

1 Gramatyka bezkontekstowa
- 1.1 Przykład
- 1.2 Przykład (2)
2 Postacie normalne

[edytuj] 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 $A\rightarrow\Gamma$ , gdzie $A$ jest dowolnym symbolem nieterminalnym, i którego znaczenie nie zależy od kontekstu w jakim występuje, a $Γ$ to dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.

[edytuj] Przykład

Język słow postaci ${a n b n}$ , dla $n$ będącego dowolną liczbą naturalną jest generowany przez:

$S\rightarrow aSb$

$S\rightarrow \epsilon$

Słowo $a a a b b b$ możemy wyprowadzić:

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

[edytuj] Przykład (2)

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) to:

$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 ((())())$

[edytuj] Postacie normalne

Istnieją dwie ważne postacie normalne gramatyk bezkontekstowych - postać normalna Chomsky'ego i postać normalna Greibach.

[edytuj] Operacje na językach bezkontekstowych

Językami bezkontekstowymi są zawsze:

konkatenacja języków bezkontekstowych
alternatywa języków bezkontekstowych
domknięcie Kleene'ego języka bezkontekstowego
przecięcie języka bezkontekstowego z językiem regularnym

Nie muszą być językami bezkontekstowymi:

dopełnienie języka bezkontekstowego
przecięcie języka bezkontekstowego

[edytuj] 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 $u v w x y$ , gdzie $| v w x | < n$ , przynajmniej jedno z $v$ i $x$ jest niepuste, i dla każdego $k$ , $u v k w x k y$ należy do tego języka.

[edytuj] Lemat Ogdena

Twierdzenie będące uogólnieniem lematu o pompowaniu to lemat Ogdena. Uogólnienie polega na tym, że dla każdego języka istnieje takie $n$ , że dla każdego słowa $z$ w którym oznaczymy więcej niż $n$ symboli można zapisać w postaci $u v w x y$ , gdzie ilość oznaczonych symboli w $v w x$ jest mniejsza od $n$ , przynajmniej jedno z $v$ i $x$ zawiera oznaczony symbol, i dla każdego $k$ , $u v k w x k y$ należy do tego języka.

Lemat o pompowaniu jest szczególnym przypadkiem lematu Ogdena, w którym oznacza się wszystkie symbole.

[edytuj] Jednoznaczność

W danej gramatyce to samo słowo może mieć więcej niż jedno drzewo wyprowadzenia. Gramatyka taka jest niejednoznaczna. Często możliwe jest przepisanie gramatyki, tak żeby pozbyć się niejednoznaczności. Dla niektórych języków jest to jednak niemożliwe – istnieją dla nich gramatyki bezkontekstowe, ale nie istnieją żadne jednoznaczne gramatyki bezkontekstowe. Taki język jest językiem niejednoznacznym.

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

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

[edytuj] Dowód nierozstrzygalności jednoznaczności gramatyki

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.

Kategoria: Języki formalne

We provide Linux to the World