Contando palavras aceitas por uma gramática regular

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.

Para um DFA, no qual o estado inicial é o estado $0$ , o número de palavras de comprimento $k$ que terminam no estado $i$ é $A^k[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.

Deixe ser um (não-determinístico) automação finito com começando estado Q 1 , Q F ⊆ Q e δ ⊆ Q × Σ × Q .$A = (Q = \{q_1, \dots, q_n\}, \Sigma, \delta, Q_F)$$q_1$$Q_F \subseteq Q$$\delta \subseteq Q\times\Sigma\times 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 } | .$Q_i(z)$$q_i$$n$$[z^n]Q_i = |\{w \mid |w| = n \wedge w \text{ accepted from } q_i\}|$

Claramente:

$Q_i(z) = \left[ q_i \in Q_F \right] + \sum\limits_{(q_i, a, q_j) \in \delta} x \cdot Q_j(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.$Q_1$$[z^n]Q_1$

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 .$\varepsilon$$x$$a \in \Sigma$$w \in \Sigma^k$$x$$x^k$

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.

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.$\#\mathsf{NC}^1$