El DFA más pequeño que acepta cadenas dadas y rechaza otras cadenas dadas

11

Dados dos conjuntos de cadenas sobre el alfabeto , ¿podemos calcular el autómata determinista de estado finito (DFA) más pequeño de modo que y ? $A,B$ $\Sigma$ $M$ $A \subseteq L(M)$ $L(M) \subseteq \Sigma^*\setminus B$

En otras palabras, representa un conjunto de ejemplos positivos. Cada cadena en debe ser aceptada por el DFA. representa un conjunto de ejemplos negativos. DFA no debe aceptar ninguna cadena en $A$ $A$ $B$ $B$

¿Hay alguna manera de resolver esto, quizás utilizando técnicas de minimización de DFA ? Me imagino creando un autómata tipo DFA que tiene tres tipos de estados: aceptar estados, rechazar estados y estados "no importa" (cualquier entrada que termine en un estado "no importa" puede ser aceptada o rechazado). Pero, ¿podemos encontrar una manera de minimizar esto a un DFA ordinario?

Podría pensar en esto como el problema de aprender un DFA, dados ejemplos positivos y negativos.

Esto está inspirado en ¿Es regex golf NP-Complete? , que hace preguntas similares para expresiones regulares en lugar de DFA.

1

Creo que tendrá que poner algún tipo de restricción sobre qué tipos de idiomas pueden ser y y cómo se pueden especificar.

A

$A$

B

$B$

reinierpost

Hay mucha literatura sobre funciones de aprendizaje / idiomas, por ejemplo, archivada bajo aprendizaje en el límite (también aprendizaje al estilo Gold). Estos no se ajustan exactamente a su problema, pero pueden ser interesantes.

Raphael

7

Un DFA como lo describe se llama DFA de separación . Existe cierta literatura sobre este problema cuando y son idiomas regulares, como Aprendizaje de DFA de separación mínima para verificación de composición, por Yu-Fang Chen, Azadeh Farzan, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw Wang $A$ $B$

Tenga en cuenta que, como dice @reinierpost, sin restricciones en A y B, el problema puede volverse indecidible.

Shaull
fuente

Si A y B son ambos lenguajes regulares, y si uno puede aceptar o rechazar arbitrariamente cualquier entrada para la que A y B arrojarían el mismo resultado, no veo cómo el problema podría ser indecidible. Para un DFA de cualquier tamaño en particular, sería posible construir un conjunto completo de entradas que debería aceptar y entradas que debería rechazar, de modo que cualquier DFA con el mismo número de estados o menos que maneje correctamente todos los casos de prueba Se puede garantizar un comportamiento idéntico en todos los casos. Dado que una máquina que acepta todo, A acepta y rechaza todo lo demás ...

supercat

... satisfacer las restricciones, uno puede poner un límite superior en el número de estados que una máquina tendría que contener; Dado que hay un número finito de máquinas posibles de cualquier tamaño, y un número finito de casos de prueba para evaluar, se podrían generar todas las máquinas posibles que sean más pequeñas que A y ver si alguna de ellas cumple las condiciones necesarias. No es exactamente una forma rápida de resolver el problema, pero ciertamente es decidible si A y B son regulares. Si no son regulares, un DFA no podría resolver A o B. La "diferencia" a veces podría ser regular incluso si A y B no lo son, pero eso ...

supercat

... sería un caso "inusual".

supercat

8

Existe una gran cantidad de literatura sobre el aprendizaje de DFA que reciben muestras positivas y negativas. Sin embargo, si y son finitos, no veo cómo el problema sería indecidible. Si entonces obviamente el DFA que acepta solo las cadenas en satisface su requisito y uno simplemente puede enumerar todos los DFA más pequeños. Si entonces claramente no existe tal DFA. $A$ $B$ $A \cap B = \emptyset$ $A$ $A \cap B \neq \emptyset$

Encontrar el DFA mínimo consistente con un conjunto dado de cadenas es NP-completo. Este resultado aparece como Teorema 1 en el artículo de Angluin sobre la complejidad de la inferencia mínima de conjuntos regulares . Claramente, su problema también es NP-completo.

Para obtener muchos enlaces buenos y debates sobre el aprendizaje de idiomas regulares, consulte la publicación de blog CSTheory sobre el aprendizaje de idiomas regulares .

Alto
fuente

Si se cambiaran los requisitos para que un autómata pudiera aceptar o rechazar arbitrariamente cualquier cosa que esté en A y B, entonces el problema siempre sería solucionable para cualquier A y B; si encontrar el autómata óptimo sería NP-completo sin hacer eso, sería NP-completo incluso con ese requisito.

supercat

El DFA más pequeño que acepta cadenas dadas y rechaza otras cadenas dadas

Respuestas: