Las máquinas DFA están diseñadas para aceptar el tipo específico de entrada cuya salida se genera mediante la transición del alfabeto de entrada de cada estado.
Acercarse :
- En esta situación, todas las strings son aceptables excepto más de 3 ceros. En este tipo de string no se aceptan tres ceros continuos.
- Cree el estado inicial y comience con la longitud mínima de la string posible, haga la transición de su entrada 0 y 1 a los estados posibles.
- según la transición, observe el estado final y márquelo.
Diseño de DFA paso a paso:
Paso 1:
haga un estado inicial, diga «A», las strings mínimas posibles son 1 y 0 y también se acepta cualquier número de 1. Para hacer esto, coloque el bucle automático de 1 en el estado «A» y haga la transición del alfabeto de entrada 0 al estado «B». Debido a que solo los 1 son aceptables, el estado «A» también se denomina estado final.
Paso 2:
como un solo cero es aceptable en la string, haga que el estado «B» sea el estado final. Transecte la entrada 0 del estado «B» al estado «C».
Paso 3:
como cada 00 es seguido inmediatamente por 1, ahora, después del estado «C», haga la transición de la entrada 1 del estado «C» al estado «A».
Paso 4:
Nos quedamos con la transición del alfabeto de entrada 1 del estado «B». Así que haga la transición de 1 del estado «B» al estado «A».
Paso 5:
después de 00, no se acepta más cero en continuidad. Por lo tanto, transectar 0 del estado «C» al estado muerto «D».
Paso 6:
Ingrese el alfabeto 0 y 1 del transecto de estado muerto al propio estado muerto.
Tabla de transición y reglas de transición del DFA anterior:
el estado «A» es tanto el estado final como el inicial, el estado «C» es el estado final, el estado «D» es el estado muerto. El estado inicial se representa con —> y los identificadores de estado final se representan con *.
| Estado | Entrada (0) | entrada (1) |
|---|---|---|
| —>A* (estado inicial y final ambos) | B | A |
| B* (estado final) | C | A |
| C | D (estado muerto) | A |
| D (estado muerto) | D (estado muerto) | D (estado muerto) |
Q’: conjunto de conjuntos finitos = {A, B, C, D}
conjunto de alfabetos de entrada = {0, 1}
Las reglas de transición informan sobre la función de transición que funciona en cada estado con cada alfabeto de entrada.
Publicación traducida automáticamente
Artículo escrito por _mridul_bhardwaj_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA