El autómata finito que reconoce el lenguaje vacío $ \emptyset $

Question

Ya que el lenguaje $L = \emptyset $ es regular, debe haber un autómata finito que lo reconozca. Sin embargo, no estoy exactamente seguro de cómo se construiría uno. Siento que la respuesta es trivial. ¿Puede alguien ayudarme?

Answer 1

Un estado, sin aceptar, y sin transiciones. (Eso es un NFA; si quieres un DFA, ten una transición del estado a sí mismo por cada letra del alfabeto que se especifique).

Answer 2

Sólo tiene un estado $s$ que es inicial, pero que no acepta con bucles $s \overset{\alpha}{\rightarrow} s$ para cualquier letra $\alpha \in \Sigma$ (con el autómata no determinista se pueden incluso omitir los bucles, es decir, la relación de transición estaría vacía).

Espero que esto ayude ;-)

Answer 3

Un lenguaje dado es un "lenguaje vacío" y tenemos que construir un autómata finito para este lenguaje. En general, consideramos "la construcción de autómatas finitos" como "la construcción de DFA". Así que....{ Supongamos que los símbolos de entrada son 'a' y 'b'}

(a) Si tomamos un estado (estado inicial) y no mostramos ninguna transición de cualquier símbolo de entrada sobre este estado, entonces esta estructura no será un DFA porque en un DFA debe haber una transición de todos los símbolos de entrada sobre cada estado. (b) Si tomamos un estado (estado inicial) y mostramos la transición de ambos símbolos de entrada 'a' y 'b' sobre este estado, entonces tampoco será un DFA porque debería haber un estado final. (c)Si tomamos un estado (estado inicial) y mostramos la transición de ambos símbolos de entrada 'a' y 'b' sobre este estado, y haciendo este estado final también, entonces este AF no será aceptor de "lenguaje vacío". (d) Si tomamos un estado inicial 'A' (sin hacerlo final) mostrando la transición de ambos símbolos de entrada sobre 'A' y tomando otro estado 'B' (como final) mostrando la transición de ambos símbolos de entrada sobre el "borde de transión" desde el estado final 'B' al estado inicial 'A' ('B' es el ESTADO NO ALCANZABLE aquí), entonces esta estructura será un AFD pero no un AFD mínimo porque en el AFD mínimo eliminamos el ESTADO NO ALCANZABLE. (e) De forma similar, no podemos tomar el concepto de estado muerto en la construcción de un DFA mínimo.

ASÍ QUE AHORA LA SOLUCIÓN EXACTA ES :-

" TOMA UN ESTADO INICIAL 'A'(no lo hace final) y OTRO ESTADO 'B'(lo hace final) y MUESTRA la transición de ambos símbolos de entrada 'a' y 'b' sobre ambos estados A' y 'B'. PERO no conecte ambos estados con ningún borde de transición. Este es el DFA mínimo deseado que acepta un "lenguaje vacío".

Answer 4

Este es el DFA que itera sobre (0|1)* pero no acepta nada (ni siquiera una cadena vacía).