Jak pokazać, że L = L (G)?

Określanie języków formalnych poprzez nadawanie gramatyki formalnej jest częstym zadaniem: potrzebujemy gramatyki nie tylko do opisu języków, ale także do ich analizy, a nawet do właściwej nauki . We wszystkich przypadkach ważne jest, aby gramatyka była poprawna , czyli generowała dokładnie pożądane słowa.

Często możemy dyskutować na wysokim szczeblu, dlaczego gramatyka jest odpowiednią reprezentacją pożądanego języka, pomijając formalny dowód. Ale co jeśli mamy wątpliwości lub z jakiegoś powodu potrzebujemy formalnego dowodu? Jakie techniki możemy zastosować?

^{To ma stać się pytaniem referencyjnym . Dlatego prosimy o podanie ogólnych, dydaktycznie przedstawionych odpowiedzi, które są zilustrowane co najmniej jednym przykładem, ale mimo to obejmują wiele sytuacji. Dzięki!}

Gramatyki są z natury obiektami rekurencyjnymi, więc odpowiedź wydaje się oczywista: przez indukcję. To powiedziawszy, specyfika często jest trudna do osiągnięcia. W dalszej części opiszę technikę, która pozwala zredukować wiele dowodów poprawności gramatycznej do kroków mechanicznych, pod warunkiem, że zostanie przeprowadzone pewne twórcze przetwarzanie wstępne. $\newcommand{\lang}[1]{\mathcal{L}(#1)} \newcommand{\sent}[1]{\vartheta(#1)} \newcommand{\derive}{\mathbin{\Rightarrow}} \newcommand{\derivestar}{\mathbin{\Rightarrow^*}} \newcommand{\nats}{\mathbb{N}}$

Podstawową ideą jest nie ograniczanie się do słów gramatyki i języka; w ten sposób trudno jest pojąć strukturę gramatyki. Zamiast tego będziemy kłócić się o zestaw zdań, które gramatyka może stworzyć. Ponadto podzielimy jeden zniechęcający cel próbny na wiele małych celów, które są bardziej wykonalne.

Niech formalnym gramatyki z nie-zaciski , końcówki , Reguły i wyjściowych symboli . Oznaczamy przez zestaw zdań, które mogą pochodzić od danego , to jest . Językiem generowanym przez jest . Załóżmy, że chcemy pokazać, że dla niektórych .$G=(N,T,\delta,S)$T δ S ∈ N ϑ ( G ) S δ α ∈ ϑ ( G $N$$T$$\delta$$S \in N$$\sent{G}$$S$$\delta$G L ( G ) = ϑ ( G ) ∩ T ∗ L = L ( G ) L ⊆ T $\alpha \in \sent{G} \iff S \derivestar \alpha$$G$$\lang{G} = \sent{G} \cap T^*$$L = \lang{G}$$L \subseteq T^*$

Ansatz

Oto jak to robimy. Definiujemy tak, aby$M_1, \dots, M_k \subseteq (N \cup T)^*$

1. $\displaystyle \sent{G} = \bigcup_{i=1}^k M_i$ i
2. $\displaystyle T^* \cap \bigcup_{i=1}^k M_i = L$ .

Podczas gdy 2. jest zwykle jasne z definicji , 1. wymaga poważnej pracy. Te dwa elementy wyraźnie oznaczają zgodnie z życzeniem.L ( G ) = $M_i$$\lang{G} = L$

Dla ułatwienia notacji oznaczmy .$M = \bigcup_{i=1}^k M_i$

Kamienista droga

Istnieją dwa główne kroki do przeprowadzenia takiego dowodu.

• Jak znaleźć (dobre) ? $M_i$
  Jedną ze strategii jest badanie faz, przez które przechodzi gramatyka. Nie każda gramatyka nadaje się do tego pomysłu; ogólnie rzecz biorąc, jest to twórczy krok. Pomaga, jeśli sami możemy zdefiniować gramatykę; z pewnym doświadczeniem będziemy w stanie zdefiniować gramatyki bardziej przystępne dzięki temu podejściu.

• Jak udowodnić 1.?
  Podobnie jak w przypadku każdej równości, istnieją dwa kierunki.

  • $\sent{G} \subseteq M$ (strukturalnego) indukcja przez realizacjach .$G$
  • M i$M \subseteq \sent{G}$ : zazwyczaj jeden indukcję , począwszy od jednego, że zawiera .$M_i$$S$

Jest to tak szczegółowe, jak to możliwe; szczegóły zależą od gramatyki i języka.

Przykład

Zastanów się nad językiem

$\qquad \displaystyle L = \{ a^n b^n c^m \mid n,m \in \nats \}$

a gramatyka z podanym przez$G = (\{S,A\}, \{a,b,c\}, \delta, S)$$\delta$

$\qquad \begin{align} S &\to Sc \mid A \\ A &\to aAb \mid \varepsilon \end{align}$

dla którego chcemy pokazać, że . Na jakich etapach działa ta gramatyka? Najpierw generuje a następnie . To natychmiast informuje nasz wybór , a mianowiciec m a n b n M $L = \lang{G}$$c^m$$a^n b^n$$M_i$

$\qquad \begin{align} M_0 &= \{Sc^m \mid m \in \nats \} \;, \\ M_1 &= \{ a^n A b^n c^m \mid m,n \in \nats \} \;, \\ M_2 &= \{ a^n b^n c^m \mid m,n \in \nats \} \;. \\ \end{align}$

Ponieważ i , pozycja 2. jest już zajęta. W stronę 1. podzieliliśmy dowód na dwie części, zgodnie z zapowiedzią.M 0 ∩ T ∗ = M 1 ∩ T ∗ = $M_2 = L$$M_0 \cap T^* = M_1 \cap T^* = \emptyset$

$\mathbf{\sent{G} \subseteq M}$

Wykonujemy indukcja strukturalna wraz z zasadami .$G$

IA: Ponieważ pomyślnie zakotwiczamy.$S = Sc^0 \in M_0$

IH: Załóżmy, że dla pewnego zbioru zdań że my też znamy .X ⊆ $X \subseteq \sent{G}$$X \subseteq M$

IS: Niech dowolnie. Musimy pokazać, że bez względu na formę ma i co reguła stosowana jest obok, nie zostawiać . Robimy to poprzez pełne rozróżnienie poszczególnych przypadków. Dzięki hipotezie indukcyjnej wiemy, że (dokładnie) ma zastosowanie jeden z następujących przypadków:α $\alpha \in X \subseteq \sent{G} \cap M$$\alpha$$M$

• $w \in M_0$ , czyli dla niektórych . Można zastosować dwie reguły, z których obie wyprowadzają zdanie w języku : m ∈ N$w = Sc^m$$m \in \nats$
  $M$
  • $Sc^m \derive Sc^{m+1} \in M_0$ i
  • $Sc^m \derive Ac^m = a^0Ab^0c^m \in M_1$ .
• w $w \in M_1$ , tj. dla niektórych : m , n ∈ $w = a^nAb^nc^m$$m,n \in \nats$
  • $w \derive a^{n+1}Ab^{n+1}c^m \in M_1$ i
  • $w \derive a^nb^nc^m \in M_2$ .
• w ∈ T $w \in M_3$ : ponieważ , dalsze pochodne nie są możliwe.$w \in T^*$

Ponieważ udało nam się objąć wszystkie przypadki, indukcja jest zakończona.

$\mathbf{\sent{G} \supseteq M}$

Wykonujemy jeden (prosty) dowód na . Zauważ, jak łączymy dowody, aby „później” mógł zakotwiczyć za pomocą „wcześniejszego” .M i M $M_i$$M_i$$M_i$

• $M_1$ : Wykonujemy indukcję nad , zakotwiczając w i używając w kroku.$m$S → S $Sc^0 = S$$S \to Sc$
• m n A c m S ⇒ ∗ S c $M_2$ : do dowolnej wartości i indukujemy ponad . Zakotwiczamy w , używając tego na podstawie poprzedniego dowodu. Krok przechodzi od .$m$$n$$Ac^m$ A → a A $S \derivestar Sc^m \derive Ac^m$$A \to aAb$
• m , n ∈ N S ⇒ ∗ a n A b n c $M_3$ : Dla dowolnego używamy poprzedniego dowodu dla .$m,n \in \nats$$S \derivestar a^nAb^nc^m \derive a^nb^nc^m$

To kończy drugi kierunek dowodu 1. i jesteśmy skończeni.

Widzimy, że mocno wykorzystujemy gramatykę liniową . W przypadku gramatyki nieliniowej potrzebujemy z więcej niż jednym parametrem zmiennym (w dowodzie (dowodach)), które mogą stać się brzydkie. Jeśli mamy kontrolę nad gramatyką, uczy nas to prostego. Rozważ jako odstraszający przykład gramatykę równoważną :$M_i$$G$

$\qquad \begin{align} S &\to aAbC \mid \varepsilon \\ A &\to aAb \mid \varepsilon \\ C &\to cC \mid \varepsilon \end{align}$

Ćwiczenie

Podaj gramatykę dla

$\qquad L = \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \nats, k \neq o, 2l = n, m \geq 2 \}$

i udowodnić swoją poprawność.

Jeśli masz problemy, gramatyka:

Zastanów się z produkcjami$G = (\{S,B_r,B_l,A,C\}, \{a,b,c\}, \delta, S)$

$\quad \begin{align} S &\to bSb \mid B_l \mid B_r \\ B_l &\to bB_l \mid bA \\ B_r &\to B_r b \mid Ab \\ A &\to aAaa \mid C \\ C &\to bcC \mid bcbc \end{align}$

i :$M_i$

$\quad\begin{align} M_0 &= \{ b^i S b^i \mid i \in \nats \} \\ M_1 &= \{ b^i B_l b^o \mid o \in \nats, i \geq o \} \\ M_2 &= \{ b^k B_r b^i \mid k \in \nats, i \geq k \} \\ M_3 &= \{ b^k a^i A a^{2i} b^o \mid k,o,i \in \nats, k \neq o \} \\ M_4 &= \{ b^k a^l (bc)^i C a^{2l} b^o \mid k,o,l,i \in \nats, k \neq o \} \\ M_5 &= L \end{align}$

Co z gramatykami nieliniowymi?

Cechą charakterystyczną klasy języków bezkontekstowych jest język Dyck : zasadniczo każdy język bezkontekstowy może być wyrażony jako przecięcie języka Dyck i języka zwykłego. Niestety, język Dyck nie jest liniowy, tzn. Nie możemy nadać gramatyki, która z natury byłaby odpowiednia dla tego podejścia.

Możemy, oczywiście, nadal zdefiniować i wykonać dowód, ale z pewnością będzie to trudniejsze w przypadku zagnieżdżonych indukcji, a co nie. Znam jeden ogólny sposób, który może w pewnym stopniu pomóc. Zmieniamy ansatz na wyświetlanie, że generujemy co najmniej wszystkie wymagane słowa i że generujemy odpowiednią liczbę słów (na długość). Formalnie to pokazujemy$M_i$

1. $\displaystyle \sent{G} \supseteq L$ i
2. n∈$\displaystyle |\lang{G} \cap T^n| = |L \cap T^n|$dla wszystkich .$n \in \nats$

W ten sposób możemy ograniczyć się do „łatwego” kierunku z oryginalnego ansatz i wykorzystać strukturę w języku, ignorując nadmiernie skomplikowane funkcje gramatyki. Oczywiście nie ma darmowego lunchu: otrzymujemy zupełnie nowe zadanie liczenia słów generowanych przez dla każdego . Na szczęście dla nas jest to często wykonalne; zobacz tutaj i tutaj, aby uzyskać szczegółowe informacje¹. Możesz znaleźć kilka przykładów w mojej pracy licencjackiej .n ∈ $G$ $n \in \nats$

Jeśli chodzi o dwuznaczne i pozbawione kontekstu gramatyki, obawiam się, że wróciliśmy do ansatz one i myśląc o ograniczeniach.

---

1. Korzystając z tej konkretnej metody liczenia, otrzymujemy jako bonus, że gramatyka jest jednoznaczna. To z kolei oznacza również, że technika musi zawieść dla dwuznacznych gramatyk, ponieważ nigdy nie możemy udowodnić 2.