Quais são os conjuntos possíveis de tamanhos de palavras em um idioma comum?

15

Dado um idioma , defina o conjunto de comprimentos de como o conjunto de comprimentos de palavras em : LLL

LS(L)={|u|uL}

Quais conjuntos de números inteiros podem ser o comprimento de um idioma comum?

Gilles 'SO- parar de ser mau'
fonte

Respostas:

14

Primeiro, uma observação que não é crucial, mas conveniente: o conjunto S de conjuntos de números inteiros LS(L) para alguma linguagem regular L em um alfabeto não vazio A não depende da escolha do alfabeto. Para ver isso, considere um autômato finito que reconheça L ; os comprimentos das palavras que estão em L são os comprimentos dos caminhos no autômato vistos como um gráfico sem rótulo do estado inicial para qualquer estado de aceitação. Em particular, você pode rotular novamente cada seta para a e obter um idioma regular com o mesmo comprimento definido sobre o alfabeto {a} . Por outro lado, seL é uma linguagem comum sobre um alfabeto de um elemento, pode ser injetada trivialmente em um alfabeto maior e o resultado ainda é uma linguagem comum.

Portanto, estamos procurando os possíveis conjuntos de comprimento para palavras sobre um alfabeto singleton. Em um alfabeto singleton, o idioma é o comprimento definido em unário: LS(L)={nNanL} . Tais idiomas são chamados idiomas unários.

Deixe L ser uma linguagem regular, e considerar um autômato finito determinístico (DFA) que reconhece L . O conjunto de comprimentos de palavras de L é o conjunto de comprimentos de caminhos no DFA, vistos como um gráfico direcionado que começa no estado inicial e termina em um dos estados de aceitação. Um DFA em um alfabeto de um elemento é bastante manso (os NFAs seriam mais selvagens): é uma lista finita ou circular. Se a lista for finita, numere os estados de 0 a h após a ordem da lista; se for circular, numere os estados de 0 a h após o início da lista h a h+r ao longo do loop.

autômatos em forma de lista

Seja F o conjunto de índices de estados de aceitação até h , e G seja o conjunto de índices de estados de aceitação de h a h+r . Então

LS(L)=F{kr+xxG,kN}

Por outro lado, deixe h e r ser dois inteiros e F e G ser dois conjuntos finitos de números inteiros tais que xF,xh e xG,hxh+r . Então o conjunto LF,G,r={akr+xxG,kN}é um idioma comum: é o idioma reconhecido pelo DFA descrito acima. Uma expressão regular que descreve esse idioma éaFaG(ar) .

Para resumir em inglês, os conjuntos de idiomas regulares são os conjuntos de números inteiros periódicos¹ acima de um determinado valor .

¹ Para manter uma noção bem estabelecida , periódica significa a função característica do conjunto (que é uma função N{false,true} que elevamos para uma função Z{false,true} ) é periódico. Periódico acima de um determinado valor significa que a função restrita a [h,+[ pode ser prolongado para uma função periódica.

Gilles 'SO- parar de ser mau'
fonte
Sua observação sobre a irrelevância do alfabeto sugere que o teorema de Parikh pode ser aplicado. Especificamente, você mostra que LS (L) = LS (L ') onde em L' todas as letras são recolhidas em um único alfabeto. Mas LS (L ') é o mapeamento parikh da linguagem L, que é conhecido por ser semi-linear para qualquer linguagem regular.
Suresh
Boa abordagem! 1) Acho que o primeiro parágrafo pode ser substituído pela observação de que linguagens regulares são fechadas contra homomorfismos de cadeias. 2) Para maior clareza, você deve considerar atribuir a segunda parte de como { h + k r + ( x - h ) } , módulo off-by-one-errors. 3) O que é um conjunto "periódico" de números inteiros? LS(L){h+kr+(xh)}
Raphael
1
@Suresh, Raphael (1): Prefiro declarar a prova de maneira elementar, nem os homomorfismos nem os mapeamentos de Parikh foram mencionados na minha classe CS 102.
Gilles 'SO- stop being evil'
@Raphael (2) Onde você começa a indexação não importa, eu poderia remover a condição h G , pois F pode absorver quantos elementos pequenos quisermos. (3) Um conjunto periódico acima de um determinado valor pode ser colocado no formulário exibido acima. GhGF
Gilles 'SO- stop being evil'
5

Qualquer subconjunto finito pode ser o comprimento-set de uma linguagem regular L , desde que você pode tomar um alfabeto unário { 0 } e definir L como { 0 1 , ... , 0 n } (isso inclui o idioma vazio e { ε } ).{1,,n}NL{0}L{01,,0n}{ε}

Agora, para os conjuntos infinitos. Vou fazer uma breve análise, embora a resposta final possa não ser suficientemente explícita. Não vou elaborar a menos que você me peça, porque acho que é intuitivo e porque não tenho muito tempo agora.

Seja expressões regulares que geram as linguagens L 1 e L 2 , respectivamente. É (mais ou menos) fácil ver quer1,r2L1L2

  • .LS(L(r1+r2))=LS(L1L2)=LS(L1)LS(L2)
  • . Isso é indicado como L S ( L 1 ) + L S ( LLS(L(r1r2))=LS(L1L2)={1+2:1LS(L1),2LS(L2)} .LS(L1)+LS(L2)
  • LS(L(r1))={0}n1{i=1ni:(1,,n)(LS(L1))n}.

Assim, os possíveis conjuntos de números inteiros que podem ser o comprimento de uma linguagem regular são aqueles que são subconjuntos finitos de ou que podem ser construídos usando subconjuntos finitos S 1 , S 2 de N e usando as fórmulas anteriores um finito número de vezes.NS1,S2N

Aqui, estamos usando que as linguagens regulares são construídas, por definição, aplicando as regras para construir uma expressão regular um número finito de vezes. Observe que podemos começar com qualquer subconjunto finito de , mesmo que nas expressões regulares comecemos com palavras de comprimento 0 e 1 apenas como o caso base. Isso é facilmente justificado pelo fato de que todas as palavras (finitas) são concatenações (finitas) dos símbolos do alfabeto.N

Janoma
fonte
Não vejo resposta final. (Você pretendia terminar sua resposta mais tarde?) Eu esperava uma descrição simples dos conjuntos possíveis e uma conexão com os autômatos.
Gilles 'SO- stop be evil'
A resposta final está aí: "Assim, os possíveis conjuntos de números inteiros ...". Essa é realmente uma descrição simples, embora conectada com expressões regulares, não autômatos.
Janoma
Há uma descrição mais simples que não envolve a tomada de um ponto de correção. Talvez essa pergunta não seja tão elementar quanto eu pensava!
Gilles 'SO- stop be evil'
Não acho que você possa evitar a última regra, já que é o operador em estrela aquele que pode produzir conjuntos infinitos de comprimentos, assim como produz linguagens infinitas.
21712 Janoma
@Gilles Então você quer uma forma fechada do menor ponto fixo da solução indutiva que Janoma fornece?
Raphael
2

De acordo com o lema de bombeamento para idiomas regulares, existe um tal que uma cadeia x de comprimento pelo menos igual a n pode ser escrita da seguinte forma: x = u v w Onde as três condições a seguir são válidas: | você v | < n | v | > 0 u v k w Lnxn

x=uvw
|uv|<n
|v|>0
uvkwL

nmv

{a+bn|nN}S
a,bNSN

EDIT: Um pouco mais de discussão. Certamente todos os conjuntos finitos de números inteiros são conjuntos de comprimento. Além disso, a união de dois conjuntos de comprimento também deve ser um conjunto de comprimento, assim como o complemento de qualquer conjunto de comprimento (daí a interseção e, portanto, a diferença). A razão para isso é que os idiomas regulares são fechados nessas operações. Portanto, a resposta que dou acima é (possivelmente) incompleta; na realidade, qualquer união de tais conjuntos também é o conjunto de comprimento de uma linguagem comum (observe que eu abandonei a necessidade de interseção, complemento, diferença etc.), pois eles são cobertos pelo fato de as linguagens regulares serem fechadas sob essas propriedades, como discutido no EDIT3; acho que apenas a união é realmente necessária, mesmo que os outros estejam certos, o que pode não ser o caso).

bna

EDIT3: À luz do comentário de Janoma, vamos esquecer as propriedades de fechamento dos conjuntos de tamanhos de idiomas que discuto na primeira edição. Como os idiomas regulares têm essas propriedades de fechamento, e como todo idioma regular possui um DFA, segue-se que o lema de bombeamento para idiomas regulares se aplica a todas as uniões, interseções, complementos e diferenças de idiomas regulares, e deixaremos assim ; nem é preciso considerar nada disso, exceto a união, que ainda acho necessário para corrigir meu original (modificado, graças à contribuição de Gilles). Portanto, minha resposta final é a seguinte: o que digo na versão original, mais o fechamento dos conjuntos de tamanhos de idiomas em relação à união de conjuntos.

Patrick87
fonte
1
{a+bna,b,nN}SN
1
L=L(a)Σ={a,b}LNL¯N+
@Gilles Mas o conjunto de todos os números naturais é um comprimento válido, certo? Não estou gerando todos os subconjuntos de números naturais, certo? Concordo que seria problemático. Edit: oh espera, eu vejo o que você está dizendo. Sim, você está certo. Corrigirá quando voltar ao computador.
22812 Patrick87
@Janoma ponto Excelente, terá de considerar como isso pode alterar o conjunto de coisas que eu estou definindo ...
Patrick87