Os idiomas regulares estão fechados além disso?

Especificamente o que quero dizer com adição é, definimos para ser o alfabeto . Línguas dadas regulares e sob algum alfabeto , olhada . $\Sigma_i$ $\{0, 1, 2, ..., i\}$ $A$ $B$ $\Sigma_i$ $A\times B$

Para cada par ordenado , definir a "soma" deste par ordenado como , onde e são números na base de i. Os zeros à esquerda são ignorados; portanto, está na frente de cada sequência de caracteres aceita. Isto implica é definido como 0. $(a, b) \in A\times B$ $a+b$ $a$ $b$ $0^*$ $\epsilon$

O idioma é o conjunto de cadeias que representam todas essas somas possíveis. $A+B$

Até agora, eu sei:

Isso é verdade em unário ( ). $\Sigma_1$
Isso vale para qualquer linguagem regular finita e , porque qualquer linguagem finita é regular e é finita. $A$ $B$ $A+B$
A linguagem = s s é um múltiplo de n na base b em é regular para qualquer . Isto significa que qualquer idiomas de forma a , também podem ser adicionados, como , o qual também é regular. No entanto, existem idiomas como = s s começa e termina com 1} que não se encaixa nesse critério, portanto não descreve todos os idiomas comuns. $C_n$ $\{$ $|$ $\}$ $\Sigma_b$ $b >= 1$ $C_n$ $C_i+C_j=C_{i + j}$ $D$ $\{$ $|$

automata-theory Phylliida
fonte

Não é verdade que, se A é regular na base 2, também é regular na base 3, considerar, por exemplo, as potências de 2.

domotorp

Entendo, você está certo. Eu editei a pergunta de acordo. Eu estava tentando provar isso, e parecia verdade, e então eu entendi mal o que era um homomorfismo e presumi que era verdade. Mas não é, desculpe por isso. Se um idioma é regular na base b ^ a para alguns a> 1, também é regular em qualquer outra base b ^ (ac) para qualquer 1 <= c <a no entanto. (por exemplo, se um idioma é regular na base 8, também é regular na base 4 e 2, simplesmente simulando o dfa da base 8).

Phylliida #

"Isso implica que defined é definido como 0". Eu não entendo o que isso significa. Se 0 e ϵ forem iguais, todos os 0 podem ser removidos e a interpretação do número não funcionará mais.

babou

A questão é simplesmente que, se uma string vazia ϵ estiver em um par ordenado, ela adicionará 0 à outra string. Também para qualquer sequência fornecida que possua 0s à esquerda, eles podem ser removidos. O que isso significa é que 000101 é o mesmo que 101, por exemplo. Isso é o que eu quis dizer, se a ϵ aparece em uma string por si só , que é equivalente em valor em relação a uma soma como 0, 00 ou 000 por si mesmos . Se essas strings estiverem dentro de outra string, todas as apostas serão desativadas, e essa substituição não será mais válida.

Phylliida

Respostas:

Sim, eles estão.

$\Sigma_i^3$ $A'$ $A$ $B'$ $B$ $C$ $A'$ $B'$ $A$ $B$ $C$ usa o fato de que você pode fazer acréscimos digitalizando da direita para a esquerda, mantendo apenas um dígito de carry como estado.

$A'\cap B'\cap C$ $A$ $B$

David Eppstein
fonte

Isso é realmente incrível. Eu não sabia que você poderia usar essas pilhas dessa maneira. Obrigado!

Phylliida

É certo que isso é um pouco duvidoso porque, neste caso, contém apenas somas de cadeias do mesmo tamanho, no entanto, porque podemos "simular" somas de cadeias de tamanhos diferentes adicionando zeros à esquerda e é simples modificar um dfa em outro dfa que reconhece 0 * na frente de todas as strings que aceitam (uma vez que você constrói o dfa somatório para reconhecer C com homomorfismo).

Phylliida

Suponho que a maior chave é que A e B precisam ser "tecnicamente modificados" da mesma maneira que sejam 0 * A e 0 * B, e uma vez que fazemos isso, é suficiente, para cada par de aeb encontrar o soma de 0 * a + 0 * b st, ambos os valores têm 0s iniciais suficientes para corresponder aos tamanhos e, em seguida, o resultado pode ser retirado de 0s conforme necessário, pois C é modificado da mesma maneira. Isso estava implícito ou há uma maneira mais simples de ver o que estou perdendo?

Phylliida

Sim, existem alguns aspectos técnicos que envolvem preenchimento, mas eles realmente não mudam as idéias básicas, então eu as omiti.

David Eppstein

Legal, isso faz sentido.

Phylliida

$A$ $B$ $M_A$ $M_B$ $a$ $b$ $M_A$ $M_B$ $M_A$ $M_B$

domotorp
fonte