Provar que o conjunto de potências de 2 sobre o alfabeto ternário não é regular.

9

É simples ver que os poderes de 2 sobre o alfabeto {0,1} são regulares porque é uma expressão regular para ele.10

Mas os poderes de 2 representados no ternário parecem não ser regulares. É difícil aplicar classes de lema ou resíduo de bombeamento, pois parece haver muito pouco padrão entre as strings. Como eu resolvo isso?

Em geral, para quais potências de representadas na base , o conjunto é regular?rkr

Tsuyoshi Ito
fonte
1
Uma observação fácil é que, se k e r são potências do mesmo número inteiro, o conjunto é regular. Eu acho que o inverso também vale, mas eu não tenho uma prova.
Tsuyoshi Ito 10/10
1
Eu acho que este é um exercício no livro de Sipser.
Zeyu 10/10
1
Parece dever de casa.
Warren Schudy 26/10/10

Respostas:

12

Aqui está uma solução alternativa (com explicação detalhada) usando o Teorema de Myhill-Nerode. Usarei as bases e para facilitar a leitura, mas a prova generaliza para bases arbitrárias que não são potências do mesmo número inteiro.2 r , k32r,k

(1) Mostre que, dada qualquer string ternária , existe outra string tal que é uma potência de .y x y 2xyxy2

Prova: Dado qualquer (deixando que seja o número que representa), e , existe tais que representa . De fato, isso caracteriza todos os números que pode representar. Portanto, encontrar o mínimo modo que seja uma potência de depende de encontrar o menor número inteiro modo que tenhamos alguma potência de no intervalo . Tomando a base de log , precisamos encontrarn k c { 0 , , 3 k - 1 } y x y 3 k n + c x y y x y 2 k 2 [ 3 k n , 3 k ( n + 1 ) - 1 ] 2 k [ k log 3 + log x , k log 3 +xnkc{0,,3k1}yxy3kn+cxyyxy2k2[3kn,3k(n+1)1]2kde modo que tenhamos um número inteiro no intervalo (soltar o aqui é duvidoso, mas simplifica os cálculos que não dependem dele) . Observe que alterar afeta apenas a parte , para que possamos encontrar um que nos aproxime arbitrariamente de algum número inteiro.- 1 k k log 3 k[klog3+logx,klog3+log(x+1)]1kklog3k

(2) Dado algum e o mínimo correspondente , mostre que existe uma string x 'de modo que o mínimo correspondente tenha que ser maior que . Repetir isso nos dá infinitamente muitas classes de equivalência de strings.y y yxyyy

Resumo da prova: Como , dados um e seus e correspondentes , sempre podemos encontrar alguns que é suficientemente pequeno, de modo que nenhum número inteiro esteja contido em . Observe que estamos implicitamente usando o fato de que nunca pode ser um número inteiro.log2mx=m+logxxykx=2mxlog(2mx+1)log(2mx)[klog3+m+logx,klog3+log(2mx+1)]klog3+logx

Cong Han
fonte
10

Em geral, para quais potências de representadas na base r , o conjunto é regular?kr

Sua pergunta é uma sub-caixa do Teorema de Cobham (Alan Cobham, Sobre a dependência básica de conjuntos de números reconhecíveis por autômatos finitos, Theory of Computing Systems 3 (2): 186-192, 1969, doi: 10.1007 / BF01746527 ):

Seja um conjunto de números inteiros não negativos e m e n sejam inteiros positivos multiplicativamente independentes. Então S é reconhecível por autômatos finitos na notação m- ar e n- ar se, e somente se, em última análise, for periódicaSmnSmn

Aqui, por multiplicativamente independente, um significa que não existe e q diferentes de zero, de modo que m p = n q . Cobham cita Büchi para o seu caso específico de potências de algum k na base r , que é reconhecível apenas se k e r forem multiplicativamente dependentes .pqmp=nqkrkr

Se você estiver interessado neste resultado, há uma pesquisa bastante interessante feita por Véronique Bruyère, Georges Hansel, Christian Michaux e Roger Villemaire ( conjuntos de números lógicos e reconhecíveis, Boletim da Sociedade Belga de Matemática 1 (2), 1994, PDF ), que também mostra o relacionamento com a aritmética Presburger.p

Sylvain
fonte
5

O lema de bombeamento implica que existe uma sequência como para alguns b , c , d , de modo que cada x n seja uma potência de k . Logo, log k ( x n ) = d n log k ( r ) + c o n s t +xn=c+b(rdn1)/(rd1)b,c,dxnk é sempre um número inteiro, então log k ( r ) é racional.logk(xn)=dnlogk(r)+const+o(1)logk(r)

Aqui está uma explicação dessa fórmula para . O lema de bombeamento fornece as cadeias u , v , w , de modo que cada cadeia x n = u v n w é uma potência de k . Interpretando essas seqüências de caracteres como números e escrevendo d e e para os comprimentos de v e w , respectivamente, x n = u r d n + e + v r d ( n - 1 )xnu,v,wxn=uvnwkdevwé uma potência ded. Então x n - x n - 1 =(u r d -u+v) r d ( n - 1 ) + e . Escrevendob=(u r d -uxn=urdn+e+vrd(n1)+e+vrd(n2)+e++vre+wdxnxn1=(urdu+v)rd(n1)+e e c = x 0 - b temos x n = c + b ( r d n - 1 ) / ( r d - 1 ) .b=(urdu+v)rec=x0bxn=c+b(rdn1)/(rd1)

Colin McQuillan
fonte
(1) Eu acho que você precisa de um termo como para lidar com a parte do prefixo do bombeamento. (2) Não consigo entender por que d n log k r + O ( 1 ) sendo sempre um número inteiro implica que log k r é racional. Mais precisamente, como está escrito, é falso porque você pode encontrar 0 ε n < 1 de modo que d n log k r + ε n seja um número inteiro. Eu acho que você precisa de algo mais específico do que a notação O. erdndnlogkr+O(1)logkr0εn<1dnlogkr+εn
Tsuyoshi Ito 10/10
Se você escrever o termo geral como digamos, então a diferença de pode-se ver dois termos com a forma b r d n . xrdn+e+yrd(n1)+e+yrd(n2)+e++yre+zbrdn
Colin McQuillan
É constante + o (1), que não é o mesmo que O (1).
Domotorp 10/10/10
@domotorp: Eu acho que o item (2) no meu comentário anterior estava se referindo a uma parte que foi editada na janela de 5 minutos, mas não tenho certeza. Talvez eu possa interpretar mal a resposta.
Tsuyoshi Ito 10/10
@ Colin: Eu não tenho certeza do que você está reivindicando pelo seu último comentário. Parece-me que seu argumento mostra que um termo como é necessário. erdn
Tsuyoshi Ito 10/10
4

Seja L o conjunto de potências de 2 codificadas na base 3. A codificação de 4n na base 3 termina com 1, enquanto a codificação de 24n na base 3 termina com 2. Portanto, L=LΣ1 é a codificação de todas as potências de 4.

A codificação de um número inteiro m>0 na base 3 leva log3(m+1) dígitos. Como nem 4n nem 4n+1 são potências de 3 para n>0 (uma vez que nenhuma é divisível por 3), a codificação de 4n leva log34n+1 dígitos.

Seja N={log34n:n0} (esta é uma sequência de Beatty ). Suponha que L seja regular. Então seria L . Isso implica que o conjunto de comprimentos de palavras em L é eventualmente periódico e, portanto, N é periódico. Em particular, N teria densidade racional assintótica. No entanto, N tem densidade assintótica 1/log34 , o que é irracional.

Yuval Filmus
fonte