Czy dany język regularny zawiera nieskończony podzbiór bez prefiksów?

Zestaw słów nad skończonym alfabetem nie zawiera prefiksu, jeśli nie ma dwóch odrębnych słów, w których jedno jest prefiksem drugiego.

Pytanie brzmi:

Jaka jest złożoność sprawdzania, czy zwykły język podany jako NFA zawiera nieskończony podzbiór bez prefiksów?

Odpowiedź (z powodu Michaiła Rudoya, tutaj poniżej) : Można to zrobić w czasie wielomianowym, a myślę, że nawet w NL.

Parafrazując odpowiedź Michaiła, niech będzie wejściowym NFA w normalnej formie (bez przejść epsilon, przycinanie) i niech (odpowiednio ) jest język uzyskać poprzez stan jak stanu początkowego i jako stanu końcowego (odp. stan jako inital i zestaw jako końcowy). Dla słowa niech będzie nieskończonym słowem uzyskanym przez iterację .$(\Sigma,q_0,F,\delta)$$L[p,r]$$L[p,R]$$p$$\{r\}$$p$$R$$u$$u^\omega$$u$

Następujące są równoważne:

1. Język $L[q_0,F]$ zawiera nieskończony podzbiór bez prefiksów.
2. $\exists q \in Q$ ,$\exists u \in L[q,q]\smallsetminus\{\varepsilon\}$ $\exists v \in L[q,F]$ więc$v$ nie jest przedrostkiem$u^\omega$ .
3. $\exists q \in Q$ $L[q,q] \neq \{\varepsilon\}$ $\forall u \in L[q,q]$ $\exists v \in L[q,F]$ więc$v$ nie jest prefiksem$u^\omega$ .

Dowód:

3 $\Rightarrow$ 2 trywialne.

Dla 2 $\Rightarrow$ 1 wystarczy zobaczyć, że dla dowolnego $w \in L[q_0,q]$ mamy, że $w (u^{|v|})^* v$ jest nieskończonym podzbiorem $L[q_0,F]$ .

Wreszcie, 1 3 jest dowodem „poprawności” w odpowiedzi Michaiła.$\Rightarrow$

Twój problem można rozwiązać w czasie wielomianowym.

Na początek przekonwertuj podany NFA na równoważny NFA z następującymi dodatkowymi właściwościami:

• Nie ma przejść epsilon
• Wszystkie stany są osiągalne od stanu początkowego

Pomocny podprogram

Załóżmy, że mamy NFA $N$ , stan $q$ i niepusty ciąg $s$ . Poniższy podprogram pozwoli nam ocenić wartość prawdy następującego wyrażenia: „każda ścieżka w $N$ od stanu $q$ do stanu akceptacji odpowiada ciągowi, który jest prefiksem ciągu $s^n$ dla niektórych $n$ .” Ponadto ten podprogram będzie działał w czasie wielomianowym.

Najpierw zbuduj NFA $S$ z $|s| + 1$ stanów, które akceptuje wszystkie ciągi, które nie są prefiksy $s^n$ dla dowolnego $n$ ( $|s|$ nie akceptują stany w pętli, aby śledzić, gdzie w „wzór” na $sssss\ldots$ jesteśmy tak daleko, i jeden akceptuje stan, jeśli już odeszliśmy od tego wzoru). Następnie skonstruuj NFA $N'$ który jest dokładnie jak $N$ ale ma $q$ jako stan początkowy. Na koniec skonstruuj ostateczną NFA $N''$którego językiem jest przy użyciu standardowej konstrukcji skrzyżowania NFA. Zauważ, że wszystkie te konstrukcje są wielomianowe pod względem wielkości danych wejściowych.$L(N'')$$L(S) \cap L(N')$

Następnie po prostu sprawdź, czy język jest pusty (co można zrobić w czasie wielomianowym za pomocą prostego wyszukiwania grafowego). wtedy i tylko wtedy, gdy , lub innymi słowy, każdy łańcuch w nie jest w L ( S ) . Innymi słowy, język N ″ jest pusty wtedy i tylko wtedy, gdy N ′ akceptuje tylko ciągi znaków, które są prefiksami s n dla niektórych n . Można to przeformułować jako dokładnie stwierdzenie, które próbowaliśmy ocenić: „każda ścieżka w N od stanu q$N''$$L(N'') = \emptyset$$L(S) \cap L(N') = \emptyset$$L(N')$$L(S)$$N''$$N'$$s^n$$n$$N$$q$stan akceptacji odpowiada ciągowi, który jest przedrostkiem ciągu $s^n$ dla niektórych $n$ . "

Główny algorytm

Rozważ zestaw stanów w NFA, które są w jakiejś pętli. Dla każdego takiego stanu $q$ wykonaj następujące czynności:

Niech $P_2$ będzie dowolną prostą pętlą zawierającą $q$ . Niech $s$ jako ciąg odpowiadający pętli $P_2$ . Ponieważ NFA nie ma przejść epsilon, $s$ nie jest pusty. Następnie zastosuj podprogram do NFA, stan $q$ i łańcuch $s$ . Jeśli podprogram mówi nam, że każda ścieżka rozpoczynająca się od $q$ w NFA i kończąca się na stanie akceptacji odpowiada prefiksowi $s^n$ dla niektórych $n$ to przechodzi do następnego stanu $q$ . W przeciwnym razie wyjdź, że dany język NFA zawiera nieskończony podzbiór wolny od prefiksów.

Jeśli spróbujemy każdego stanu $q$ który jest w pętli, a algorytm nigdy nie wyprowadza danych wyjściowych, oznacza to, że język danego NFA nie zawiera nieskończonego podzbioru wolnego od prefiksów.

Prawidłowość (pierwsza połowa)

Po pierwsze, załóżmy, że powyższy algorytm stwierdza, że ​​dany język NFA zawiera nieskończony podzbiór wolny od prefiksów. Powiedzmy, że ta moc została wybrana przy rozpatrywaniu trochę pętli $P_2$ i niektóre państwa $q$ . Tak jak poprzednio, $s$ jest łańcuchem odpowiadające $P_2$ . Następnie wiemy zgodnie z podprogramem, że nie każda ścieżka rozpoczynająca się od $q$ w NFA i kończąca się na stanie akceptacji odpowiada przedrostkowi $s^n$ dla niektórych $n$ (ponieważ jest to jedyne wyjście podprogramu, które prowadzi do głównego algorytmu wyjście w tym $q$ ).

Niech $P_3$ będzie ścieżką, której istnienie jest zapewnione przez podprogram: ścieżka od $q$ do stanu akceptacji, tak że odpowiadający ciąg $t$ nie jest przedrostkiem $s^n$ dla żadnego $n$ .

Niech $P_2'$ składa się z $m$ kopii $P_2$ gdzie $m$ jest wystarczająco duży, aby $m|s| > |t|$. Ponieważ $P_2$ jest pętli $q$ , $P_2'$ mogą być traktowane jako tor z $q$ na $q$ . Ciąg odpowiadający $P_2'$ to $s^m$

Niech $P_1$ będzie ścieżką od stanu początkowego do $q$ (która istnieje, ponieważ każdy stan jest osiągalny od początku) i niech $r$ będzie łańcuchem odpowiadającym tej ścieżce.

Zatem ścieżka składająca się z $P_1$ , $x$ kopii $P_2'$ i $P_3$ jest ścieżką obliczeń akceptujących. Ciąg odpowiadający tej ścieżce to $r(s^m)^xt$ . Zatem NFA akceptuje każdy ciąg postaci $r(s^m)^xt$ . Jest to nieskończony zestaw ciągów akceptowanych przez NFA i twierdzę, że ten zestaw ciągów nie zawiera prefiksów. W szczególności załóżmy, że $r(s^m)^xt$ jest przedrostkiem $r(s^m)^yt$ z$y > x$ . Innymi słowy,$t$ jest prefiksem$(s^m)^{y-x}t$ . Ponieważ$(s^m)^{y-x}$ ma długość$m(y-x)|s| \ge m|s| > |t|$oznacza to, że$t$ jest prefiksem$(s^m)^{y-x} = s^{m(y-x)}$ . Ale wiemy na podstawie wyniku podprogramu, że$t$nie jest przedrostkiem$s^n$ dla żadnego$n$. Zatem$r(s^m)^xt$nie może być prefiksem$r(s^m)^yt$, a zgodnie z potrzebami zestaw ciągów znaków nie zawiera prefiksu.

Dlatego pokazałem, że jeśli główny algorytm wypisuje, że język danego NFA zawiera nieskończony podzbiór wolny od prefiksów, to w rzeczywistości tak jest.

Prawidłowość (druga połowa)

Następnie pokażę drugą połowę: jeśli język danego NFA zawiera nieskończony podzbiór wolny od prefiksów, to główny algorytm wypisze ten fakt.

Załóżmy, że dany język NFA zawiera nieskończony podzbiór bez prefiksów. Niech $A$ będzie zbiorem (akceptujących) ścieżek obliczeniowych odpowiadających tym ciągom. Zauważ, że $A$ jest nieskończonym zestawem akceptujących ścieżek obliczeniowych, których odpowiadające ciągi nigdy nie są przedrostkami.

Powiedz, że stan „zapętla się” w NFA, jeśli istnieje pętla w NFA przez ten stan, a w przeciwnym razie „nie zapętla”. Rozważ wszystkie ścieżki od stanu początkowego do dowolnego stanu zapętlenia, które przechodzą tylko przez stany niepętlowe (z wyjątkiem jednego stanu zapętlenia, w którym się kończą). Niech $P$ będzie zbiorem tych ścieżek. Każda ścieżka $p \in P$ nie może mieć pętli, ponieważ wówczas stany w tej pętli byłyby stanami pętli, a zatem $p$ przechodziłoby przez stan pętli. Tak więc długości ścieżek w $P$ są ograniczone przez liczbę stanów w NFA, a zatem $P$ jest skończone (na przykład, jeśli stan początkowy jest stanem zapętlonym, wówczas jedyną taką ścieżką jest pusta ścieżka).

Możemy podzielić $A$ na $|P|+1$ podzestawy na podstawie tego, jak zaczynają się ścieżki obliczeniowe w $A$W szczególności, w przypadku $p \in P$ , niech P jest zbiorem wszystkich ścieżek obliczeń w A, które zaczynają się od ścieżki P i pozwolić B jest zbiorem wszystkich innych ścieżek A . Oczywiście, wszystkie P S i B są rozłączne i ich suma jest cały zestaw . Ponadto B.$A_p$$A$$p$$B$$A$$A_p$$B$$A$$B$zawiera tylko ścieżki, które nigdy nie przechodzą przez stan zapętlenia, a zatem nigdy nie zapętlają; zatem $B$ jest skończone. Możemy zatem dojść do wniosku, że niektóre $A_p$ muszą być nieskończone (w przeciwnym razie $A$ byłby związkiem skończonych wielu zbiorów skończonych).

Ponieważ $A_p$ jest nieskończone, istnieje nieskończenie wiele ścieżek obliczeniowych, z których żaden łańcuch nie jest przedrostkiem, które akceptują ścieżki zaczynające się od $p$ . Niech $q$ będzie stanem osiągniętym na końcu ścieżki $p$ . Możemy dojść do wniosku, że istnieje nieskończenie wiele ścieżek akceptujących, nazwijmy ten zestaw $A'$ , zaczynając od $q$ wszystkie, które odpowiadają ciągom znaków, które nie są przedrostkami.

Podczas głównego algorytmu uruchamiamy podprogram w stanie $q$ i niektórych ciągach $s$ . Ten podprogram mówi nam, czy każda akceptowalna ścieżka rozpoczynająca się od $q$ odpowiada ciągowi, który jest prefiksem $s^n$ dla niektórych $n$ . Gdyby tak było, wszystkie nieskończenie wiele ścieżek akceptujących w $A'$ byłyby prefiksami $s^n$ dla różnych $n$ , co oznaczałoby, że wszystkie one są przedrostkami siebie. Tak nie jest, więc dochodzimy do wniosku, że gdy główny algorytm uruchamia podprogram w stanie $q$, wynikiem jest inny możliwy wynik. To jednak prowadzi główny algorytm do wyjścia, że ​​język NFA zawiera nieskończony podzbiór wolny od prefiksów.

To kończy dowód poprawności.

Definicje

Definicja 1 : Niech $S$ będzie zbiorem słów. Mówimy, że $S$ jest ładnie nieskończenie wolny od przedrostka (wymyślona nazwa na potrzeby tej odpowiedzi), jeśli istnieją słowa $u_0,\dots,u_n,\dots$ i $v_1,\dots,v_n,\dots$ takie, że:

• Dla każdego $n\ge 1$ , $u_n$ i $v_n$ są niepuste i zaczynają się od odrębnych liter;

• $S=\{u_0v_1,\dots,u_0\dots u_n v_{n+1},\dots\}$ .

Intuicja polega na tym, że możesz umieścić wszystkie te słowa na nieskończonym ukorzenionym drzewie ( ■jest to korzeń, ▲są liście i •pozostałe są wewnętrzne węzły) o następującym kształcie, tak że słowa w $S$ są dokładnie etykietami ścieżek od korzenia do liścia:

   u₀    u₁    u₂
■-----•-----•-----•⋅⋅⋅
      |     |     |
      | v₁  | v₂  | v₃
      |     |     |
      ▲     ▲     ▲

Twierdzenie 1.1 : Ładnie nieskończony zbiór bez prefiksów jest bez prefiksów.

Dowód zdania 1.1 : Załóżmy, że $u_0\dots u_n v_{n+1}$ jest ścisłym przedrostkiem $u_0 \dots u_m v_{m+1}$ . Istnieją dwa przypadki:

• Jeśli $n < m$ to $v_{n+1}$ jest prefiksem $u_{n+1}\dots u_m v_{m+1}$ . Jest to niemożliwe, ponieważ $u_{n+1}$ i $v_{n+1}$ mają wyraźne pierwsze litery.

• Jeśli $n > m$ to $u_{m+1}\dots u_n v_{n+1}$ jest prefiksem $v_{m+1}$ . Jest to niemożliwe, ponieważ $u_{m+1}$ i $v_{m+1}$ mają wyraźne pierwsze litery.

Twierdzenie 1.2 : Ładnie nieskończony zbiór bez prefiksów jest nieskończony.

Dowód tezy 1,2 W dowód 1.1, wykazano, że jeśli $n\not= m$ wówczas $u_0\dots u_n v_{n+1}$ i $u_0 \dots u_m v_{m+1}$ nie są porównywalne w celu prefiks. Dlatego nie są równi.

Główny dowód

Twierdzenie 2 : Dowolny nieskończony zbiór bez prefiksów zawiera niezły nieskończony zbiór bez prefiksów.

Twierdzenie 3 : Język zawiera nieskończony zbiór bez prefiksów tylko wtedy, gdy zawiera ładnie nieskończony zbiór bez prefiksów.

Dowód poniżej.

Dowód zdania 3 : $\boxed{\Rightarrow}$ według zdania 2. $\boxed{\Leftarrow}$ według zdań 1.1 i 1.2.

Twierdzenie 4 : Zbiór ładnie pozbawionych prefiksów podzbiorów języka regularnego (zakodowanych jako nieskończone słowo $\overline{u_0}\widehat{v_1}\overline{u_1}\widehat{v_2}\overline{u_2}\dots$ ) jest $\omega$ nieregularny (i ma rozmiar Büchi automat rozpoznający to wielomian wielkości NFA rozpoznającej zwykły język).

Dowód poniżej.

Twierdzenie 5 : Podejmowanie decyzji, czy zwykły język opisany przez NFA zawiera nieskończony podzbiór wolny od prefiksów, można wykonać wielomianem czasowym wielkości NFA.

Dowód twierdzenia 5 : Według twierdzenia 3 wystarczy sprawdzić, czy zawiera on ładnie nieskończony podzbiór wolny od prefiksów, co można zrobić w czasie wielomianowym, budując automat Büchi podany w twierdzeniu 4 i testując niepustość jego język (który można wykonać w czasie liniowo w rozmiarze automatu Büchi).

Dowód propozycji 2

Lemat 2.1 : Jeśli $S$ jest zbiorem bez prefiksów, to także $w^{-1}S$ (dla dowolnego słowa $w$ ).

Dowód 2.1 : Z definicji.

Lemat 2.2 : Niech $S$ będzie nieskończonym zestawem słów. Niech $w:=\operatorname{lcp}(S_n)$ najdłuższa prefiks wspólne dla wszystkich słów $S$ . $S$ i $w^{-1}S$ mają tego samego kardynała.

Dowód 2.2 : Zdefiniuj $f:w^{-1}S\to S$ przez $f(x)=wx$ . Jest dobrze zdefiniowany przez definicję $w^{-1}S$ , iniekcyjny z definicji $f$ i przymiotnikowy z definicji $w$ .

Dowód tezy 2 Budujemy $u_n$ i $v_n$ przez indukcję $n$ , z założenia indukcyjnego $H_n$ składa się z następujących części:

• $(P_1)$ For all $k\in\{1,\dots,n\}$, $u_0\dots u_{k-1} v_k \in S$;

• $(P_2)$ For all $k\in\{1,\dots,n\}$, $u_k$ and $v_k$ are non-empty and start with distinct letters;

• $(P_3)$ $S_n:=(u_0\dots u_n)^{-1}S$ is infinite;

• $(P_4)$ There is no non-empty prefix common to all words in $S_n$. In other words: There is no letter $a$ such that $S_n\subseteq a\Sigma^*$.

Remark 2.3: If we have sequences that verify $H_n$ without $(P_4)$, we can modify $u_n$ to make them to also satisfy $(P_4)$. Indeed, it suffices to replace $u_n$ by $u_n\operatorname{lcp}(S_n)$. $(P_1)$ is unaffected. $(P_2)$ is trivial. $(P_4)$ is by construction. $(P_3)$ is by lemma 3.

We now build the sequences by induction on $n$:

• Initialization: $H_0$ is true by taking $u_0:=\operatorname{lcp}(S)$ (i.e. by taking $u_0:=\varepsilon$ and applying remark 3.1).

• Induction step: Suppose that we have words $u_1,\dots,u_n$ and $v_1,\dots,v_n$ such that $H_n$ for some $n$. We will build $u_{n+1}$ and $v_{n+1}$ such that $H_{n+1}$.

Since $S_n$ is infinite and prefix-free (by lemma 1), it does not contain $\varepsilon$ so that $S_n=\underset{a\in \Sigma}{\bigsqcup}(S_n\cap a\Sigma^*)$. Since $S_n$ is infinite, there is a letter $a$ such that $S_n\cap a\Sigma^*$ is infinite. By $(P_4)$, there is a letter $b$ distinct from $a$ such that $S_n\cap b\Sigma^*$ is non-empty. Pick $v_{n+1}\in S_n\cap b\Sigma^*$. Taking $u_{n+1}$ to be $a$ would satisfy $(P_1)$, $(P_2)$ and $(P_3)$ so we apply remark 3.1 to get $(P_4)$: $u_{n+1}:=a\operatorname{lcp}(a^{-1}S_n)$.

$(P_1)$ $u_1\dots u_nv_{n+1}\in u_1\dots u_n(S_n\cap b\Sigma^*)\subseteq S$.

$(P_2)$ By definition of $u_{n+1}$ and $v_{n+1}$.

$(P_3)$ $a^{-1}S_n$ is infinite by definition of $a$, and $S_{n+1}$ is therefore infinite by lemma 3.

$(P_4)$ By definition of $u_{n+1}$.

Proof of proposition 4

Proof of proposition 4: Let $A=(Q,\to,\Delta,q_0,F)$ be a NFA.

The idea is the following: we read $u_0$, remember where we are, read $v_1$, backtrack to where we were after reading $u_0$, read $u_1$, remember where we are, ... We also remember the first letter that was read in each $v_n$ to ensure that $u_n$ starts with another letter.

I've been told that this could be easier with multi-head automata but I'm not really familiar with the formalism so I'll just describe it using a Büchi automaton (with only one head).

We set $\Sigma':=\overline{\Sigma}\sqcup\widehat{\Sigma}$, where the overlined symbols will be used to describes the $u_k$s and the symbols with hats for the $v_k$s.

We set $Q':=Q\times (\{\bot\}\sqcup (Q \times \Sigma))$, where:

• $(q,\bot)$ means that you are reading some $u_n$;

• $(q,(p,a))$ means that you finished reading some $u_n$ in the state $p$, that you are now reading $v_{n+1}$ that starts with an $a$, and that once you are done, you will go back to $p$ to read a $u_{n+1}$ that does not start with $a$.

We set $q_0':=(q_0,\bot)$ because we start by reading $u_0$.

We define $F'$ as $F\times Q \times \Sigma$.

The set of transitions $\to'$ is defined as follows:

• "$u_n$" For each transition $q\overset{a}{\to}q'$, add $(q,\bot)\overset{\overline{a}}{\to'}(q',\bot)$;

• "$u_n$ to $v_{n+1}$" For each transition $q\overset{a}{\to}q'$, add $(q,\bot)\overset{\widehat{a}}{\to'}(q',(q,a))$;

• "$v_n$" For each transition $q\overset{a}{\to}q'$, add $(q,(p,a))\overset{\widehat{a}}{\to'}(q',(p,a))$;

• "$v_n$ to $u_n$" For each transition $p\overset{a}{\to}p'$ where $p$ is final and letter $b$ distinct from $a$, add $(q,(p,b))\overset{\overline{a}}{\to'}(p',\bot)$;

Lemma 4.1: $\overline{u_0}\widehat{v_1}\overline{u_1}\widehat{v_2}\dots \overline{u_n}\widehat{v_{n+1}}$ is accepted by $A'$ iff for each $n\ge 1$, $u_n$ and $v_n$ are non-empty and start with distinct letters, and for each $n\ge 0$, $u_0\dots u_n v_{n+1}\in L(A)$.

Proof of lemma 4.1: Left to the reader.