Jak udowodnić, że język jest pozbawiony kontekstu?

Istnieje wiele technik, aby udowodnić, że język nie jest pozbawiony kontekstu, ale jak udowodnić, że język jest pozbawiony kontekstu?

Jakie są techniki, aby to udowodnić? Oczywiście jednym ze sposobów jest wykazanie gramatyki bezkontekstowej dla tego języka. Czy istnieją jakieś systematyczne techniki znajdowania gramatyki bezkontekstowej dla danego języka?

Dla stałych języków, nie są systematyczne sposoby w celu uzyskania regularnego automat gramatyka / skończonych Stan: na przykład, Myhill-Nerode twierdzenie zapewnia jeden sposób. Czy istnieje odpowiednia technika dla języków bezkontekstowych?

Moją motywacją jest (mam nadzieję) zbudowanie pytania referencyjnego zawierającego listę technik, które często są pomocne, gdy próbuję udowodnić, że dany język jest pozbawiony kontekstu. Ponieważ mamy tutaj wiele pytań, które są tego szczególnymi przypadkami, byłoby dobrze, gdybyśmy mogli udokumentować ogólne podejście lub ogólne techniki, których można użyć w obliczu tego rodzaju problemu.

Praktycznym podejściem, które w wielu przykładach działa [ale nie zawsze, wiem] jest próba znalezienia zagnieżdżonej struktury ciągów w języku. „Zagnieżdżone zależności” muszą być generowane jednocześnie w różnych częściach łańcucha.

Mamy również podstawowy zestaw narzędzi :

1. konkatenacja: jeśli możesz podzielić język na dwie kolejne części, użyj tej produkcji$S\to S_1S_2$

2. związek: podzielony na części rozłączne$S\to S_1 \mid S_2$

3. iteracja:$S\to S_1S \mid \varepsilon$

Przykład 1

Oto przykład zagnieżdżenia (dziękuję Raphael).

$L=\{b^ka^l(bc)^ma^nb^o \mid k,l,m,n,o\in {\Bbb N},k\neq o,2l=n,m\ge 2 \}$

Zamień na . Możemy teraz upuścić w warunkach.2 l $n$$2l$$n$

Zamień na (mylić? to „oh”, a nie „zero”). Zastosuj narzędzia do unii. Pracujemy tutaj z . Również iff oraz gdzie jest nową zmienną. Zamień na .k > o  lub  k < o o k > $k \neq o$$k > o \text{ or } k < o$$o$$k > o$k = s + o s > 0 s k s + $k>o$$k=s+o$$s>0$$s$$k$$s+o$

$L_1 =\{b^{s+o}a^l(bc)^ma^{2l}b^o \mid l,m,o,s\in {\Bbb N},s>0,m\ge 2 \}$

Kilka prostych przeróbek.

$L_1 =\{bb^sb^o a^l bcbc(bc)^m (aa)^{l}b^o \mid l,m,o,s\in {\Bbb N} \}$

Teraz widzimy strukturę zagnieżdżania i zaczynamy budować gramatykę.

T → b U U → b U ∣ $S_1 \to TV$ , , (patrz: konkatenacja i iteracja tutaj)$T\to bU$$U\to bU \mid \varepsilon$

o $V \to bVb \mid W$ (generujemy po obu stronach)$o$ $b$

$W \to aWaa\mid X$

Y → b c b c Z → b c Z ∣ $X\to YZ$ , ,$Y\to bcbc$$Z\to bcZ\mid \varepsilon$

Przykład 2

$K =\{ a^kb^lc^m \mid l=m+k\}$

Pierwsze „oczywiste” przepisanie.

$K =\{ a^kb^{m+k}c^m \mid m,k\ge 0\} = \{ a^kb^mb^kc^m \mid m,k\ge 0\}$

W językoznawstwie nazywa się to „zależnością międzyseryjną”: przeplatanie (zwykle) silnie wskazuje na brak kontekstu. Oczywiście i jesteśmy zbawieni.m + k = k + $k,m,k,m$$m+k=k+m$

$K =\{ a^kb^{k+m}c^m \mid m,k\ge 0\} = \{ a^kb^kb^mc^m \mid m,k\ge 0\}$

z produkcjami , ,X → a X b ∣ ε Y → b Y c ∣ $S\to XY$$X\to aXb\mid \varepsilon$$Y\to bYc\mid \varepsilon$

Podobnie$K'= \{ a^kb^lc^m \mid m=k+l\} = \{ a^kb^lc^lc^k \mid k,l\ge 0\}$

z produkcjami ,X → b X c ∣ $S\to aSc \mid X$$X\to bXc\mid \varepsilon$

Komentarz końcowy: te techniki pomogą ci opracować kandydatową gramatykę bezkontekstową, która, mam nadzieję, rozpozna twój język. Konieczny może być jeszcze dowód poprawności , aby gramatyka naprawdę rozpoznała Twój język (nic więcej i nic mniej).

Istnieje jedna charakterystyka CFL, która może być użyteczna, twierdzenie Chomsky'ego-Schützenbergera .

Język Dyck

Niech alfabet. Definiujemy język Dyck D_T z za pomocą gramatyki bezkontekstowej z podanym przezD $T$ T G = ( $D_T \subseteq (T \cup \hat{T})^*$$T$$G = (\{S\}, T \cup \hat{T}, \delta, S)$$\delta$

$\qquad\displaystyle S \to aS\hat{a}S \mid \varepsilon, \quad a \in T$ .

Twierdzenie Chomsky'ego-Schützenbergera

$L \subseteq \Sigma^*$ jest bezkontekstowy tylko wtedy, gdy istnieją

• alfabet ,$T$
• zwykły język i$R \subseteq (T \cup \hat{T})^*$
• homomorfizm$\psi : (T \cup \hat{T}) \to \Sigma^*$

po to aby

$\qquad \displaystyle L = \psi(D_T \cap R)$ .

Zauważ, że homomorfizm rozciąga się na słowa (symbol po symbolu), a następnie na języki (słowo po słowie).

Przykład

Rozważ . Z$L = \{ a^n b^n c^m \mid n,m \in \mathbb{N}$

• T = { ] , ⟩ $T = \{ [, \langle\}$ (i kanonicznie ),$\hat{T} = \{ ], \rangle\}$
• $R = \mathcal{L}([^* ]^*\langle^* \rangle^*)$ i
• $\psi(x) = \begin{cases} a, &x = [ \\ b, &x =\ ] \\ \varepsilon, &x = \langle \\ c, &x =\ \rangle \end{cases}$

twierdzenie implikuje, że jest pozbawiony kontekstu, w szczególności od tego czasu$L$

$\qquad\displaystyle D_T \cap R = \{[^n ]^n \langle^m \rangle^m \mid n,m \in \mathbb{N}\}$ .

Przykład 2

Pokaż, że jest pozbawiony kontekstu.$L = \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k \neq o, 2l = n, m \geq 2 \}$

Potrzebujemy tutaj jednego rodzaju nawiasów dla , jednego dla , jednego dla i drugiego używanego do modelowania które powodują . Używamy$a$$bc$$b$$b$$k \neq o$

• $T = \{ [, \langle, \vdash, < \}$ ,
• $R = \mathcal{L}(<^+>^+\vdash^* [^* \langle\langle^+ \rangle^+\rangle ]^* \dashv^*) \cup \mathcal{L}(\vdash^* [^* \langle\langle^+ \rangle^+\rangle ]^* \dashv^*<^+>^+)$ i
• $\psi(x) = \begin{cases} b, &x \in \{\vdash, \dashv, <\} \\ a, &x = [ \\ aa, &x =\ ] \\ bc, &x = \langle \\ \varepsilon, &\text{else} \end{cases}$

i zastosuj twierdzenie. Aby zobaczyć, że , nie potrzebujemy więcej niż fakt, że pasujące symbole (np. I ) muszą występować równie często w dowolnym . Dodając to ograniczenie do wyrażeń regularnych, przez które zdefiniowaliśmy , otrzymujemy$L = \psi(D_T \cap R)$$[$$]$$w \in D_T$$R$

$\qquad \begin{align*} D_T \cap R = &\{<^p>^p \vdash^o [^l \langle^m \rangle^m ]^l \dashv^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2\} \\ &\cup\ \{\dots\} \end{align*}$

i tym razem

$\qquad\begin{align*} \psi(D_T \cap R) &= \{ b^{p+o} a^l (bc)^m a^{2l} b^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2 \} \\ &\quad \cup\ \{ \dots \} \\ &= \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k > o, 2l = n, m \geq 2 \} \\&\quad \cup\ \{ \dots \} \\ &= L \;. \end{align*}$

Do gramatyki i automatów

Jeśli w końcu chcemy mieć automat lub gramatykę, mamy przed sobą jeszcze trochę pracy.

• W kierunku automat skonstruować NPDA dla i NFA dla . Pierwszy z nich jest standardowy, a my mamy algorytmy dla drugiego, pod warunkiem, że język jest podany w odpowiedniej reprezentacji (patrz również tutaj ). Oba przecięcie to kolejna standardowa konstrukcja i można zastosować do każdego przejścia osobno.$D_T$$R$$\psi$

• W kierunku gramatyki, zbuduj ją dla (znowu, powinno być standardowe), weź tę dla i je . Następnie zastosuj do zestawu reguł (symbol dla symbolu).$R$$D_T$$\psi$

Prawdopodobnie jest to łatwe, ponieważ algorytmiczne; złożoność polega na znalezieniu odpowiedniego , i . Nie wiem, czy to podejście jest (często) prostsze niż bezpośrednie tworzenie PDA / gramatyki, ale może pozwolić skupić się na ważnych cechach danego języka. Spróbuj sam!R $T$$R$$\psi$