(N) DFA con los mismos estados iniciales / de aceptación

¿Qué se sabe sobre la clase de idiomas reconocidos por autómatas finitos que tienen el mismo estado inicial y de aceptación? Este es un subconjunto adecuado de los idiomas regulares (ya que cada idioma contiene la cadena vacía), pero ¿qué tan débil es? ¿Existe una caracterización algebraica simple?

Lo mismo ocurre con los idiomas reconocidos por autómatas no deterministas que tienen el mismo conjunto de estados iniciales y de aceptación.

Esta pregunta se resuelve para autómatas deterministas y autómatas inequívocos en el libro [1]

[1] J. Berstel, D. Perrin, C, Reutenauer, Códigos y autómatas, vol. 129 de la Enciclopedia de Matemáticas y sus Aplicaciones, Cambridge University Press, 2009.

En el caso de autómatas deterministas, la caracterización se da en la Proposición 3.2.5. Recordemos que un submonoide de A * es unitaria derecho si, por todo u , v ∈ M , T , U v ∈ M implica v ∈ M . $M$$A^*$$u, v \in M$$u, uv \in M$$v \in M$

Proposición . Sea un subconjunto regular de A ∗ . Las siguientes condiciones son equivalentes:$L$$A^*$

1. es un submonoide unitario derecho,$L$
2. para algún código de prefijo P ,$L = P^*$$P$
3. El autómata mínimo de tiene un estado final único, es decir, el estado inicial.$L$
4. Existe un autómata determinista que reconoce que tiene el estado inicial como un estado final único.$L$

Para autómatas inequívocos, la caracterización se sigue del Teorema 4.2.2 y se puede establecer de la siguiente manera:

Proposición . Sea un subconjunto regular de A ∗ . Las siguientes condiciones son equivalentes:$L$$A^*$

1. es un submonoide libre de A ∗ ,$L$$A^*$
2. para algún código C ,$L = C^*$$C$
3. Existe un autómata inequívoco que reconoce que tiene el estado inicial como un estado final único.$L$

Finalmente, para autómatas no deterministas, la caracterización es simplemente que es un submonoide de A ∗ .$L$$A^*$

Los autómatas finitos en los que el estado inicial es también el único estado de aceptación tienen la forma , donde r es una expresión regular. Sin embargo, como J.-E. Pin señala a continuación, lo contrario no es cierto: hay idiomas de la forma r ∗ que no son aceptados por un DFA con un estado de aceptación único.$r^∗$$r$$r^*$

Intuitivamente, dada una secuencia de estados tal que q 0 = q n ya sea n = 0 o el diagrama de estado subyacente debe tener un ciclo que implica q 0 . El último caso es capturado algebraicamente por la estrella de Kleene.$q_0, \ldots, q_n$$q_0 = q_n$$n = 0$$q_0$

Una subclase importante de esta familia es una subclase de idiomas 0 reversibles. Un lenguaje es 0 reversible si la reversión del DFA mínimo para el lenguaje también es determinista. La operación de inversión se define como el intercambio de estados iniciales y finales, y la inversión de la relación de borde del DFA. Esto significa que un lenguaje 0 reversible solo puede tener un estado de aceptación. Su pregunta es agregar una restricción adicional de que este estado debería ser el estado inicial. Su restricción no define los idiomas reversibles 0 porque el DFA mínimo para esos idiomas puede tener estados iniciales y finales distintos.

La clase de idiomas reversibles es interesante porque fue una de las primeras familias de idiomas con infinitas cadenas que solo se pudo aprender de ejemplos positivos. El artículo de Angluin también proporciona una caracterización algebraica.

Inferencia de idiomas reversibles , Dana Angluin, Journal of the ACM, 1982

Puede referirse a los autómatas de semiflores, como dice su artículo: "Un autómata de semiflores (SFA) es un autómata de corte con un estado inicial único que es igual a un estado final único en el que todos los ciclos pasarán por el estado inicial-final ". Consulte "LA DESCOMPOSICIÓN DE LA HOLONOMÍA DE LOS AUTOMÁTICOS CIRCULARES DE SEMIA FLORES" -Shubh Narayan Singh, KV Krishna.