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 ₀ , 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
q₀- un estado inicial q ₀ ∈ 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.