DFA mínimo que satisface una vista finita de un idioma

Digamos que uno tiene un idioma $L \subseteq \Sigma^*$ , pero uno no sabe qué cadenas son realmente parte del idioma. Todo lo que uno tiene es una vista finita del lenguaje: un conjunto finito de cadenas $A \subseteq L$ que se sabe que están en el idioma, y ​​un conjunto finito de cadenas $B \subseteq (\Sigma^* \setminus L)$ que se sabe que no están en el idioma.

Por ejemplo, supongamos que tengo $A = \{ab, aaab, aaaaabb\}$ y $B = \{b, aab, aaaba\}$ . Puede que tenga el idioma $L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$ , ya que $A$y $B$ son consistentes con $L$ , o podría tener un lenguaje completamente diferente.

Mi pregunta es: ¿hay alguna forma conocida de crear un DFA (autómata finito determinista) que acepte las cadenas en $A$ y rechace las cadenas en $B$ , con un número mínimo o casi mínimo de estados? ¿Cuál es la complejidad de este problema? ¿Qué tan bueno es aproximar $L$ (suponiendo que $L$ tenga una complejidad descriptiva bastante baja, y $A$ y $B$ son grandes)?

Pregunta original en math.stackexchange.com. Decidí volver a publicar aquí después de no obtener respuestas a la pregunta original, y no tener idea de dónde buscarlas. Si alguien pudiera señalarme hacia una investigación en esta área, sería muy apreciado.

Como ya sabe por los comentarios, encontrar el DFA mínimo que satisface un conjunto finito de ejemplos positivos y negativos es -duro. Sin embargo, no toda esperanza está perdida, si usted está dispuesto a modificar su modelo de aprendizaje ligeramente entonces podemos volver a P .$\mathsf{NP}$$\mathsf{P}$

Suponga que usted está tratando de aprender un desconocido DFA que es mínimo para un lenguaje L W . Si permite las consultas de membresía del oráculo y actúa como maestro, responda la siguiente pregunta: Dado un DFA propuesto G, ¿reconoce L W ? Si no, ¿puede proporcionar un contraejemplo?$W$$L_W$$G$$L_W$

Tenga en cuenta que si el oráculo tiene acceso a , puede comparar G con W en tiempo polivinílico, ya que es fácil probar la igualdad entre lenguajes regulares. La generación de un contraejemplo también se puede hacer en tiempo polinómico.$W$$G$$W$

En este marco, puede aprender en tiempo polinomial utilizando el algoritmo de Angluin ( 1987 ; pdf ) (o el refinamiento de Schapire del mismo; consulte la sección 5.4.5). Para obtener más información sobre este modelo, aquí hay dos preguntas sobre cstheory y CS.SE al respecto:$W$

• Límites inferiores para aprender en la consulta de membresía y el modelo de contraejemplo

• ¿Hay mejoras en el algoritmo de Dana Angluin para aprender conjuntos regulares?

Me parece que puede usar un refinamiento de la equivalencia de Myhill-Nerode para este problema.

x ∈ Σ u x ∈ A v x ∈ B A B u $u\nsim v$$x\in\Sigma$$ux\in A$$vx\in B$$A$$B$$u$$v$

Es suficiente para estudiar esta relación sobre prefijos de elementos de y . Esto le dará un límite inferior en la cantidad de estados que necesita. No estoy seguro de que le brinde directamente una forma de construir el autómata mínimo, pero es al menos un camino para explorar.$A$$B$

Creo que este problema puede haber sido redactado de manera inexacta por el interrogador. Aparentemente, el interrogador quiere un algoritmo que generalice palabras infinitas basadas en ejemplos específicos de palabras finitas, utilizando algún tipo de inducción mecanizada, es decir, reconociendo patrones aparentes en los ejemplos.

Además de algunas investigaciones sobre la teoría de CS citadas en los comentarios, también hay más investigación empírica en esta área, por ejemplo, a continuación, utilizando ANN para crear FSM a partir de ejemplos. Tenga en cuenta que siempre se puede ejecutar un algoritmo de minimización de DFA estándar en el resultado. La biblioteca AT&T FSM es buena para trabajar en esta área.

El interlocutor no es específico sobre el dominio de su problema, eso puede ayudarlo a comprender la estructura de los ejemplos y obtener referencias más específicas. Sin embargo, un ejemplo que se puede ver son los algoritmos de IA en juegos que usan algoritmos FSM. Sospecho que hay algunos casos en los que los FSM se aprenden de ejemplos que utilizan algoritmos de aprendizaje.

[1] Aprendiendo una clase de grandes máquinas de estados finitos con una red neuronal recurrente C. Lee Giles, 1, BG Horne, T. Lin 1995

[2] Aprendizaje de FSM con redes recurrentes autoagrupadas por Zeng y Smyth 1993

[3] Biblioteca AT&T FSM