¿Cuál es el número de idiomas aceptados por un DFA de tamaño ?

19

La pregunta es simple y directa: para un fijo , ¿cuántos idiomas (diferentes) son aceptados por un DFA de tamaño (es decir, estados)? Declararé formalmente esto:nnn

Defina un DFA como , donde todo está como de costumbre y es una función (posiblemente parcial). Necesitamos establecer esto ya que a veces solo las funciones totales se consideran válidas.(Q,Σ,δ,q0,F)δ:Q×ΣQ

Para cada , defina la relación (equivalencia) en el conjunto de todos los DFA como: \ mathcal {A} \ sim_n \ mathcal {B} if | \ mathcal {A} | = | \ mathcal {B} | = n y L (\ mathcal {A}) = L (\ mathcal {B}) .n1A n B | A | = | B | = n L ( A ) = L ( B )nAnB|A|=|B|=nL(A)=L(B)

La pregunta es, entonces: para un n dado n, ¿cuál es el índice de n ? Es decir, ¿cuál es el tamaño del conjunto {L(UN)UN es un DFA de tamaño norte} ?

Incluso cuando δ es una función total, no parece ser un recuento fácil (al menos para mí). Es posible que el gráfico no esté conectado, y los estados en el componente conectado que contiene el estado inicial podrían estar aceptando, por lo que, por ejemplo, hay muchos gráficos de tamaño norte aceptan Σ . Lo mismo con otras combinaciones triviales para el idioma vacío y otros idiomas cuyo DFA mínimo tiene menos de norte estados.

(Una ingenua) recurrencia tampoco parece funcionar. Si tomamos un DFA de tamaño k y agregamos un nuevo estado, entonces, si queremos mantener el determinismo y hacer que el nuevo gráfico esté conectado (para tratar de evitar casos triviales), tenemos que eliminar una transición para conectar el nuevo estado, pero en ese caso podemos perder el idioma original.

¿Alguna idea?

Nota. Actualicé la pregunta nuevamente, con una declaración formal y sin los elementos de distracción anteriores.

Janoma
fuente
Solo para aclarar: ¿Te refieres a "cuántos idiomas diferentes se pueden definir usando estados?", Donde un lenguaje se define usando estados si hay un DFA con estados que lo acepta. Además, para las expresiones regulares, la expresión regular "a * aaaaaa" seguramente tiene> 1 concatenaciones, pero el DFA solo necesita un estado (dos si necesita un receptor por separado), ¿no? nnn
Evgenij Thorstensen
Disculpas: para el ejemplo de expresiones regulares, debería ser "a a a a a *", ya que eso permite cualquier número.
Evgenij Thorstensen
La definición de parece estar muy relacionada con la noción de "profundidad de punto", excepto que el concepto se aplica normalmente a lenguajes libres de estrellas (probablemente por las razones que describió @Evgenij Thorstensen). c(r)
mhum
1
Observación trivial: se pueden usar estados para definir al menos idiomas diferentes. n+12n
Evgenij Thorstensen
2
Podemos obtener un poco más, por lo que parece estar bien. Pero el número de autómatas de estado n es alrededor de (suponiendo ) ¿Podemos obtener ? n c n 2 n = 2 c n log n + n = 2 Θ ( n log n ) | Σ | = c 2 ω ( n )2Ω(norte)norteCnorte2norte=2CnorteIniciar sesiónnorte+norte=2Θ(norteIniciar sesiónnorte)El |ΣEl |=C2ω(n)
Kaveh

Respuestas:

20

Creo que esta pregunta ha sido estudiada previamente. Mike Domaratzki escribió una encuesta sobre investigación en esta área: "Enumeración de idiomas formales", Bull. COMER, vol. 89 (junio de 2006), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf

Hermann Gruber
fuente
44
El documento aborda con precisión la pregunta formulada, desde la página 120 en adelante. Es la función , y el documento da límites bastante estrechos (cerca de lo que Kaveh menciona arriba), aunque no he inhalado todos los detalles. gk(n)
Evgenij Thorstensen
1
En efecto. Lo que queremos, entonces, es , o, por la relación dada, f k ( n ) , que es el número de DFA mínimos no isomórficos por pares con n estados sobre un alfabeto k -letter. Tampoco lo he mirado en detalle, pero parece que solo se conocen límites, no cantidades exactas. gk(n)fk(n)nk
Janoma el
66
Y, del mismo autor, tenemos el artículo Sobre el número de idiomas distintos aceptados por autómatas finitos con n estados , que incluso proporciona cálculos explícitos para ( 1 n 10 ), g 2 ( n ) ( 1 n 6 ) y g 3 ( n ) ( 1 n 4 ). g1(n)1n10g2(n)1n6g3(n)1n4 4
Janoma el