DFA para aceitar todas as cadeias binárias de poder de forma de

9

Podemos formar o DFA aceitando números binários divisíveis por .n

Por exemplo, o DFA que aceita números binários divisíveis por 2 pode ser formado da seguinte maneira:

insira a descrição da imagem aqui

Da mesma forma, o DFA que aceita números binários divisíveis por 3 pode ser formado da seguinte maneira: insira a descrição da imagem aqui

Podemos seguir um procedimento bem definido para formar esses tipos de DFAs. No entanto, pode haver algum procedimento bem definido ou, melhor dizendo, lógica para formar DFAs que aceitam números do formato ?nk

Por exemplo, consideremos o DFA aceitando todos os números do formulário . Esta linguagem será { 1 , 10 , 100 , 1000 , . . . } , portanto, tenha a expressão regular 10 . Podemos formar o DFA da seguinte maneira: 2k{1,10,100,1000,...}10insira a descrição da imagem aqui

Tentei formar DFA para e similares? Mas não foi capaz de fazê-lo. Ou é apenas o seu padrão de 2 n equivalentes binários que estava possibilitando a criação do DFA e não podemos formar o DFA aceitando todos os números binários do formato n k para n específico ?3k2nnkn

Maha
fonte
Eu acho que você tem a resposta aqui
3
@Raphael, não, isso é para múltiplos de ; trata-se de potências de n . nn
DW
fyi pode haver outras "próximos" funções que são calculável por AFDs tais como divisibilidade de poderes etc., por exemplo, a função de Collatz (que envolve poderes de 3) pode ser calculado por um transdutor de estados finitos etc
vzn

Respostas:

10

Aqui está uma prova rápida e suja, usando o Lemma de Bombeamento, de que a linguagem composta por 3 n em binário, não é regular (nota: é regular se representada no ternário, portanto, a representação é importante).L3n

Usarei a notação do artigo da Wikipedia sobre Pumping Lemma . Suponha por contradição que seja regular. Vamos w L ser qualquer cadeia com | w | p (comprimento de bombeamento). Ao bombear o lema, escreva w = x y z com | y | 1 , | x y | p e para todos os i 0 x y i z L . Vou escrever x , yLwL|w|pw=xyz|y|1,|xy|pi0 xyizLxy, e também para valores numéricos das partes correspondentes, e | x | , | y | , | z | por seus comprimentos em w . Numericamente temos w = 3 k 0 para alguns k 0N . Ao mesmo tempo, temos numericamente w = z + 2 | z | y + 2 | z | + | y | x . Assim, temosz|x|,|y|,|z|ww=3k0k0Nw=z+2|z|y+2|z|+|y|x

z+2|z|y+2|z|+|y|x=3k0

Agora, vamos bombear para obter tudo o que 0wi0

z+2|z|y(j=0i1(2|y|)j)+2|z|+i|y|x=3ki,

onde . Simplificando chegamos a i 1k0<k1<k2<i1

z+2|z|y(2i|y|1)/(2|y|1)+2|z|+i|y|x=3ki.

Seja . Então nós temosC=z2|z|y/(2|y|1)

3ki=2|z|+i|y|y/(2|y|1)+2|z|+i|y|x+C.

Agora observe que

3ki3ki1=(2|y|1)(3ki1C).

Portanto, temos Note que | 2 | y | - 3 k i - k i - 1 | 1 . Assim, por um lado, o valor absoluto do lado direito cresce pelo menos em 3 kC(2|y|1)=3ki1(2|y|3kiki1).|2|y|3kiki1|1 , que vai para o infinito comi. Por outro lado,C(2 | y | -1)é independente deie é uma constante. Isso dá uma contradição.3ki1iC(2|y|1)i

Denis Pankratov
fonte
Você poderia elaborar um pouco sobre o porquê é verdadeiro? Estou perguntando, porque essa desigualdade sozinha poderia ser usada para chegar a uma contradição: | 2 | y | - 3 k i - k i - 1 | 1 , multiplicando ambos os lados por 3 k i - 1 , obtemos | 3 k i - 1|2|y|3kiki1|1|2|y|3kiki1|13ki1 , portanto, | C ( 2 | y | - 1 ) | 3 k i - 1 , o que é uma contradição (pelo motivo fornecido na sua prova). |3ki12|y|3ki|3ki1|C(2|y|1)|3ki1
Anton Trunov 23/01
11
Desde , temos 2 | y | é par e 3 k i - k i - 1 é ímpar. Sua diferença é ímpar, portanto, pelo menos 1 em valor absoluto. |y|12|y|3kiki1
Denis Pankratov
10

Uma maneira de ver que isso não é possível (por exemplo) para a linguagem de potências 3 na expansão binária é considerar a função geradoraL3

,k=0nkzk

onde é o número de palavras de comprimento k em L . Sabe-se que esta função é racional, isto é, um quociente de polinômios p ( x ) / q ( x ) , para qualquer L regular . Em particular, os números n k satisfazem uma recorrência linear n k + p + 1 = a 0 n k + + a p n k + p para alguns p NnkkLp(x)/q(x)Lnknk+p+1=a0nk++apnk+ppNe .a1,,apZ

Por outro lado, como é um número irracional em ( 1 , 2 ) , obtemos que n k{ 0 , 1 } para todo k , e a sequência ( n k ) k 1 não é periódica . Isso contradiz, pois, após no máximo 2 p etapas, os valores de n k , , n k + plog2(3)(1,2)nk{0,1}k(nk)k12pnk,,nk+p precisa repetir, e a recorrência levaria a um comportamento periódico.

Klaus Draeger
fonte
8

Uma resposta completa para sua pergunta é fornecida por um resultado (difícil) de Cobham [2].

Dada uma base de numeração , é dito que um conjunto de números naturais é b- reconhecível se as representações na base b de seus elementos formarem uma linguagem regular no alfabeto { 0 , 1 , , b - 1 } . Assim, como você observou, o conjunto de potências de 2 é 2 - reconhecível, pois é representado pelo conjunto regular 10 no alfabeto { 0 , 1 } . Da mesma forma, o conjunto de potências de 4 é 2bbb{0,1,,b1}2210{0,1}42-reconhecível - corresponde ao conjunto regular - e o conjunto de potências de 3 é 3 -recognizável - corresponde ao conjunto regular 10 sobre o alfabeto { 0 , 1 , 2 } .1(00)3310{0,1,2}

Diz- se que um conjunto de números naturais é basicamente periódico se for uma união finita de progressões aritméticas.

Diz-se que duas bases são dependentes multiplicativamente se houver um r > 1 de modo que b e c sejam potências de r : por exemplo, 8 e 32 são dependentes multiplicativamente desde 8 = 2 3 e 8 = 2 5 .b,c>1r>1bcr8328=238=25

Teorema [Cobham] Let e c duas bases multiplicativamente independentes. Se um conjunto é b -reconhecível e c -reconhecível, então é basicamente periódico.bcbc

S332S

O teorema de Cobham levou a muitas generalizações e desenvolvimentos surpreendentes. Eu recomendo a pesquisa [1] se você estiver interessado.

p

[2] A. Cobham, Sequências uniformes de etiquetas, Matemática. Teoria dos Sistemas 6 (1972), 164-192.

J.-E. Pin
fonte
Could you fix the references, please? Now they are both numbered [1] & [1].
Anton Trunov