Número de DFAs mínimos de tamanho, no máximo,

9

Seja um alfabeto de tamanho e considere DFAs mínimos, cujo tamanho é limitado por no máximo . Seja o número de diferentes DFAs mínimos.2 m f ( m )Σ2mf(m)

Podemos encontrar uma fórmula de forma fechada para ?f(m)

Considerando que para a função de transição de um DFA de tamanho no máximo é um gráfico. Como o grau dos nós é delimitado por , para cada nó existem possibilidades de pares de arcos (conforme sugerido nos comentários). Neste gráfico, existem no máximo opções possíveis de estado inicial e no máximo opções possíveis de conjuntos de estados finais. Assim, o número máximo de DFAs de tamanho no máximo é .|Σ|=2m2m2m2mmf(m)m2mm2m=2mm2m+1

Podemos generalizar para um alfabeto arbitrário : o limite se torna . Σf(m)2mm|Σ|m+1

Mas limitamos aqui os DFAs arbitrários e estou interessado em limitar o número mínimo de DFAs. Assim, parece que esse limite poderia ser mais apertado ... Alguém tem uma estimativa melhor?

Eu apreciaria, se possível, alguns trabalhos relacionados a esse problema ou uma prova / contra-exemplo.

Luz
fonte
11
Não acho que seu limite superior esteja correto. Parece que deve ser , em vez de . Para cada nó, considere os dois arcos que saem desse nó; existem possibilidades para onde o primeiro arco vai, e possibilidades para onde o segundo arco vai, então possibilidades no total. Como existem nós, obtemos possibilidades para o conjunto de arcos. A generalização seria . f(m)m×2m×m2mf(m)m×2m×22mmmm2m(m2)m=m2mf(m)m×2m×m|Σ|m
DW
4
Aqui é uma referência que pode ser relevent: "sobre o número de DISTINCT línguas aceites pelo Autômatos Finitos com N estados" - citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.2838
Michael Wehar
2
Agradeço a vocês por corrigirem meu erro e me fornecerem essa referência que é de fato relevante.
Luz

Respostas:

7

De acordo com Ishigami Y., Tani S. (1993) As dimensões VC de autômatos finitos com n estados, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , a dimensão VC de a classe de conceito de DFAs de estados em um alfabeto de tamanho k é d = d ( n , k ) : = ( k - 1 + o ( 1 ) ) n log 2 n . Segue-se que existem pelo menos 2 d autômatos n- state distintos em um knk

d=d(n,k):=(k1+o(1))nlog2n.
2dnkalfabeto de letras. O limite superior do número de tais autômatos segue de um argumento simples de contagem (fornecido no artigo) e é no máximo .2d
Aryeh
fonte
Obrigado. Entendo pela sua resposta que existem m DFAs de estados (pelo menos e no máximo). Mas estou interessado em contar o mínimo de DFAs. Assim, o seu limite superior não contradiz o dado na minha resposta, certo? m(|Σ|1+o(1))m m
Luz
Eu acho que isso também conta com DFAs mínimos, já que a dimensão VC é independente da representação, na verdade, está contando idiomas distintos - que correspondem a DFAs mínimos.
Aryeh 22/02
oh :( então seu limite está contradizendo meu ... desde meu tem um grande denominador o que o torna muito abaixo seu ... como é que ??(m1)!
Luz
Não vejo bem a contradição - o denominador grande ainda é inundado por m m no numerador. (m1)!mm
Aryeh 22/02
De fato, se você olhar para a prova de Thm. 3.2 no artigo que vinculei, você verá a expressão exata no denominador.
Aryeh 22/02
4

(Nota: o limite superior indicado na resposta aceita é melhor ou igual ao indicado aqui)

Um limite superior é proposto neste artigo, dado em um dos comentários anteriores: Sobre o número de línguas distintas aceitas por autômatos finitos com n estados ” (2002, M. Domaratzki, D. Kisman, J. Shallit) .

Nesse papel:

  • o função fornece o número de DFAs mínimos não isomórficos distintos com estados- m ao longo de um | Σ | alfabeto de letras ,f|Σ|(m)m|Σ|
  • g|Σ|(m)m|Σ|

g|Σ|(m) mm

68g|Σ|(m)2mm|Σ|m(m-1 1)!2mm|Σ|m+1 1

f|Σ|(m)

Luz
fonte