¿Cómo y cuándo agregar estado muerto en autómatas definidos?

Hola, aquí hay un ejemplo para ti.

Suponga que está haciendo una máquina (Autómatas finitos) que puede tomar su entrada del conjunto de Alfabetos (az) y el conjunto de números (o-9).

Para esto, usted impone la restricción de que la máquina procese la información SOLO SI VE un Alfabeto como entrada. en ese caso, harás una máquina que tiene 3 estados:

¿Son increíbles las IIT solo por la calidad de los estudiantes que hay allí? No es la facultad, la enseñanza, etc. (¿Jairam Ramesh tiene razón?)
¿Cuál es la diferencia entre Prolog y Python con respecto a la codificación de problemas de inteligencia artificial?
¿Cómo puedes usar una computadora?
¿Qué me estoy perdiendo si estoy usando Windows 7 en lugar de Linux / Ubuntu?
¿Por qué Valve eligió Debian como base de SteamOS?

Estado-1: estado inicial, la máquina no ha visto nada

Estado-2: El estado, cuando la máquina ve un alfabeto.

Estado-3; El estado, cuando la máquina ve un dígito. En este caso, la máquina nunca llegaría al estado final, incluso si ve un alfabeto después del dígito. ESTE ES EL ESTADO MUERTO, donde la FA entra en modo muerto.

Aquí está la FA para ese problema, el estado 3 es nuestro estado Muerto.

PD: la etiqueta “az” en la rama del estado 1–3 debe aparecer en la rama del estado 3–3.

¿Son los gráficos la estructura de datos primaria que se encuentra en la naturaleza?

¿Qué es mejor, BITS Goa CS o Hyderabad CS?

Arquitectura del procesador: ¿Cuál es la diferencia entre las CPU de 32 bits y las de 64 bits? ¿Cómo aumenta el rendimiento de las CPU de 64 bits?

¿Cuáles son algunos concursos / tareas populares en el análisis morfológico de los lenguajes naturales?

¿Qué pasaría si un robot autoconsciente cometiera un asesinato o cualquier otro delito? ¿Se les aplican las leyes actuales?

¿Qué rama de la física es la más cercana a la informática?

Un estado muerto en un autómata finito determinista (creo que esto es lo que querías decir con ‘definido’) es un estado en el que una vez que el autómata llega a él, nunca puede volver a ningún otro estado. Tratemos de entenderlo a través de un ejemplo:

Decir:

L = {Cualquier cadena de a y b con como máximo 2 a’s}

Entonces, antes que nada, juzguemos algunas de las cadenas que pueden ser parte de este lenguaje:

cuerda vacía
una
si
ab
licenciado en Letras
tejido
Automóvil club británico
tejido
aab …… b
abab
b… .bab..bab… b

Y así sucesivamente, y con todas estas cadenas como entradas, su autómata debería alcanzar su estado / estados finales.

Pero las siguientes cadenas, estrictamente no son parte de este lenguaje:

aaa
ababa
Automóvil club británico
b … baaba..a

Y así sucesivamente, para todos estos casos, su autómata debe estar en un estado no final.

El DFA para esto se puede construir de la siguiente manera:

Como este lenguaje acepta cadenas vacías, el estado inicial será un estado final.
Los estados registrarán el recuento de a.
Si hay más de dos a en la cadena, el autómata nunca debería aceptar esa cadena.

El siguiente es el diagrama para el mismo (lo siento por mis pobres habilidades de dibujo).

Aquí QD es el estado muerto. Ahora, piense en lugar de introducir este nuevo estado, si hubiéramos regresado a cualquier otro estado intermedio (es decir, 1, 2 o 3), entonces se habría aceptado al menos una de las cadenas incorrectas (verifique esto …).

Solo intenta esto entonces:

L = {Cualquier cadena de a y b con al menos 2 b’s y al menos 2 a’s}

Espero que esta comprensión ayude …

Snehangshu Chakraborty

Los estados muertos son aquellos estados que no aceptan cuyas transiciones para cada símbolo de entrada terminan en sí mismas.

Ej: Dibuje DFA para todas las cadenas de longitud como máximo 3.

La cadena de longitud> 3 debe rechazarse por un estado muerto o un estado de falla. En la figura de abajo, el estado muerto es q4.