Construcción de un FA a partir de un RE
Podemos usar la construcción de Thompson para encontrar un autómata finito a partir de una expresión regular. Reduciremos la expresión regular a expresiones regulares más pequeñas y las convertiremos a NFA y finalmente a DFA.
Algunas expresiones RA básicas son las siguientes:
Case 1 - Para una expresión regular 'a', podemos construir el siguiente FA -
Case 2 - Para una expresión regular 'ab', podemos construir el siguiente FA -
Case 3 - Para una expresión regular (a + b), podemos construir el siguiente FA -
Case 4 - Para una expresión regular (a + b) *, podemos construir el siguiente FA -
Método
Step 1 Construya un NFA con movimientos nulos a partir de la expresión regular dada.
Step 2 Elimine la transición nula de NFA y conviértala en su DFA equivalente.
Problem
Convierta el siguiente RA en su DFA equivalente - 1 (0 + 1) * 0
Solution
Concatenaremos tres expresiones "1", "(0 + 1) *" y "0"
Ahora quitaremos el εtransiciones. Después de quitar elε transiciones del NDFA, obtenemos lo siguiente:
Es un NDFA correspondiente al RE - 1 (0 + 1) * 0. Si desea convertirlo en un DFA, simplemente aplique el método de conversión de NDFA en DFA que se describe en el Capítulo 1.
Autómatas finitos con movimientos nulos (NFA-ε)
Un autómata finito con movimientos nulos (FA-ε) transita no solo después de dar la entrada del conjunto alfabético, sino también sin ningún símbolo de entrada. Esta transición sin entrada se llamanull move.
Un NFA-ε está representado formalmente por una tupla de 5 (Q, ∑, δ, q 0 , F), que consta de
Q - un conjunto finito de estados
∑ - un conjunto finito de símbolos de entrada
δ- una función de transición δ: Q × (∑ ∪ {ε}) → 2 Q
q0- un estado inicial q 0 ∈ Q
F - un conjunto de estados finales de Q (F⊆Q).
Lo anterior (FA-ε) acepta un conjunto de cadenas: {0, 1, 01}
Eliminación de movimientos nulos de autómatas finitos
Si en un NDFA, hay ϵ-mover entre el vértice X al vértice Y, podemos eliminarlo usando los siguientes pasos:
- Encuentre todos los bordes salientes de Y.
- Copie todos estos bordes comenzando desde X sin cambiar las etiquetas de los bordes.
- Si X es un estado inicial, haga que Y también sea un estado inicial.
- Si Y es un estado final, convierta X también en un estado final.
Problem
Convierta el siguiente NFA-ε en NFA sin movimiento nulo.
Solution
Step 1 -
Aquí la transición ε es entre q1 y q2, Entonces deja q1 es X y qf es Y.
Aquí los flancos salientes de q f son af para las entradas 0 y 1.
Step 2 -
Ahora copiaremos todas estas aristas de q 1 sin cambiar las aristas de q f y obtendremos el siguiente FA -
Step 3 -
Aquí q 1 es un estado inicial, entonces hacemos q f también un estado inicial.
Entonces la FA se convierte en ...
Step 4 -
Aquí q f es un estado final, entonces hacemos q 1 también un estado final.
Entonces la FA se convierte en ...
