Defina a seguinte classe de idiomas "circulares" sobre um alfabeto finito Sigma. Na verdade, o nome já existe para denotar uma coisa diferente que parece, usada no campo da computação de DNA. AFAICT, essa é uma classe de idiomas diferente.
Uma linguagem L é circular se, para todas as palavras w
w
Essa classe de idiomas é conhecida? Estou interessado nas linguagens circulares, que também são regulares e, em particular, em:
um nome para eles, se eles já são conhecidos
a decidibilidade do problema, dado um autômato (em particular: um DFA), se o idioma aceito obedece à definição acima
fl.formal-languages
automata-theory
regular-language
vincenzoml
fonte
fonte
Respostas:
Na primeira parte, mostramos um algoritmo exponencial para decidir a circularidade. Na segunda parte, mostramos que esse é um problema coNP. Na terceira parte, mostramos que toda linguagem circular é uma união de linguagens da forma r + (aqui r pode ser o regexp vazio); a união não é necessariamente disjunta. Na quarta parte, exibimos uma linguagem circular que não pode ser escrita como uma soma disjunta ∑ r + i .r+ r ∑ r+Eu
Editar: Incorporadas algumas correções após os comentários de Marcos. Em particular, minhas afirmações anteriores de que a circularidade é coNP-completa ou NP-difícil são corrigidas.
Editar: Corrigida a forma normal de ∑ r ∗ i a ∑ r + i . Exibiu uma linguagem "inerentemente ambígua".∑ r∗Eu ∑ r+Eu
Continuando o comentário de Peter Taylor, veja como decidir (extremamente ineficientemente) se um idioma é circular, considerando seu DFA. Construa um novo DFA cujos estados sejam n- pares dos estados antigos. Este novo DFA executa n cópias do DFA antigo em paralelo.n n
Se o idioma não for circular, haverá uma palavra w, de modo que, se o passarmos pelo DFA repetidamente, começando com o estado inicial s 0 , obteremos os estados s 1 , … , s n de modo que s 1 esteja aceitando apenas um dos outros não está aceitando (se todos estão aceitando, então a sequência s 0 , … , s n deve alternar para que w ∗ esteja sempre no idioma). Em outras palavras, temos um caminho de s 0 , … , s nw s0 s1,…,sn s1 s0 0, … , Sn W∗ - 1 a s 1 ,…, s n em que s 1 está aceitando, mas um dos outros não está aceitando. Por outro lado, se o idioma é circular, isso não pode acontecer.s0 0, … , Sn - 1 s1, … , Sn s1
Portanto, reduzimos o problema a um simples teste de acessibilidade direcionada (basta verificar todos os n- tufos possíveis "ruins" ).n
O problema da circularidade é difícil de coNP. Suponha que recebamos uma instância 3SAT com n variáveis → x e m cláusulas C 1 , ... , C m . Podemos supor que n = m (adicione variáveis fictícias) e que n seja primo (caso contrário, encontre um primo entre n e 2 n usando o teste de primalidade da AKS e adicione variáveis e cláusulas fictícias).n x⃗ m C1, … , Cm n = m n n 2 n
Considere o seguinte idioma: "a entrada não possui a forma → x 1 ⋯ → x n onde → x i é uma atribuição satisfatória para C i ". É fácil construir um O ( n 2 ) DFA para esse idioma. Se o idioma não for circular, haverá uma palavra w no idioma, cujo poder não está no idioma. Como as únicas palavras que não estão no idioma têm comprimento n 2 , w deve ter comprimento 1 ou n . Se for de comprimentox⃗ 1⋯ x⃗ n x⃗ Eu CEu O ( n2) W n2 W 1 n 1 , considere w n vez (ele ainda está no idioma), de modo que w é na linguagem e w n não está no idioma. O fato de que w n não está nos meios de linguagem que w é uma atribuição satisfatória.1 Wn W Wn Wn W
Por outro lado, qualquer atribuição satisfazer traduz em uma palavra comprovando a não circularidade da língua: a atribuição satisfazer w pertence à língua, mas w n não. Portanto, o idioma é circular se a instância 3SAT for insatisfatória.W Wn
Nesta parte, discutimos uma forma normal para linguagens circulares. Considere algumas DFA para uma linguagem circular L . Uma sequência C = C 0 , ... é real se C 0 = s (o estado inicial), todos os outros estados estão aceitando, e C i = C j implica C i + 1 = C j + 1 . Assim, toda sequência real é eventualmente periódica, e há apenas muitas seqüências reais finitas (já que o DFA possui muitos estados finitos).eu C= C0 0, … C0 0= s Ci=Cj Ci+1=Cj+1
Dizemos que uma palavra se comporta de acordo com CC se a palavra leva o DFA de estado c i para o estado c i + 1 , para todo i . O conjunto de todas essas palavras E ( C ) é regular (o argumento é semelhante à primeira parte desta resposta). Note-se que E ( C ) é um subconjunto de L .ci ci+1 i E(C) E(C) L
Dada uma sequência real C , defina C k como a sequência C k ( t ) = C ( k t ) . A sequência C k também é verdadeiro. Desde há apenas finitamente muitos diferentes seqüências C k , a linguagem D ( C ) , que é a união de todos E ( C k ) também é regular.C Ck Ck(t)=C(kt) Ck Ck D(C) E(Ck)
Afirmamos que D ( C ) tem a propriedade de que se x , y ∈ D ( C ) então x y ∈ D ( C ) . De fato, suponha que x ∈ C k e y ∈ C l . Então x y ∈ C k + l . Assim, D ( C ) = D ( C ) + pode ser escrito na forma rD(C) x,y∈D(C) xy∈D(C) x∈Ck y∈Cl xy∈Ck+l D(C)=D(C)+ + para alguma expressão regular r .r+ r
Cada palavra w nos corresponde língua para alguma seqüência verdadeira C , ou seja, não existe uma verdadeira seqüência C que w se comporta de acordo com. Assim G é a união de D ( C ) sobre toda a sequência verdadeira C . Portanto, toda linguagem circular tem uma representação da forma ∑ r + i . Por outro lado, todo idioma é circular (trivialmente).w C C w L D(C) C ∑r+i
Considere a linguagem circular L de todas as palavras sobre a , b que contenham um número par ou a 's ou um número par de b ' s (ou ambos). Mostramos que não pode ser escrito como uma soma disjunta ∑ r + i ; por "disjunção" queremos dizer que r + i ∩ r + j = ∅ .L a,b a b ∑r+i r+i∩r+j=∅
Let NiNi be the size of the some DFA for r+ir+i , and N>maxNiN>maxNi be some odd integer. Consider x=aNbN!x=aNbN! . Since x∈Lx∈L , x∈r+ix∈r+i for some ii . By the pumping lemma, we can pump a prefix of xx of length at most NN . Thus r+ir+i generates z=aN!bN!z=aN!bN! . Similarly, y=aN!bNy=aN!bN is generated by some r+jr+j , which also generates zz . Note that i≠ji≠j since xy∉Lxy∉L . Thus the representation cannot be disjoint.
fonte
Here are some papers that discuss these languages:
Thierry Cachat, The power of one-letter rational languages, DLT 2001, Springer LNCS #2295 (2002), 145-154.
S. Hovath, P. Leupold, and G. Lischke, Roots and powers of regular languages, DLT 2002, Springer LNCS #2450 (2003), 220-230.
H. Bordihn, Context-freeness of the power of context-free languages is undecidable, TCS 314 (2004), 445-449.
fonte
@Dave Clarke, L = a*|b* would be circular, but L* would be (a|b)*.
In terms of decidability, a language LL is circular if there is an L′L′ such that LL is the closure under + of L′L′ or if it is a finite union of circular languages.
(I'm dying to redefine "circular" replacing your >> with ≥≥ . It simplifies things a lot. We can then characterise the circular languages as those for which there exists a NDFA whose starting state has only epsilon-transitions to accepting states and has an epsilon-transition to each accepting state).
fonte
Edit: A complete (simplified) PSPACE-completeness proof appears below.
Two updates. First, the normal form described in my other answer appears already in a paper by Calbrix and Nivat titled Prefix and period languages of rational ωω -langauges, unfortunately not available online.
Second, deciding whether a language is circular given its DFA is PSPACE-complete.
Circularity in PSPACE. Since NPSPACE=PSPACE by Savitch's theorem, it is enough to give an NPSPACE algorithm for non-circularity. Let A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F) be a DFA with |Q|=n|Q|=n states. The fact that the syntactic monoid of L(A)L(A) has size at most nnnn implies that if L(A)L(A) is not circular then there is a word ww of length at most nnnn such that w∈L(A)w∈L(A) but wk∉L(A)wk∉L(A) for some k≤nk≤n . The algorithm guesses ww and computes δw(q)=δ(q,w)δw(q)=δ(q,w) for all q∈Q, using O(nlogn) space (used to count up to nn). It then verifies that δw(q0)∈F but δ(k)w∉F for some k≤n.
Circularity is PSPACE-hard. Kozen showed in his classic 1977 paper Lower bounds for natural proof systems that it is PSPACE-hard to decide, given a list of DFAs, whether the intersection of the languages accepted by them is empty. We reduce this problem to circularity. Given binary DFAs A1,…,An, we find a prime p∈[n,2n] and construct a ternary DFA A accepting the language L(A)=¯{2w12w2⋯2wp:wi∈L(A1+(imodn))}.
fonte
Every s∈L of length p>0 can be written as xyiz where x=z=ϵ , y=w≠ϵ . It's obvious that |xy|≤p and |y|=|w|>0. It follows that the language is regular for non-empty inputs, by the pumping lemma.
For w=ϵ , the definition holds, since a NDFA that accepts the empty string will also accept any number of empty strings.
The union of the above languages is the language L and since regular languages are closed under union, it follows that every circular language is regular.
By Rice's theorem, CIRCULARITY/TM is undecidable. The proof is similar to regularity.
fonte