Specjalna klasa języków: języki „okrężne”. Czy to jest znane

20

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: $w$ $\Sigma^*$

$w$ należy do L wtedy i tylko wtedy, gdy dla wszystkich liczb całkowitych , należy do L. $k > 0$ $w^k$

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

1

To bardzo interesujące pytanie. Dwa powiązane pytania: 1) jeśli mamy zwykły język L i powiązany DFA, czy możemy sprawić, by był okrągły? 2) Czy w danym języku L jest tak, że circ (L) jest regularny lub ma jakieś fajne właściwości?

— Suresh Venkat,

ps może to jest oczywiste, ale dlaczego uważasz, że języki okrężne są podklasą zwykłych języków?

— Suresh Venkat,

3

@Suresh, myślę, że definiuje on język jako kolisty, jeśli jest to a) regularny; b) spełnia właściwość zamknięcia

\forall w \in L, n \in N : w^{n} \in L

$\forall w \in L, n \in \mathbb{N} : w^n \in L$ .

— Peter Taylor

Crosspost w MO .

— Hsien-Chih Chang 張顯之 12.01.11

1

Może nie należy pisać podziękowań, ale to było moje pierwsze pytanie i bardzo doceniłem jakość komentarzy, odpowiedzi i dyskusji. Dzięki.

— vincenzoml

19

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 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^+$ $r$ $\sum 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 . Wykazał „z natury dwuznaczny” język. $\sum r_i^*$ $\sum 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 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 , otrzymujemy stany takie, że akceptuje tylko jeden z pozostałych nie akceptuje (jeśli wszystkie z nich akceptują, to sekwencja musi cyklicznie, aby zawsze było w języku). Innymi słowy, mamy ścieżkę od $w$ $s_0$ $s_1,\ldots,s_n$ $s_1$ $s_0,\ldots,s_n$ $w^*$ do gdzie akceptuje, ale jeden z pozostałych nie akceptuje. I odwrotnie, jeśli język jest okrągły, to nie może się zdarzyć. $s_0,\ldots,s_{n-1}$ $s_1,\ldots,s_n$ $s_1$

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 i klauzule . Możemy założyć, że (dodaj zmienne fikcyjne) i że jest liczbą pierwszą (w przeciwnym razie znajdź liczbę pierwszą między a za pomocą testowania pierwotności AKS, i dodaj zmienne fikcyjne i klauzule). $n$ $\vec{x}$ $m$ $C_1,\ldots,C_m$ $n = m$ $n$ $n$ $2n$

Rozważ następujący język: „dane wejściowe nie mają formy gdzie jest zadowalającym przypisaniem dla ”. Łatwo jest zbudować DFA dla tego języka. Jeśli język nie jest okrągły, wówczas w języku znajduje się słowo , którego mocy nie ma w języku. Ponieważ jedyne słowa spoza języka mają długość , musi mieć długość lub . Jeśli ma długość $\vec{x}_1 \cdots \vec{x}_n$ $\vec{x}_i$ $C_i$ $O(n^2)$ $w$ $n^2$ $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. $w^n$ $w$ $w^n$ $w^n$ $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$ $w^n$

W tej części omawiamy normalną formę dla języków okrężnych. Rozważmy pewien DFA dla okrągłej języka . Sekwencja jest prawdziwa, jeśli (stan początkowy), wszystkie inne stany akceptują, a oznacza . 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 = C_0,\ldots$ $C_0 = s$ $C_i = C_j$ $C_{i+1} = C_{j+1}$

Mówimy, że słowo zachowuje się zgodnie z $C$ jeśli bierze ono DFA ze stanu do stanu , dla wszystkich . Zbiór wszystkich takich słów jest regularny (argument jest podobny do pierwszej części tej odpowiedzi). Należy zauważyć, że jest podzbiorem . $c_i$ $c_{i+1}$ $i$ $E(C)$ $E(C)$ $L$

Biorąc pod uwagę rzeczywistą sekwencję , zdefiniuj jako sekwencję . Sekwencja jest również prawdziwe. Ponieważ istnieje tylko skończenie wiele różnych sekwencji , język , która jest sumą wszystkich jest również regularne. $C$ $C^k$ $C^k(t) = C(kt)$ $C^k$ $C^k$ $D(C)$ $E(C^k)$

Twierdzimy, że ma właściwość, że jeśli to . Rzeczywiście, załóżmy, że i . Następnie . Zatem można zapisać w postaci $D(C)$ $x,y \in D(C)$ $xy \in D(C)$ $x \in C^k$ $y \in C^l$ $xy \in C^{k+l}$ $D(C) = D(C)^+$ dla niektórych wyrażeń regularnych . $r^+$ $r$

Każde słowo w pewnym językowych odpowiada rzeczywistym sekwencji , czyli istnieje realne sekwencji , które działa zgodnie. Zatem jest związek w ciągu wszystkich rzeczywistych kolejności . Dlatego każdy język okrągły ma reprezentację postaci . I odwrotnie, każdy taki język jest okrągły (trywialny). $w$ $C$ $C$ $w$ $L$ $D(C)$ $C$ $\sum r_i^+$

Rozważmy okrągły język wszystkich słów nad które zawierają albo liczbę parzystą, albo , albo parzystą liczbę (lub oba). Pokazujemy, że nie można go zapisać jako rozłącznej sumy ; przez „rozłączny” rozumiemy, że . $L$ $a,b$ $a$ $b$ $\sum r_i^+$ $r_i^+ \cap r_j^+ = \varnothing$

$N_i$ $r_i^+$ $N > \max N_i$ $x = a^N b^{N!}$ $x \in L$ $x \in r_i^+$ $i$ $x$ $N$ $r_i^+$ $z = a^{N!} b^{N!}$ $y = a^{N!} b^N$ $r_j^+$ $z$ $i \neq j$ $xy \notin L$ . Zatem reprezentacja nie może być rozłączna.

— Yuval Filmus
źródło

Wydaje się, że jest tu wiele błędów. Redukujesz z UNSAT, a nie SAT, więc pokazujesz, że jest to trudne dla CoNP. Jaki jest twój wielomian czasowy świadek (nie) członkostwa?

— Mark Reitblatt,

„Ponieważ jedyne słowa nie w języku mają długość ” Czy to nie powinno być ?

n^{2}

$n^2$

n m

$nm$

— Mark Reitblatt

Nie sądzę, że jest „trywialnie w CoNP”. Przynajmniej nie jest to dla mnie oczywiste. „Oczywistym” certyfikatem byłby ciąg w języku, a potęga taka, że nie jest w języku. Ale nie jest dla mnie od razu oczywiste, dlaczego takie słowo musi być wielomianowe. Może przeoczam prosty fakt teorii automatów.

l

$l$

k

$k$

l^{k}

$l^k$

— Mark Reitblatt,

Jeszcze poważniejszą pozorną wadą jest to, że przeskakujesz od każdej klauzuli indywidualnie do satysfakcjonującej, aż cała formuła jest satysfakcjonująca. Oczywiście, chyba że się mylę.

— Mark Reitblatt,

Zgadzam się, że nie jest jasne, że cykliczność jest w CoNP. Z drugiej strony nie widzę problemów w pozostałej części argumentu (teraz, gdy wstawiłem ). Jeśli każda klauzula jest spełniona przez to samo przypisanie, wówczas instancja 3SAT jest spełniona przez to przypisanie.

n = m

$n = m$

— Yuval Filmus

17

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.

— Jeffrey Shallit
źródło

6

@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). $>$ $\ge$

— Peter Taylor
źródło

Masz rację. Usunąłem mój niepoprawny post.

— Dave Clarke

Odnośnie adaptacji za pomocą

: Myślę, że minimalny DFA powinien zawsze mieć dokładnie jeden stan akceptacji, a mianowicie stan początkowy. Być może może się zdarzyć więcej stanów akceptujących, ale wtedy potrzebują one przejścia

do stanu początkowego.

\geq

$\geq$

ε

$\varepsilon$

— Raphael

1

@ Rafael, zastanów się ponownie L = a * | b *. DFA, którego stan początkowy jest jedynym stanem akceptującym i który akceptuje aib, musi zaakceptować (a | b) *.

— Peter Taylor

W kwestii rozstrzygalności ponownie: załóżmy, że masz DFA z

stanami, z których

akceptuje. Załóżmy, że akceptuje słowo

, a także akceptuje

,

, ...,

. Następnie akceptuje

dla

. (Dowód jest prostym zastosowaniem zasady szufladki). Jeśli można pokazać, że minimalny (minimalizujący

) kontrprzykład (

,

n

$n$

n_{a}

$n_a$

w

$w$

w^{2}

$w^2$

w^{3}

$w^3$

w^{n_{a} + 1}

$w^{n_a+1}$

w^{x}

$w^x$

x > 0

$x > 0$

| w |

$|w|$

w

$w$

x

$x$ ) do okrągłości języka akceptowanego przez DFA ma długość ograniczona funkcją

wówczas możliwe jest badanie siły brutalnej. Podejrzewam, że

, ale tego nie udowodniłem.

n

$n$

| w | <= n + 1

$|w| <= n+1$

— Peter Taylor

Kontynuacja powyższego pomysłu @ Raphael. Idea stanu początkowego = tylko stan akceptacji jest niewłaściwa dla tego problemu, ale przechwytuje kilka interesujących właściwości. Gdy M jest minDFA, stan początkowy jest jedynym stanem akceptacji wtedy i tylko wtedy, gdy L (M) jest gwiazdą Kleene języka bez prefiksów. To jedna z moich ulubionych ciekawostek DFA, dlatego szybko się nią dzielę! ;)

— mikero

5

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 $\omega$ , 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.

$A = (Q,\Sigma,\delta,q_0,F)$ $|Q|=n$ $L(A)$ $n^n$ $L(A)$ $w$ $n^n$ $w \in L(A)$ $w^k \notin L(A)$ $k \leq n$ $w$ $\delta_w(q) = \delta(q,w)$ $q \in Q$ $O(n\log n)$ $n^n$ $\delta_w(q_0) \in F$ $\delta_w^{(k)} \notin F$ $k \leq n$

$A_1,\ldots,A_n$ $p \in [n,2n]$ $A$

L (A) = \bar{{2 w_{1} 2 w_{2} \dots 2 w_{p} : w_{i} \in L (A_{1 + (i \mod n)})}} .

$L(A) = \overline{\{2w_12w_2\cdots2w_p : w_i \in L(A_{1+(i\mod{n})})\}}.$

A

$A$ również binarne.) Nietrudno jest zauważyć (używając faktu, że jest liczbą pierwszą), że jest kołowy tylko wtedy, gdy przecięcie jest puste.

p

$p$

L (A)

$L(A)$

L (A_{1}) \cap \dots \cap L (A_{n})

$L(A_1) \cap \cdots \cap L(A_n)$

— Yuval Filmus
źródło

0

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 \in L$ $p>0$ $xy^{i}z$ $x = z = \epsilon$ $y = w \neq \epsilon$ $|xy| \leq 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= \epsilon$

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$

— chazisop
źródło

1

Lemat pompowania jest koniecznym, ale niewystarczającym warunkiem prawidłowości. W szczególności istnieją języki nieregularne spełniające warunki pompowania. Twierdzenie Rice'a mówi również, że jest nierozstrzygalny. Nie oznacza to, że jest nierozstrzygalny (gdzie to DFA, a TM)! Na przykład, test pustki dla DFA jest rozstrzygalny, podczas gdy test pustki dla TM nie jest.

{⟨ M ⟩ | L (M) is circular}

$\{\langle M\rangle\vert L(M)\text{ is circular}\}$

{⟨ D ⟩ | L (D) is circular}

$\{\langle D\rangle\vert L(D)\text{ is circular}\}$

D

$D$

M

$M$

— alpoge 13.01.11

1

Oto niemożliwy do obliczenia język okrężny. Niech , gdzie to jakiś język, który nie jest obliczalny (np. Kody zatrzymujących baz TM). Wówczas jest okrągły, ale wyraźnie nieobliczalny (wyrocznia dla może być użyta do ustalenia ).

D = {0^{x} 1 : x \in R}

$D = \{ 0^x 1 : x \in R\}$

R

$R$

D^{*}

$D^*$

D^{*}

$D^*$

R

$R$

— Yuval Filmus

2

@Peter, czy przeczytałeś tę odpowiedź? Próbowano udowodnić, że każdy okrągły język (bez warunku regularności) jest regularny.

— Yuval Filmus

1

@Yuval, mój błąd. @chazisop, lemat pompujący jest przydatny do udowodnienia nieregularności języków, ale nie regularności. (Poza tym stwierdzenie pierwszego zdania sprowadza się do „Każde długości można zapisać jako gdzie ”, co jest wyraźnie fałszywe).

s \in L

$s \in L$

p > 0

$p > 0$

y^{i}

$y^i$

y \neq ϵ

$y \ne \epsilon$

— Peter Taylor

1

Tak, używam CIRCULARITY / TM, aby się do tego odnieść. OKOLICZNOŚĆ / DFA jest prawdopodobnie rozstrzygalne.

— chazisop 16.01.11