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

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 $L$$L'$

$\qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \}$

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

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

• deterministyczny automat skończony (DFA),
• niedeterministyczny automat skończony (NFA),
• wyrażenie regularne ( wyrażenie regularne języków formalnych) lub
• regularna gramatyka

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

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

• 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 $L$$L'$$L'$$L$$L$$L$$L'$

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 $X = KX + L$$K$$L$
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 .$\mathbb{N}$

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

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 $\dots$$L$$L'$$L$$L'$

Obejmuje to możliwość użycia operacji zamknięcia: w jawnie podanej operacji w przykładzie mamy .$L'= (\Sigma^* \setminus L) \cdot \Sigma^*$

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

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 $s$$k$$s$<some property>$k$$k$

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:

$$L_1 \mathop{S} L_2 = \{ x_1y_1 \ldots x_n y_n \in \Sigma^* : x_1 \ldots x_n \in L_1, y_1 \ldots y_n \in L_2 \}$$ $A_i = \langle \Sigma, Q_i, F_i, \delta_i, q_{0i} \rangle$$L_i$$i=1,2$$\langle \Sigma, Q, F, \delta, q_0 \rangle$

• Zbiór stanów to , gdzie trzeci składnik pamięta, czy następny symbol to (gdy 1) czy (gdy 2).$Q_1 \times Q_2 \times \{1,2\}$$x_i$$y_i$
• Stan początkowy to .$q_0 = \langle q_{01}, q_{02}, 1 \rangle$
• Stany akceptujące to .$F = F_1 \times F_2 \times \{1\}$
• Funkcja przejścia jest zdefiniowana przez i .$\delta(\langle q_1, q_2, 1 \rangle, \sigma) = \langle \delta_1(q_1,\sigma), q_2, 2 \rangle$$\delta(\langle q_1, q_2, 2 \rangle, \sigma) = \langle q_1, \delta_2(q_2,\sigma), 1 \rangle$

---

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

$$L^R = \{ w^R : w \in \Sigma^* \}.$$ $(w_1\ldots w_n)^R = w_n \ldots w_1$$L$$\langle \Sigma, Q, F, \delta, q_0 \rangle$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$ , gdzie

• Zestaw stanów to .$Q' = Q \cup \{q'_0\}$
• Stan początkowy to .$q'_0$
• Unikalny stan akceptacji to .$q_0$
• Funkcja przejścia jest zdefiniowana następująco: , i dla dowolnego stanu i , .$\delta'(q'_0,\epsilon) = F$$q \in Q$$\sigma \in \Sigma$$\delta(q', \sigma) = \{ q : \delta(q,\sigma) = 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.$q'_0$

---

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 \in \Sigma^* : xy \in L \}.$$ $L$$\langle \Sigma, Q, F, \delta, q_0 \rangle$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$$q=\delta(q_0,x)$$\delta(q,y) \in F$$\delta(q_0,x) = q$$y$$x$

• 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' = \{q'_0\} \cup Q \times Q \times \{1,2\}$$q'_0$$\langle q,q_{curr}, s \rangle$$q$$q_{curr}$$s$$y$$x$
• Końcowe stany to : akceptujemy, gdy .$F' = \{\langle q,q,2 \rangle : q \in Q\}$$\delta(q_0,x)=q$
• Transitions implementują zgadywanie .$\delta'(q'_0,\epsilon) = \{\langle q,q,1 \rangle : q \in Q\}$$q$
• Transitions (dla każdego i ) symulują oryginalny DFA.$\delta'(\langle q,q_{curr},s \rangle, \sigma) = \langle q,\delta(q_{curr},\sigma),s \rangle$$q,q_{curr} \in Q$$s \in \{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 .$\delta'(\langle q,q_f,1 \rangle, \epsilon) = \langle q,q_0,2 \rangle$$q \in Q$$q_f \in F$$y$$x$$y$

---

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:

$$E_k(L) = \{ x \in \Sigma^* : \text{ there exists $y \in L$ whose edit distance from $x$ is at most $k$} \}.$$ $\langle \Sigma, Q, F, \delta, q_0 \rangle$$L$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$$E_k(L)$

• Zbiór stanów to , gdzie drugi element zlicza liczbę dokonanych do tej pory zmian.$Q' = Q \times \{0,\ldots,k\}$
• Stan początkowy to .$q'_0 = \langle q_0,0 \rangle$
• Stany akceptujące to .$F' = F \times \{0,\ldots,k\}$
• Dla każdego mamy przejścia .$q,\sigma,i$$\langle \delta(q,\sigma), i \rangle \in \delta'(\langle q,i \rangle, \sigma)$
• Wstawienia są obsługiwane przez przejścia dla wszystkich takich, że .$\langle q,i+1 \rangle \in \delta'(\langle q,i \rangle, \sigma)$$q,\sigma,i$$i < k$
• Usunięcia są obsługiwane przez przejścia dla wszystkich takich, że .$\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \epsilon)$$q,\sigma,i$$i < k$
• Podstawienia są podobnie obsługiwane przez przejścia dla wszystkich takie, że .$\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \tau)$$q,\sigma,\tau,i$$i < k$

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

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:$r$$L$$L^R$$L$

• $\epsilon^R = \epsilon$ , , .$\sigma^R = \sigma$$\emptyset^R = \emptyset$
• $(r_1+r_2)^R = (r_1^R + r_2^R)$ , , .$(r^*)^R = (r^R)^*$$(r_1r_2)^R = r_2^R r_1^R$

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_1r_2)^R = r_2^R r_1^R$$(0^*1^*)^R = 1^*0^*$$r^R$$L^R$

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\colon \Sigma \to \Delta^*$$r$$L$$h(L)$$\sigma$$r$$h(\sigma)$

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