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

22

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!

Raphael
źródło

Odpowiedzi:

21

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.

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,δ,S)T δ S N ϑ ( G ) S δ α ϑ ( G )NTδSNϑ(G)SδG L ( G ) = ϑ ( G ) T L = L ( G ) L T αϑ(G)SαGL(G)=ϑ(G)TL=L(G)LT

Ansatz

Oto jak to robimy. Definiujemy tak, abyM1,,Mk(NT)

  1. ϑ(G)=i=1kMi i
  2. Ti=1kMi=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 ) = L.MiL(G)=L

Dla ułatwienia notacji oznaczmy .M=i=1kMi

Kamienista droga

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

  • Jak znaleźć (dobre) ? Mi
    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.

    • Gϑ(G)M (strukturalnego) indukcja przez realizacjach .G
    • M i SMϑ(G) : zazwyczaj jeden indukcję , począwszy od jednego, że zawiera .MiS

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

L={anbncmn,mN}

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

SScAAaAbε

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 iL=L(G)cmanbnMi

M0={ScmmN},M1={anAbncmm,nN},M2={anbncmm,nN}.

Ponieważ i , pozycja 2. jest już zajęta. W stronę 1. podzieliliśmy dowód na dwie części, zgodnie z zapowiedzią.M 0T = M 1T = M2=LM0T=M1T=

ϑ(G)M

Wykonujemy indukcja strukturalna wraz z zasadami .G

IA: Ponieważ pomyślnie zakotwiczamy.S=Sc0M0

IH: Załóżmy, że dla pewnego zbioru zdań że my też znamy .X MXϑ(G)XM

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:α MαXϑ(G)MαM

  • wM0 , czyli dla niektórych . Można zastosować dwie reguły, z których obie wyprowadzają zdanie w języku : m N Mw=ScmmN
    M
    • ScmScm+1M0 i
    • ScmAcm=a0Ab0cmM1 .
  • w =wM1 , tj. dla niektórych : m , n Nw=anAbncmm,nN
    • wan+1Abn+1cmM1 i
    • wanbncmM2 .
  • w T wM3 : ponieważ , dalsze pochodne nie są możliwe.wT

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

ϑ(G)M

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

  • mM1 : Wykonujemy indukcję nad , zakotwiczając w i używając w kroku.mS S cSc0=SSSc
  • m n A c m S S c mM2 : do dowolnej wartości i indukujemy ponad . Zakotwiczamy w , używając tego na podstawie poprzedniego dowodu. Krok przechodzi od .mnAcm A a A bSScmAcmAaAb
  • m , n N S a n A b n c mM3 : Dla dowolnego używamy poprzedniego dowodu dla .m,nNSanAbncmanbncm

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ą : G.MiG

SaAbCεAaAbεCcCε

Ćwiczenie

Podaj gramatykę dla

L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

i udowodnić swoją poprawność.

Jeśli masz problemy, gramatyka:

Zastanów się z produkcjamiG=({S,Br,Bl,A,C},{a,b,c},δ,S)

SbSbBlBrBlbBlbABrBrbAbAaAaaCCbcCbcbc

i :Mi

M0={biSbiiN}M1={biBlbooN,io}M2={bkBrbikN,ik}M3={bkaiAa2ibok,o,iN,ko}M4={bkal(bc)iCa2lbok,o,l,iN,ko}M5=L

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 pokazujemyMi

  1. ϑ(G)L i
  2. n N|L(G)Tn|=|LTn|dla wszystkich .nN

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 NG nN

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.
Raphael
źródło