Jak udowodnić, że język jest regularny?

48

Istnieje wiele metod, aby udowodnić, że dany język nie jest regularny , ale co muszę zrobić, aby udowodnić, że jakiś język jest prawidłowy?

Na przykład, jeśli otrzymam informację, że jest regularne, jak mogę udowodnić, że następujące jest również regularne?L LL

L:={wL:uv=w for uΣL and vΣ+}

Czy mogę narysować niedeterministyczny automat skończony, aby to udowodnić?

corium
źródło
1
w definicji twojego jest literówka , edytuj, aby naprawić. L
Ran G.
2
„Rysowanie” nie jest dowodem; musisz podać NFA i udowodnić, że akceptuje język.
Raphael
Myślę, że definicja języka wciąż nie ma sensu ...
hugomg,
2
w każdym razie konkretny język nie ma znaczenia, jeśli pytanie brzmi „czy mogę narysować NFA, aby udowodnić, że jest on prawidłowy”. @ corium, czy możemy edytować pytanie, aby odzwierciedlić bardziej ogólne pytanie: „jak udowodnić, że określony jest regularny”? L
Ran G.

Odpowiedzi:

48

Tak, jeśli możesz wymyślić jedno z poniższych:

dla jakiegoś języka , jest regularne. Istnieje więcej równoważnych modeli , ale powyższe są najczęstsze.LLL

Istnieją również przydatne właściwości poza światem „obliczeniowym”. jest również regularne, jeśliL

  • jest skończony
  • możesz go zbudować, wykonując pewne operacje na zwykłych językach, a te operacje są zamknięte dla zwykłych języków , takich jak

    • skrzyżowanie,
    • komplement,
    • homomorfizm,
    • odwrócenie,
    • iloraz lewy lub prawy,
    • regularna transdukcja

    i więcej , lub

  • stosując twierdzenie Myhill – Nerode, jeśli liczba klas równoważności dla jest skończona.L

W podanym przykładzie mamy trochę (regularny) język jako podstawę i chcemy powiedzieć coś o języku z niego wyprowadzonym. Zgodnie z pierwszym podejściem - skonstruuj odpowiedni model dla - możemy założyć dowolny równoważny model dla ; pozostanie oczywiście abstrakcyjne, ponieważ jest nieznany. W drugim podejściu możemy użyć bezpośrednio i zastosować do niego właściwości zamknięcia, aby uzyskać opis dla .L L L L L L LLLLLLL

Ran G.
źródło
4
Warto również zauważyć, że udowodnienie, że język jest skończony, wystarczy, aby pokazać, że jest on regularny. Może to być przydatne, szczególnie w przypadku dowodów niekonstruktywnych w poszczególnych przypadkach.
Patrick87
2
Wyrażenia regularne znalezione w językach programowania mogą zrobić znacznie więcej niż zwykłe języki. Musiałbyś ograniczyć się do „klasycznych” konstrukcji.
David Lewis,
4
@DavidLewis: Na tej stronie można założyć, że przez „wyrażenie regularne” rozumie się pojęcie klasyczne.
Raphael
@DavidLewis Zgadzam się, należy unikać wyrażenia regularnego w kontekście teorii, aby uniknąć nieporozumień.
Raphael
Zauważ, że dla każdego z pierwszych czterech pocisków potrzebujesz dowodu, że twoja reprezentacja jest rzeczywiście poprawna.
Raphael
10

Metody elementarne

  1. Automaty skończone (być może niedeterministyczne, z pustymi przejściami).
  2. Wyrażenia regularne.
  3. Prawy (lub Lewy, ale nie oba) równania liniowe, takie jak gdzie i są regularne.K LX=KX+LKL
  4. Gramatyka regularna (typ 3).
  5. Operacje zachowujące zwykłe języki (operacje boolowskie, iloczyn, gwiazda, losowanie, morfizmy, odwrotności morfizmów, odwracanie itp.)
  6. Rozpoznany przez skończoną monoidę.

Metody logiczne (często stosowane w formalnej weryfikacji)

  1. Monadyczna logika drugiego rzędu (twierdzenie Büchiego).
  2. Liniowa logika czasowa (twierdzenie Kampa).
  3. Twierdzenie o drzewie Rabina (logika monadyczna drugiego rzędu z dwoma następcami). Bardzo potężny.

Metody zaawansowane

  1. Wyrafinowane lematy pompujące. Patrz na przykład
    [1] J. Jaffe, Niezbędny i wystarczający lemat pompowania dla zwykłych języków, Sigact News - SIGACT 10 (1978) 48-49.
    [2] A. Ehrenfeucht, R. Parikh i G. Rozenberg, Pompowanie lematów dla zbiorów regularnych, SIAM J. Comput. 10 (1981), 536–541.
    [3] S. Varricchio, Warunek pompowania dla regularnych zestawów, SIAM J. Comput. 26 (1997) 764–771.

  2. Cóż, quasi-zamówienia. Patrz
    [4] W. Bucher, A. Ehrenfeucht, D. Haussler, O wszystkich regulatorach generowanych przez relacje derywacji, Theor. Comput. Sci. 40 (1985) 131–148.
    [5] M. Kunz, Regularne rozwiązania nierówności językowych i quasi-zamówienia .

  3. Obsługa racjonalnej serii .N

  4. Metody algebraiczne oparte na Transdukcjach (patrz także Operacje zachowujące zwykłe języki ).

J.-E. Kołek
źródło
4

Odpowiedź Ran G. podaje dość obszerną listę równoważnych modeli, których można użyć do określenia zwykłych języków (i lista jest długa, automaty dwukierunkowe, logika MSO, ale jest to objęte linkiem pod „bardziej równoważnymi modelami ”). I jak podkreśla Raphael, potrzebujemy argumentu, aby przekonać odbiorców, że wybrana reprezentacja jest rzeczywiście poprawna.

Rozpatrując pytanie, dodaje „Na przykład ”. Oznacza to, że musimy podać prawidłową konstrukcję, która przy założeniu , że w każdym z powyższych modeli określimy język , zamienia ten model w jeden dla . Zasadniczo będzie to ten sam typ modelu, ale nie musi tak być: możemy np. Zacząć od deterministycznego FSA dla i skończyć z nieokreślonym dla .L L L L LLLL

Obejmuje to możliwość użycia operacji zamknięcia: w jawnie podanej operacji w przykładzie mamy .L=(ΣL)Σ

Chodzi mi o to, że odpowiedź jest świetna, ale powinniśmy dodać „konstrukcję od do ”, gdy nie budujemy od podstaw konkretnego języka.L LL

Hendrik Jan
źródło
1
Nie jestem do końca pewien, do czego zmierzasz. Jeśli mam jakiś model dla , mogę przekonwertować go na dowolny inny równoważny. L
Raphael
@Raphael Przepraszam, że mam rację. Wcześniejsze odpowiedzi wydają się wyjaśniać, że możemy skonstruować opis języka (jako automat, operacje itp.). Zgadzam się. Wydaje się jednak, że pytanie dotyczy właściwości zamknięcia, patrz podany przykład. Tej kwestii brakuje mi w innych odpowiedziach: aby udowodnić właściwość zamknięcia, zakładasz, że masz opis, i skonstruuj nową.
Hendrik,
1
Ach, to ! Teraz rozumiem, mój zły. Zgadzam się, tego aspektu brakuje w odpowiedzi Ran. L
Raphael
1
Nie jestem pewien, dlaczego brakuje (ani czego dokładnie brakuje). Załóżmy, że masz regularne„a ty chcesz udowodnić jest regularny, a także, można zacząć od „s DFA i użyć go do budowy DFA dla . Ale jest to objęte „konstruowaniem DFA dla ” .. nie ma żadnych ograniczeń w używaniu automatu do tego zadania (i oczywiście, jeśli jest zdefiniowane przez , będziesz zmuszony użyć automatu ). . To samo dotyczy wyrażeń regularnych, zamykania, gramatyki itp. L L L L L L L L LLLLLLLLL
Ran G.
1
OK Właściwie wolę edytować pytanie i usunąć część „na przykład”, dzięki czemu pytanie jest bardziej ogólne i odniesienie do przyszłych podobnych pytań .. (:
Ran G.
4

Od czasu do czasu można spotkać język określony jako „wszystkie ciągi gdzie każdy -elementowe podciąg spełnia ”, gdzie jest jakaś ustalona na stałym poziomie. W takim przypadku język będzie prawidłowy. Chodzi tutaj o zdefiniowanie automatu skończonego, którego niektóre stany „zapamiętują” ostatnio oglądane symboli wejściowych, jak w odpowiedzi na to pytanie .k s k ksks<some property>kk

Rick Decker
źródło
4

Inną metodą, nieuwzględnioną w powyższych odpowiedziach, jest skończona transformacja automatu . Jako prosty przykład pokażmy, że zwykłe języki są zamknięte podczas operacji losowej , zdefiniowanej w następujący sposób: Możesz pokazać zamknięcie za pomocą właściwości zamknięcia, ale możesz też pokazać je bezpośrednio za pomocą DFA. Załóżmy, że jest DFA, który akceptuje (dla ). Konstruujemy nowy DFA w następujący sposób:

L1SL2={x1y1xnynΣ:x1xnL1,y1ynL2}
Ai=Σ,Qi,Fi,δi,q0iLii=1,2Σ,Q,F,δ,q0
  • Zbiór stanów to , gdzie trzeci składnik pamięta, czy następny symbol to (gdy 1) czy (gdy 2).Q1×Q2×{1,2}xiyi
  • Stan początkowy to .q0=q01,q02,1
  • Stany akceptujące to .F=F1×F2×{1}
  • Funkcja przejścia jest zdefiniowana przez i .δ(q1,q2,1,σ)=δ1(q1,σ),q2,2δ(q1,q2,2,σ)=q1,δ2(q2,σ),1

Bardziej wyrafinowana wersja tej metody wymaga zgadywania . Jako przykład pokażmy, że zwykłe języki są zamknięte podczas cofania , to znaczy (Tutaj .) Jest to jedna ze standardowych operacji zamykania, a zamykanie w odwróceniu łatwo wynika z manipulacji wyrażeniami regularnymi (które można uznać za odpowiednik skończonej transformacji automatu do wyrażenia regularne) - wystarczy odwrócić wyrażenie regularne. Ale możesz również udowodnić zamknięcie za pomocą NFA. Załóżmy, że jest akceptowane przez DFA . Budujemy NFA

LR={wR:wΣ}.
(w1wn)R=wnw1LΣ,Q,F,δ,q0Σ,Q,F,δ,q0 , gdzie
  • Zestaw stanów to .Q=Q{q0}
  • Stan początkowy to .q0
  • Unikalny stan akceptacji to .q0
  • Funkcja przejścia jest zdefiniowana następująco: , i dla dowolnego stanu i , .δ(q0,ϵ)=FqQσΣδ(q,σ)={q:δ(q,σ)=q}

(Możemy pozbyć się jeśli pozwolimy na wiele stanów początkowych.) Elementem zgadywania jest tutaj końcowy stan słowa po odwróceniu.q0


Zgadywanie często obejmuje również weryfikację. Jednym prostym przykładem jest zamykanie w rotacji : Załóżmy, że jest akceptowane przez DFA . Konstruujemy NFA , który działa w następujący sposób. Najpierw NFA zgaduje . Następnie sprawdza, czy i że , przechodząc od do niedeterministycznie. Można to sformalizować w następujący sposób:

R(L)={yxΣ:xyL}.
LΣ,Q,F,δ,q0Σ,Q,F,δ,q0q=δ(q0,x)δ(q,y)Fδ(q0,x)=qyx
  • Stany to . Oprócz stanu początkowego , stanami są , gdzie jest stanem, który zgadliśmy, jest stanem bieżącym, a określa, czy jesteśmy w część wkładu (przy 1) lub w strony wejścia (gdy 2).Q={q0}Q×Q×{1,2}q0q,qcurr,sqqcurrsyx
  • Końcowe stany to : akceptujemy, gdy .F={q,q,2:qQ}δ(q0,x)=q
  • Transitions implementują zgadywanie .δ(q0,ϵ)={q,q,1:qQ}q
  • Transitions (dla każdego i ) symulują oryginalny DFA.δ(q,qcurr,s,σ)=q,δ(qcurr,σ),sq,qcurrQs{1,2}
  • Przejścia , dla każdego i , implementacja przejścia z części do częśćJest to dozwolone tylko wtedy, gdy osiągnęliśmy stan końcowy w części .δ(q,qf,1,ϵ)=q,q0,2qQqfFyxy

Inny wariant techniki obejmuje ograniczniki. Jako przykład rozważmy zmianę zamknięcia odległości edycji : Biorąc pod uwagę DFA dla , e konstruujemy NFA dla następująco:

Ek(L)={xΣ: there exists yL whose edit distance from x is at most k}.
Σ,Q,F,δ,q0LΣ,Q,F,δ,q0Ek(L)
  • Zbiór stanów to , gdzie drugi element zlicza liczbę dokonanych do tej pory zmian.Q=Q×{0,,k}
  • Stan początkowy to .q0=q0,0
  • Stany akceptujące to .F=F×{0,,k}
  • Dla każdego mamy przejścia .q,σ,iδ(q,σ),iδ(q,i,σ)
  • Wstawienia są obsługiwane przez przejścia dla wszystkich takich, że .q,i+1δ(q,i,σ)q,σ,ii<k
  • Usunięcia są obsługiwane przez przejścia dla wszystkich takich, że .δ(q,σ),i+1δ(q,i,ϵ)q,σ,ii<k
  • Podstawienia są podobnie obsługiwane przez przejścia dla wszystkich takie, że .δ(q,σ),i+1δ(q,i,τ)q,σ,τ,ii<k
Yuval Filmus
źródło
3

Język jest zwykły, jeśli możesz napisać skaner, który decyduje o dowolnych ciągach znaków, niezależnie od tego, czy należą one do języka, używając nie więcej niż stałej ilości pamięci - tzn. Rozpoznanie można wykonać w przestrzeni O (1) .

reinierpost
źródło
Masz na myśli przestrzeń O (1)? W każdym razie jest to objęte faktem, że DFA wystarcza; warto wyraźnie zauważyć tę równoważność w zakresie programowania.
Raphael
Tak, to tylko inna perspektywa.
reinierpost
3

Transformacja wyrażeń regularnych jest jednym ze sposobów udowodnienia zamknięcia w niektórych operacjach. Dwa najprostsze przykłady to zamknięcie w wyniku odwrócenia i zamknięcie w przypadku homomorfizmu .

Biorąc pod uwagę wyrażenie regularne reprezentujące język , możemy skonstruować wyrażenie regularne dla , języka odwrotności wszystkich słów w , rekurencyjnie:rLLRL

  • ϵR=ϵ , , .σR=σR=
  • (r1+r2)R=(r1R+r2R) , , .(r)R=(rR)(r1r2)R=r2Rr1R

Wszystkie takie zdarzenie w końcowej zasady . Na przykład możesz sprawdzić, czy . Ustanawia indukcyjne strukturalne że język jest faktycznie . ( 0 1 ) R = 1 0 r R L R(r1r2)R=r2Rr1R(01)R=10rRLR

Innym prostym przykładem jest zamknięcie w warunkach homomorfizmu. Biorąc pod uwagę homomorfizm i wyrażenie regularne dla języka , możemy uzyskać wyrażenie regularne dla , zastępując każdą instancję in przez . r L h ( L ) σ r h ( σ )h:ΣΔrLh(L)σrh(σ)

Yuval Filmus
źródło
0

Innym sposobem jest zbudowanie języka za pomocą operacji, w ramach których wiesz, że są one zamknięte. Jest to rozszerzenie do wyrażania regularnego, ponieważ masz dużo więcej dostępnych operacji (odwróć ciąg, dopełniaj, przecinaj, odcinaj kawałek, po prostu zachowaj część, homomorfizmy i odwrotne homomorfizmy ...)

vonbrand
źródło
2
To już wspomniano w odpowiedzi Ran.
Raphael