Zdefiniuj następującą klasę języków „okrągłych” nad skończonym alfabetem Sigma. W rzeczywistości nazwa już istnieje, aby oznaczać inną rzecz, która się wydaje, stosowana w dziedzinie przetwarzania DNA. AFAICT, to inna klasa języków.
Język L jest okrągła wtw dla wszystkich słów w , mamy:
należy do L wtedy i tylko wtedy, gdy dla wszystkich liczb całkowitych , należy do L.
Czy ta klasa języków jest znana? Interesują mnie języki obiegowe, które są również regularne, a w szczególności:
imię dla nich, jeśli są już znane
rozstrzygalność problemu, biorąc pod uwagę automat (w szczególności: DFA), czy zaakceptowany język jest zgodny z powyższą definicją
fl.formal-languages
automata-theory
regular-language
vincenzoml
źródło
źródło
Odpowiedzi:
W pierwszej części przedstawiamy wykładniczy algorytm decydujący o okrągłości. W drugiej części pokazujemy, że jest to trudny problem coNP. W trzeciej części pokazujemy, że każdy język okrągły jest połączeniem języków postaci (tutaj r może być pustym wyrażeniem regularnym); związek niekoniecznie jest rozłączny. W czwartej części pokazujemy okrągły język, którego nie można zapisać jako rozłączną sumę ∑ r + i .r+ r ∑r+i
Edycja: Wprowadzono poprawki po komentarzach Marka. W szczególności moje wcześniejsze twierdzenia, że cykliczność jest coNP-pełna lub NP-twarda są poprawione.
Edit: Poprawione normalną formę z do Ď R + I . Wykazał „z natury dwuznaczny” język.∑r∗i ∑r+i
Kontynuując komentarz Petera Taylora, oto jak zdecydować (wyjątkowo nieefektywnie), czy dany język jest okrągły, biorąc pod uwagę jego DFA. Skonstruuj nowy DFA, którego stany są czopami starych stanów. Ten nowy DFA obsługuje równolegle n kopii starego DFA.n n
Jeśli język nie jest okrągły, wówczas istnieje słowo tak że jeśli przepuszczamy go przez DFA wielokrotnie, zaczynając od stanu początkowego s 0 , otrzymujemy stany s 1 , … , s n takie, że s 1 akceptuje tylko jeden z pozostałych nie akceptuje (jeśli wszystkie z nich akceptują, to sekwencja s 0 , … , s n musi cyklicznie, aby w ∗ zawsze było w języku). Innymi słowy, mamy ścieżkę od s 0 , … , s nw s0 s1,…,sn s1 s0,…,sn w∗ do s 1 ,…, s n gdzie s 1 akceptuje, ale jeden z pozostałych nie akceptuje. I odwrotnie, jeśli język jest okrągły, to nie może się zdarzyć.s0,…,sn−1 s1,…,sn s1
Więc zredukowaliśmy problem do prostego ukierunkowanego testu osiągalności (po prostu sprawdź wszystkie możliwe „złe” pary).n
Problem okrężności jest trudny dla CoNP. Załóżmy, że mamy dane instancji 3SAT z zmiennymi → x i m klauzule C 1 , ... , C m . Możemy założyć, że n = m (dodaj zmienne fikcyjne) i że n jest liczbą pierwszą (w przeciwnym razie znajdź liczbę pierwszą między n a 2 n za pomocą testowania pierwotności AKS, i dodaj zmienne fikcyjne i klauzule).n x⃗ m C1,…,Cm n=m n n 2n
Rozważ następujący język: „dane wejściowe nie mają formy gdzie → x i jest zadowalającym przypisaniem dla C i ”. Łatwo jest zbudować O ( n 2 ) DFA dla tego języka. Jeśli język nie jest okrągły, wówczas w języku znajduje się słowo w , którego mocy nie ma w języku. Ponieważ jedyne słowa spoza języka mają długość n 2 , w musi mieć długość lub . Jeśli ma długośćx⃗ 1⋯x⃗ n x⃗ i Ci O(n2) w n2 w 1 n 1 , zamiast tego rozważ (wciąż jest w języku), aby było w języku, a nie było w języku. Fakt, że nie jest w języku oznacza, że jest zadowalającym zadaniem.wn w wn wn w
I odwrotnie, każde zadowalające przypisanie przekłada się na słowo potwierdzające niekołowość języka: zadowalające przypisanie należy do języka, ale nie. Tak więc język jest okrągły, jeśli instancja 3SAT jest niezadowalająca.w wn
W tej części omawiamy normalną formę dla języków okrężnych. Rozważmy pewien DFA dla okrągłej języka . Sekwencja C = C 0 , … jest prawdziwa, jeśli C 0 = s (stan początkowy), wszystkie inne stany akceptują, a C i = C j oznacza C i + 1 = C j + 1 . Tak więc każda prawdziwa sekwencja jest ostatecznie okresowa i istnieje tylko skończona liczba prawdziwych sekwencji (ponieważ DFA ma skończenie wiele stanów).L C=C0,… C0=s Ci=Cj Ci+1=Cj+1
Mówimy, że słowo zachowuje się zgodnie zC jeśli bierze ono DFA ze stanu do stanu c i + 1 , dla wszystkich i . Zbiór wszystkich takich słów E ( C ) jest regularny (argument jest podobny do pierwszej części tej odpowiedzi). Należy zauważyć, że E ( C ) jest podzbiorem L .ci ci+1 i E(C) E(C) L
Biorąc pod uwagę rzeczywistą sekwencję , zdefiniuj C k jako sekwencję C k ( t ) = C ( k t ) . Sekwencja C k jest również prawdziwe. Ponieważ istnieje tylko skończenie wiele różnych sekwencji C k , język D ( C ) , która jest sumą wszystkich E ( C k ) jest również regularne.C Ck Ck(t)=C(kt) Ck Ck D(C) E(Ck)
Twierdzimy, że ma właściwość, że jeśli x , y ∈ D ( C ), to x y ∈ D ( C ) . Rzeczywiście, załóżmy, że x ∈ C k i y ∈ C l . Następnie x y ∈ C k + l . Zatem D ( C ) = D ( C ) + można zapisać w postaci rD(C) x,y∈D(C) xy∈D(C) x∈Ck y∈Cl xy∈Ck+l D(C)=D(C)+ dla niektórych wyrażeń regularnych r .r+ r
Każde słowo w pewnym językowych odpowiada rzeczywistym sekwencji C , czyli istnieje realne sekwencji C , które w działa zgodnie. Zatem L jest związek R ( C ) w ciągu wszystkich rzeczywistych kolejności C . Dlatego każdy język okrągły ma reprezentację postaci ∑ r + i . I odwrotnie, każdy taki język jest okrągły (trywialny).w C C w L D(C) C ∑r+i
Rozważmy okrągły język wszystkich słów nad a , b, które zawierają albo liczbę parzystą, albo a , albo parzystą liczbę b (lub oba). Pokazujemy, że nie można go zapisać jako rozłącznej sumy ∑ r + i ; przez „rozłączny” rozumiemy, że r + i ∩ r + j = ∅ .L a,b a b ∑r+i r+i∩r+j=∅
źródło
Oto kilka artykułów omawiających te języki:
Thierry Cachat, Moc literowych języków racjonalnych, DLT 2001, Springer LNCS # 2295 (2002), 145-154.
S. Hovath, P. Leupold i G. Lischke, Korzenie i potęgi języków regularnych, DLT 2002, Springer LNCS # 2450 (2003), 220-230.
H. Bordihn, Wolność kontekstu potęgi języków bezkontekstowych jest nierozstrzygalna, TCS 314 (2004), 445–449.
źródło
@Dave Clarke, L = a * | b * byłoby koliste, ale L * byłoby (a | b) *.
Pod względem rozstrzygalności język jest okrągły, jeśli istnieje taki, że jest zamknięciem pod + lub jeśli jest skończonym połączeniem języków okrągłych.L L′ L L′
(Umieram przedefiniować „okrągły” wymieniając z . Upraszcza rzeczy dużo. Możemy wtedy charakteryzować języki okrągłe jak te, dla których istnieje NDFA którego począwszy państwo ma tylko epsilon-przejścia z akceptacją państw i ma przejście epsilon do każdego stanu akceptującego).> ≥
źródło
Edycja: Pełny (uproszczony) dowód kompletności PSPACE pojawia się poniżej.
Dwie aktualizacje. Po pierwsze, normalna forma opisana w mojej drugiej odpowiedzi pojawia się już w artykule Calbrixa i Nivata zatytułowanym Prefiks i języki okresowe racjonalnych langaugesω , niestety niedostępne online.
Po drugie, podejmowanie decyzji, czy język jest okrągły, biorąc pod uwagę jego DFA, jest kompletny z PSPACE.
źródło
Każde o długości można zapisać jako gdzie , . To oczywiste, że i . Wynika z tego, że język jest regularny dla niepustych danych wejściowych, dzięki lemacie pompującej.s∈L p>0 xyiz x=z=ϵ y=w≠ϵ |xy|≤p |y|=|w|>0
Dla obowiązuje definicja, ponieważ NDFA, który akceptuje pusty ciąg, akceptuje również dowolną liczbę pustych ciągów.w=ϵ
Zjednoczeniem powyższych języków jest język L, a ponieważ języki zwykłe są zamknięte w ramach unii, wynika z tego, że każdy język okrągły jest regularny.
Według twierdzenia Rice'a, jest nierozstrzygalna. Dowód jest podobny do regularności.CIRCULARITY/TM
źródło