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}$

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

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.