Dado un DFA, A, deje que L (A) denote el número de palabras que A acepta. Creo que es fácil calcular L (A): traducir la codificación de A a una expresión regular. Si la estrella de Kleene aparece en algún lugar de la expresión, el lenguaje es infinito. De lo contrario: revisa y cuenta todas las combinaciones de palabras que se pueden hacer usando la expresión (básicamente si hay un operador + en la expresión, multiplica la cantidad de palabras legales por la cantidad de cadenas conectadas por el + ..)
¿Esto esta mal? Gracias por adelantado
regular-languages
automata
regular-expressions
usuario67573
fuente
fuente
Respuestas:
Sí, esto está mal, debido a la ambigüedad.
Considere el siguiente idioma: .( a + a a ) + a ( a + ϵ )
Con su método, vemos 4 palabras, . ¡Pero tenemos duplicados! Hay varias formas de hacer la misma palabra dentro de la expresión regular dada.a , a a , a a , a
Un mejor método es usar programación dinámica en un DFA mínimo para su idioma, sin estados "muertos". Si el DFA mínimo es cíclico, el lenguaje es infinito, por lo que podemos suponer que no hay ciclos. Usar un DFA es clave, porque el determinismo significa que hay exactamente un camino a través del DFA para cada palabra.
Lo que haces es crear una recurrencia para la cantidad de palabras que terminan en un estado dado:
El número total de palabras es entonces la suma del número de palabras que terminan en cada estado final.
fuente
Complementando la respuesta de jmite, no es demasiado difícil calcular el número de palabras en un idioma normal, utilizando el método de "matriz de transferencia". Esto es lo mismo que la programación dinámica de jmite, pero la técnica tiene otras aplicaciones, como la enumeración asintótica.
Dado un DFA, construya una matriz (donde es el conjunto de estados) en la que es el número de letras que hacen que el DFA se mueva del estado al estado . Sean y los indicadores del estado inicial y de los estados de aceptación, respectivamente. Finalmente, sea.Q × Q METRO Q METRO( i , j ) j yo 1q0 0 1F n = | Q |
El número de palabras de longitud es . Calcule para . Si , el lenguaje aceptado por el DFA es infinito. De lo contrario, el número de palabras en el idioma es .metro Cmetro: =1FMETROmetro1q0 0 Cmetro 0 ≤ m < 2 n Cnorte+ ⋯ +C2 n - 1> 0 C0 0+ ⋯ +Cn - 1
(Cuando se calculan las potencias de , se debe tener cuidado con respecto a la magnitud de las entradas, que es exponencial en . Dado que su tamaño es solo polinomial, el algoritmo resultante se ejecuta en tiempo polinomial).METRO metro
fuente
En realidad, aún puede derivar fórmulas de conteo para expresiones regulares inequívocas con estrellas de Kleene dentro.
Dada la definición inductiva de una expresión regular como:
Considere la siguiente traducción[[ ⋅ ]] : R e → C ( z) que toma una expresión regular y la traduce en una función racional de valores complejos:
Podemos mostrar que esta traducción devuelve una expresión racional haciendo inducción estructural enmi y observando que todas las operaciones utilizadas en el lado derecho conservan la racionalidad.
Supongamos que la expresión regularmi que ponemos es inequívoco, entonces encontraríamos que la función racional denotada por [[ e ]] ∈ C ( z) es en realidad la función generadora para la familia de palabras que son aceptadas por el lenguaje subyacente mi , clasificados por su longitud.
Por ejemplo, considere el idioma(una∗si)∗ , que define el lenguaje de las ejecuciones de una delimitado por si . Ahora, esta expresión regular no es ambigua, por lo que podemos ejecutar nuestro truco de traducción:
Como resultado, dada la función generadora anterior, su coeficiente de extracción será
De hecho, desde nuestra traducción[[ ⋅ ]] genera funciones racionales, podemos usar una descomposición de fracción parcial para crear una fórmula de enumeración para cualquier expresión regular inequívoca.
Supongamos que tiene una función racional irreducible
De hecho, la descomposición de fracción parcial se generaliza a funciones racionales multivariadas, por lo que en realidad puede construir fórmulas de conteo para consultas tales como "¿Cuántas palabras hay donde haynorte metro
a
s yb
s? "Desafortunadamente, la medida en que este método será útil termina cuando tiene una expresión ambigua.
fuente