O número de diferentes idiomas regulares

14

Dado um alfabeto Σ={uma,b} , quantas linguagens regulares diferentes existem que podem ser aceitas por um autômato finito não-determinístico do estado ?n

Como exemplo, vamos considerar . Temos então configurações de transição diferentes e configurações diferentes de estado inicial e final, portanto, temos um limite superior de idiomas diferentes. No entanto, muitos deles serão equivalentes e, uma vez que o teste é PSPACE-Complete, provavelmente não é possível testar cada configuração. Existem outros meios ou argumentos combinatórios que vinculam o número de idiomas diferentes aceitos por um determinado recurso?2 18 2 3 2 24n=321823224

john_leo
fonte
Existem apenas 3 configurações diferentes de estado inicial, não 23 .
8304 FrankW
4
Idéia rápida: as linguagens regulares são caracterizadas por finitas classes de equivalência, cf. Myhill-Nerode. Quantos conjuntos diferentes de classes de equivalência um autômato n state suporta?
Raphael
5
Pode ser útil pesquisar no artigo "No número de idiomas distintos aceitos por autômatos finitos com n estados", de Domaratzki, Kisman e Shallit.
Hendrik Jan
1
aqui está o URL do
citeseer
1
encontrou quase a mesma pergunta em tcs.se: qual é o número de idiomas aceitos por um DFA de tamanho n?
vzn

Respostas:

11

Este é um resumo do artigo Sobre o número de idiomas distintos aceitos pelos autômatos finitos com n Estados . O documento fornece limites relativamente fáceis, porém distantes, reduzidos e superiores do número de idiomas distintos aceitos pelos NFAs. A discussão deles sobre o número de DFAs distintos é muito esclarecedora, por isso também incluirei essa parte.

O artigo começa com um assintótico bastante rigoroso para o número de idiomas distintos aceitos por um DFA com estados em um alfabeto unário. Isso é feito observando sob quais condições um determinado DFA de estado n unário é mínimo. Nesses casos, a descrição do autômato pode ser mapeada (bijetivamente) para uma palavra primitiva , e a enumeração de tais palavras é bem conhecida e feita com a ajuda da função Möbius . Usando esse resultado, os limites para alfabetos não unários, tanto no caso do DFA quanto no do NFA, são comprovados.nn

Vamos entrar em mais detalhes. Para um alfabeto com letras , defina f k ( n )k Observe quegk(n)= n

fk(n)=o número de DFA mínimos não isomórficos aos pares com n estadosgk(n)=o número de idiomas distintos aceitos pelos DFAs com n estadosGk(n)=o número de idiomas distintos aceitos pelos NFA com n estados
. Começamos comf1(k)eg1(k). gk(n)=Eu=1nfk(Eu)f1(k)g1(k)

Enumeração de DFAs unários

Um DFA unário com estados q 0 , , q n - 1 é mínimo seM=(Q,{uma},δ,q0 0,F)q0 0,...,qn-1

  1. Está conectado. Assim, após renomear, o diagrama de transição consiste em um loop e uma cauda, ​​ou seja, eδ( q n - 1 ,a)= q j para algunsjn-1.δ(qEu,uma)=qEu+1δ(qn-1,uma)=qjjn-1
  2. O loop é mínimo.
  3. Se , então q j - 1F e qj0 0qj-1Fou q j - 1Fe q n - 1F.qn-1Fqj-1Fqn-1F

O loop é mínimo se a palavra a ja n - 1 definida por a i = { 1qj,...,qn-1umajuman-1 forprimitivo, o que significa que não pode ser escrito na formaxk para alguma palavraxe algum número inteirok2. O númeroψk(n)de palavras primitivas de comprimentonsobrekd, em queμ(n)é afunção Möbius. Com a ajuda deψk(n)

umaEu={1E se qF,0 0E se qF
xkxk2
ψk(n)nk alfabetos com letra é conhecido, ver, por exemplo, Lothaire, Combinatorics on Words . Temos
ψk(n)=d|nμ(d)kn/d
μ(n)ψk(n) o papel prova fórmulas exactas para e g 1 ( n ) e mostra que assintoticamente (Teorema 5 e Corollary 6), g 1 ( n )f1(n)g1(n)
g1(n)=2n(n-α+O(n2-n/2))f1(n)=2n-1(n+1-α+O(n2-n/2)).

Enumeração de DFAs

O próximo passo é um limite inferior para . O teorema 7 afirma que f k ( n ) f 1 ( n ) n ( k - 1 ) nn 2 n - 1 n ( k - 1 ) n . Para um conjunto Δ Σ de um autômato M , defina M Δ como a restrição de M a Δ .fk(n)

fk(n)f1(n)n(k-1)nn2n-1n(k-1)n.
ΔΣMMΔMΔ
A prova funciona considerando o conjunto Sk,n de do DFA sobre o k -Carta alfabeto { 0 , 1 , ... , k - 1 } definida porMk{0 0,1,...,k-1}
  1. Permitir que seja um dos f 1 ( n ) DFAs unários diferentes em n estados eM{0 0}f1(n)n
  2. Escolhendo quaisquer funções h i : Q Q para 1 i < k e definindo δ ( q , i ) =k-1hEu:QQ1Eu<k para um i < k e q Q .δ(q,Eu)=hEu(q)1Eu<kqQ

A observação é então que contém f 1 ( n ) n ( k - 1 ) n línguas diferentes e mínimas.Sn,kf1(n)n(k-1)n

Enumeração de AFN

Para um tem o limite inferior trivial 2 n , já que todo subconjunto ϵ , a , , a n - 1 pode ser aceito por algum NFA com nG1(n)2nϵ,uma,...,uman-1n
G1(n)(c1nregistron)n
k2

n2(k-1)n2Gk(n)(2n-1)2kn2+1
(q,uma)Qδ(q,uma)2kn2{1,...,k}k[0 ..n-1]
M=(Q,Σ,δ,q0 0,F)Σ={0 0,1,...,k-1}Q={q0 0,...,qn-1}δ
δ(qEu,0 0)=q(Eu+1)modnpara 0 0Eu<nδ(qEu,j)=hj(Eu)para 0 0Eu<n,1j<k
hj:{1,...,n-1}2QF={qEu}Eu[0 ..n-1]2(k-1)n2nmaneiras de escolher o conjunto de estados finais. Pode-se então mostrar que nenhum desses NFAs aceita o mesmo idioma.
john_leo
fonte