Provando um idioma (ir) regular (métodos padrão falharam)

Atualmente, estou tentando provar um idioma regularmente (para diversão pessoal). O idioma é:

O idioma que contém todos os números no ternário que possuem paridade de bits quando codificados em binário.

Atualmente, tentei algumas abordagens diferentes que não me levaram a nenhum sucesso. Tentei usar o lema de bombeamento (não consegui encontrar nada para bombear), Myhill-Nerode (semelhante) e até contei o número de strings de cada comprimento para o qual a afirmação é verdadeira (minha intuição é que ele verifique com um argumento probabilístico).

Existem outras abordagens que possam ajudar aqui ou existem intuições que podem ser úteis? Neste ponto, meu melhor palpite é que o idioma não é regular, mas não me parece capaz de apresentar uma explicação.

formal-languages regular-languages arithmetic James
fonte

Tem certeza de que é um idioma não regular? Considere o idioma em

{0, 1}^{*}

$\{0,1\}^*$ de modo que as cordas tenham um número par de unidades. Esta é uma linguagem comum. Agora aplique o homomorfismo nesse idioma para convertê-lo em um idioma contendo todas as seqüências ternárias. O homomorfismo inverso define um esquema de codificação. Linguagens regulares são fechadas sob homomorfismo e homomorfismo inverso.

Dib

@ Dib Não acho que essa seja uma abordagem válida, simplesmente porque não acredito que exista tal homomorfismo. Para expandir, como eu o entendo, o homomorfismo deve ser uma função das letras do alfabeto para as strings, então 1, 0, 1101 deve mapear para A, B, AABA, onde A e B são strings no ternário. 1 mapeia para 1 no ternário e 0 mapeia para 0 no ternário, mas 1101 mapeia para 111 e não 1101 no ternário.

James

Devo acrescentar que tenho quase certeza de que esse idioma é irregular. Isso ocorre porque cerca de 50% dos números do tipo 10 * (ou seja, potências de 3) na base 3 têm paridade uniforme, como poderíamos esperar razoavelmente (empírico, verifiquei até

3^{20000}

$3^{20000}$ ) Isso significa que alguém poderia razoavelmente esperar bombear algo dessa forma, bombeando algo da forma

3^{n}

$3^n$ para receber algo como

3^{n + m}

$3^{n+m}$ . Isso não estaria no idioma com probabilidade 0.5. O problema é que não posso provar exatamente isso - acabaria com um argumento probabilístico.

James

Respostas:

Isso pode ser comprovado, mas você precisa de algumas ferramentas não triviais para fazer isso.

Comece com o conjunto S = {0,3,5,6, ...} de números inteiros não negativos com um número par de 1s na expansão da base 2.

É sabido que este conjunto é "2-automático"; isto é, existe um autômato finito que aceita exatamente as expansões da base 2 dos elementos de S. Além disso, é sabido que esse conjunto não é, no final das contas, periódico (ou seja, não é verdade que exista um período P tal que depois de algum ponto C, se x> = C está em S, então também é x + P). (Se assim fosse, a palavra associada 01101001 de Thue-Morse ... seria finalmente periódica, mas é sabido no trabalho de Thue em 1912 que não contém nenhum bloco repetido três vezes consecutivas.)

Em seguida, suponha que S seja realmente "3-automático"; isto é, existe um autômato que aceita exatamente as expansões da base 3 dos elementos de S. Em seguida, por um teorema clássico de Cobham (Math. Systems. Teoria 3 (1969) 186-192, isso implicaria que S é basicamente periódico. já vimos que não é.

Você pode encontrar muito mais sobre essas idéias no meu livro com Allouche, "Automatic Sequences". Atenção, porém, nossa prova de Cobham é um pouco falha, e uma versão corrigida pelo Rigo pode ser encontrada online aqui: http://arxiv.org/abs/0907.0624 .

Jeffrey Shallit
fonte

Muito obrigado. Imaginei que precisaria de algum tipo de ferramenta não trivial, mas ainda não tenho a educação necessária para descobrir qual!

James

@ Jeffrey: Bom uso do Cobham's; por curiosidade, você acredita que alguma prova exigirá - ou a incorporará de alguma forma?

Michaël