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={x1y1…xnyn∈Σ∗:x1…xn∈L1,y1…yn∈L2}
Ai=⟨Σ,Qi,Fi,δi,q0i⟩Lii=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∈Σ∗}.
(w1…wn)R=wn…w1L⟨Σ,Q,F,δ,q0⟩⟨Σ,Q′,F′,δ′,q′0⟩ , gdzie
- Zestaw stanów to .Q′=Q∪{q′0}
- Stan początkowy to .q′0
- Unikalny stan akceptacji to .q0
- Funkcja przejścia jest zdefiniowana następująco: , i dla dowolnego stanu i , .δ′(q′0,ϵ)=Fq∈Qσ∈Σδ(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.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∈Σ∗:xy∈L}.
L⟨Σ,Q,F,δ,q0⟩⟨Σ,Q′,F′,δ′,q′0⟩q=δ(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′={q′0}∪Q×Q×{1,2}q′0⟨q,qcurr,s⟩qqcurrsyx
- Końcowe stany to : akceptujemy, gdy .F′={⟨q,q,2⟩:q∈Q}δ(q0,x)=q
- Transitions implementują zgadywanie .δ′(q′0,ϵ)={⟨q,q,1⟩:q∈Q}q
- Transitions (dla każdego i ) symulują oryginalny DFA.δ′(⟨q,qcurr,s⟩,σ)=⟨q,δ(qcurr,σ),s⟩q,qcurr∈Qs∈{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,2⟩q∈Qqf∈Fyxy
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 y∈L whose edit distance from x is at most k}.
⟨Σ,Q,F,δ,q0⟩L⟨Σ,Q′,F′,δ′,q′0⟩Ek(L)
- Zbiór stanów to , gdzie drugi element zlicza liczbę dokonanych do tej pory zmian.Q′=Q×{0,…,k}
- Stan początkowy to .q′0=⟨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