Decir que uno tiene un lenguaje $L \subseteq \Sigma^*$, pero uno no sabe qué cadenas son en realidad parte de la lengua. Todo lo que uno tiene es de un número finito de vista de la lengua: un conjunto finito de cadenas de $A \subseteq L$ que son conocidos en el lenguaje, y un conjunto finito de cadenas de $B \subseteq (\Sigma^* \setminus L)$ que no lo están en el idioma.
Por ejemplo, digamos que tengo la $A = \{ab, aaab, aaaaabb\}$$B = \{b, aab, aaaba\}$. Yo podría tener el idioma $L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$, ya que el $A$ $B$ son consistentes con $L$, o podría tener un lenguaje completamente diferente.
Mi pregunta es: ¿hay una forma conocida de crear un DFA (los autómatas finitos deterministas) que acepta las cadenas en $A$ y rechaza las cadenas en $B$, con una mínima o casi-el número mínimo de estados? ¿Cuál es la complejidad de este problema? ¿Cuán bueno es aproximar $L$ (asumiendo $L$ tiene un muy bajo descriptiva de la complejidad, y $A$ $B$ son grandes)?
No estaba seguro de si esta era la investigación de nivel para cstheory.stackexchange.com, así que voy a postear aquí. Me he tomado una puñalada en el tratando de encontrar una respuesta para esta pregunta, pero no tengo ni la menor idea de dónde buscar.
