Contando palavras aceitas por uma gramática regular

26

Dado um idioma comum (NFA, DFA, gramática ou regex), como pode ser contado o número de palavras aceitantes em um determinado idioma? Tanto "com exatamente n letras" quanto "com no máximo n letras" são de interesse.

Margareta Ackerman tem dois trabalhos sobre o assunto relacionado de enumerar palavras aceitas por uma NFA, mas não pude modificá-las para contar com eficiência.

Parece que a natureza restrita das linguagens regulares deve facilitar a contagem delas - quase espero uma fórmula mais que um algoritmo Infelizmente, minhas pesquisas até agora não revelaram nada, então devo estar usando os termos errados.

Charles
fonte
Presumo que você queira dizer "número de palavras aceitantes de tamanho ", ou algo assim? mais, o que é o número de aceitar palavras de Σ *nΣ
Suresh Venkat

Respostas:

37

Para um DFA, no qual o estado inicial é o estado 0 , o número de palavras de comprimento k que terminam no estado i é Ak[0,i] , onde A é a matriz de transferência do DFA (uma matriz na qual o número na linha i coluna j é o número de símbolos de entrada diferentes que causam uma transição do estado i para o estado j ). Assim, você pode contar aceitando palavras de comprimento exatamente k facilmente, mesmo quando k é moderadamente grande, apenas calculando uma potência da matriz e adicionando as entradas correspondentes aos estados de aceitação.

O mesmo funciona para aceitar palavras de comprimento no máximo , com uma matriz ligeiramente diferente. Adicione uma linha e coluna extras da matriz, com uma na célula que esteja na linha e na coluna, uma na nova linha e na coluna do estado inicial e um zero em todas as outras células. O efeito dessa alteração na matriz é adicionar mais um caminho ao estado inicial em cada potência.k

Isso não funciona para os NFAs. Suspeito que a melhor coisa a fazer é converter para um DFA e aplicar o algoritmo de alimentação da matriz.

David Eppstein
fonte
2
A resposta perfeita: óbvia apenas depois de ler.
Charles
1
Essa abordagem possui um tempo de execução exponencial do pior caso, se você tiver uma entrada diferente de um DFA. Isso não é um problema para você, @Charles? Você parece incluir expressões regulares, NFA e gramática em suas perguntas e também pede uma maneira eficiente.
Raphael
17

Deixe ser um (não-determinístico) automação finito com começando estado Q 1 , Q FQ e δ Q × Σ × Q .A=(Q={q1,,qn},Σ,δ,QF)q1QFQδQ×Σ×Q

Let a função de geração de todas as palavras que podem ser aceites, a partir de q i , que é o n ° coeficiente de expansão a sua série [ z n ] Q i = | { w | w | = N w  aceites a partir de  q i } | .Qi(z)qin[zn]Qi=|{w|w|=nw accepted from qi}|

Claramente:

Qi(z)=[qiQF]+(qi,a,qj)δxQj(z)

Resolva o sistema de equações (linear) resultante para (usando o Mathematica ou uma ferramenta similar). Então, [ z n ] Q 1 é a quantidade desejada.Q1[zn]Q1

Isso remonta a uma técnica introduzida pelas gramáticas por Chomsky e Schützenberger (1963); transfere facilmente para autômatos finitos.

Editar: se você quiser contabilizar as transições , deixe de fora o fator x na soma da transição correspondente. Similarmente, se você tiver "comprimido" bordas, ou seja, em vez de símbolo a Σ uma palavra w Σ k em uma transição, substitua x com x k .εxaΣwΣkxxk

Rafael
fonte
Agradeço a nota histórica!
Charles
1
Na verdade, esse é um método que funciona muito bem (e é simples, quando você o obtém) em muitas circunstâncias. Por exemplo, você pode executar CFGs exatamente da mesma maneira.
Raphael
1
Entendo, eu entendi errado. Nesse caso, se você quiser ler sobre isso, recomendo Kuich (1970), que achei mais acessível do que o trabalho de C&S. Ele também cobre isso em um livro dele, do qual não me lembro.
Raphael
1
Você está dizendo que pode contar palavras de tamanho em um idioma regular no tempo polinomial e sem construir o DFA? Perguntado sobre a complexidade disso no MO: mathoverflow.net/questions/162186/…n
joro
1
@joro No caso de gramáticas inequívocas, acho que isso é verdade, sim.
Raphael
7

Acho que esse é um problema difícil de contar, veja este artigo: Contar o tamanho de seqüências regulares de um determinado comprimento é # P-completo: S. Kannan, Z. Sweedyk e SR Mahaney. Contagem e geração aleatória de strings em idiomas regulares. No Simpósio ACM-SIAM sobre algoritmos discretos (SODA), páginas 551–557, 1995.

Miklós István
fonte
1
O post acima pressupõe que o comprimento especificado seja unário. Se, em vez disso, o comprimento estiver em binário, o problema é difícil para o PSPACE. Digo isso com base na prova de que decidir a equivalência de duas expressões regulares é difícil para o PSPACE. Nessa redução, um reg-ex foi construído para aceitar todas as cadeias e o outro para aceitar todas as cadeias que não são válidas, rejeitando os históricos de computação da máquina PSPACE M na entrada w. Usar essa segunda expressão regular e o comprimento de um histórico de computação de M em w como entradas para o problema em questão torna esse outro problema também difícil para o PSPACE.
Mikhail Rudoy
3

O seguinte: CMTV , considera a classe de complexidade que é (essencialmente, mas em um cenário um pouco mais geral) a classe de funções que conta o número de cálculos aceitos de um autômato finito não determinístico em uma palavra de entrada de um determinado comprimento. Muitos resultados agora são conhecidos sobre essa classe de complexidade, incluindo a contenção no espaço de log determinístico como consequência da CDL . Observe que o autômato está fixo nessa configuração e a palavra de entrada é a única entrada.#NC1

SamiD
fonte