Expresión regular NFA del sistema formal
Algoritmo para convertir expresión regular (Regular Expression) en NFA.
Entrada: expresión regular R definida en el conjunto de texto (NT).
Salida: An NFA que puede aceptar el lenguaje definido por la expresión regular R.
(1) Para el NFA establecido.
(2) Para el símbolo terminal a El NFA creado es
Cada vez que se necesita un nuevo estado, se le asigna un nuevo número, de modo que no hay dos estados que puedan tener el mismo número.
Expresión regular NFA (cont.)
Expresión regular NFA (cont.)
(3) Utilice el método de construcción NFA de las dos expresiones regulares básicas (Expresión regular básica) anterior, puede utilizar estos dos para construir una expresión regular compuesta. (Expresión regular compuesta) en una NFA De acuerdo con las siguientes reglas de conversión, la expresión regular R se puede establecer con éxito en una NFA completa.
Primero, debe establecer un estado inicial (Estado inicial) Si y un estado final (Estado Final) Sf.
Si hay una expresión regular compuesta de tipo R1│R2, la NFA construida es la siguiente:
Expresión regular NFA(cont.)
Si hay una expresión regular compuesta de tipo R1 R2, el NFA construido es el siguiente:
Expresión regular NFA(cont'd)
Si hay es una expresión regular compuesta de tipo R1*, el NFA construido es el siguiente:
Expresión regular NFA(cont'd)
Ejemplo: convertir la expresión regular R=(0│ 1)*01 en NFA.
Primero descomponga la expresión regular R en sus componentes básicos de la siguiente manera: De acuerdo con la estructura de la figura anterior, encuentre su NFA básico (NFA primitivo) y su NFA compuesto (NFA compuesto). ).
Expresión regular NFA (cont.)
(1) Para el primer componente base (Componente Primitivo) R1, es decir, el NFA básico construido para el primer símbolo terminal 0 es el siguiente:
(2) De la misma manera, el NFA básico construido para R2 es:
NFA de expresión regular (cont.)
(3) El AFN compuesto construido para R3= R1│R2 es el siguiente:
(4) Debido a que R4=(R3), el AFN de R4 es el mismo que el de R3. El AFN es exactamente el mismo.
NFA de expresión regular (cont.)
(5) El NFA de expresión regular construido para R5= R4* es el siguiente:
NFA de expresión regular (cont. 'd)
(6) El NFA básico construido para R6=0 es el siguiente:
: El estado 7' se toma de modo que no sea necesario modificarlo más adelante cuando fusionándose. Valores de otros estados.
Expresión regular NFA(cont'd)
(7) R7= R5 La NFA básica construida por R6 es la siguiente:
:El estado 7 se fusiona con el estado 7' para formar el estado 7.
Expresión regular NFA (cont.)
(8) Repita los pasos anteriores para construir R9 =(0│1)*01 El NFA es el siguiente:
NFA DFA
Generalmente, el símbolo de entrada contiene (cadena vacía)
Paso 1: Un NFA llamado N quiere convertirse en un nombre es el DFA de D, el estado inicial de D
El estado inicial es un conjunto que contiene el estado inicial s0, por lo que este estado s0 se agrega a -CLOSURE (s0), y los estados que se pueden alcanzar desde s0 a través del símbolo de entrada se agregan a este -CLOSURE (s0) Este conjunto. is Para el estado inicial de este DFA, sea el estado marcado.
Paso 2: Para los elementos en el estado marcado, para cada símbolo de entrada a() si estado marcado, si f(si, a) = sj, coloque todo en un conjunto T y -CLOSURE(T), si no es igual al estado existente, configúrelo en estado sin marcar.
Paso 3: encuentre el siguiente estado sin marcar, configúrelo para marcar indicado, repita el paso hasta que no haya ningún estado sin marcar.
NFA DFA
NFA DFA
Paso 4: Se puede obtener una tabla de transición de lo anterior pasos Si contiene el estado inicial (o estado final) del NFA original, entonces este estado es el estado inicial (o estado final).
Paso 5: Encuentre el diagrama de transición de acuerdo con la Tabla de transición. .
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
DFA convertido de NFA, en el que algunos estados se pueden fusionar en uno solo. En cuanto a cómo minimizar el número de estados en DFA, hay tres pasos:
Paso 1: combinar todos los estados en DFA. en El grupo de estados (Grupo) G se divide en un grupo de estados terminal F y un grupo de estados no terminal (G-F).
Paso 2: Divida todos los grupos de estados mediante el siguiente procedimiento de división (Procedimiento SPLIT) (División) procesamiento Si algún grupo de estados se divide debido al programa de división, el proceso de división continuará hasta que todos los grupos de estados ya no puedan dividirse.
Minimización de DFA
Minimización de DFA. (cont.)
Paso 3: Convertir cada grupo de estados en un nuevo estado (Estado).
Paso cuatro: Eliminar todos los estados muertos (es decir, el estado); no es el estado inicial y no se puede alcanzar desde otros estados.
Minimización de DFA (cont.)
Procedimiento SPLIT
comenzar
para cada grupo G de P
comience
dividir G en subgrupos de modo que dos estados s y t de G estén
en el mismo subgrupo si y solo para todos los símbolos de entrada a, los estados s
y t tienen transiciones a estados en el mismo grupo de P;
reemplazan todos los subgrupos que se formaron en P;
fin
fin
Minimización de DFA (cont.)
Ejemplo
Minimización de DFA (c
continuación)
Minimización de DFA (cont.)
Paso 1: Divida los estados A, B, C, D, E en grupos de estados no terminales {A, B, C,D} y el grupo de estados terminales.
Paso 2: Dado que el grupo de estados terminales solo contiene un estado E, no es necesario dividirlo nuevamente. Los estados {A, B, C, D. } son procesados por el programa de división. Se sabe que los estados A, B, C y D se transfieren al estado B (que pertenece al mismo grupo de estados {A, B, C, D}) para el símbolo de entrada 0. Pero para símbolo de entrada 1, grupo de estados {entre A, B, C, D}, solo el estado D se transferirá al grupo de estados, mientras que los estados A, B, C se transferirán todos al grupo de estados {C, D}, por lo que el grupo de estados {A, B, C, D} se divide en {A, B, C} y dos grupos de energía de estados. Dado que el grupo de estados solo contiene un estado D, no es necesario dividirlo más. grupo de estados {A, B, C}. Para el símbolo de entrada 0, los estados A, B y C se transfieren todos al estado B, pero para el símbolo de entrada 1, solo el estado B se transferirá al estado D (es decir, en el grupo de estados), por lo que el grupo de estados {A, B, C} se divide en {A, C}. En este punto, ya no se puede dividir.
Minimización de DFA (cont.)
Paso 3: Haga de cada grupo de estados un nuevo estado
{A,C}=S1
Sea {A,C}=S1
= S2
= S3
= S4
Paso 4: No hay ningún estado muerto, por lo que no es necesario eliminar ningún estado.
La tabla de transición que se puede obtener de lo anterior es
p>Finalmente, el DFA para encontrar el número mínimo de estados es
FA Regular Grammar
Un método para convertir autómatas finitos en gramática regular:
(1) Si el estado A alcanzará el estado B para el símbolo terminal de entrada a, y el estado B no es el estado terminal (final Estado), entonces su gramática regular es A aB.
(2) Si el estado A alcanzará el estado B para el símbolo terminal de entrada a, y el estado (Estado final), entonces su gramática regular A a, A aB.
(3) Si el estado A para el símbolo terminal de entrada a alcanzará el estado A mismo, y el estado A es tanto el estado inicial (estado inicial) como el estado terminal, por lo que es regular la gramática es A, A a y A aA.
Ejemplo:
Entonces su gramática regular es G=,N={S,A,B,C},T={0 ,1},P={
S , A 0C, B 0C , C 0C,
S 0, A 1C, B 1B, C 1C}
S 0A, B 1,
S 1,
S 1B,
Según la gramática anterior, se puede encontrar que el idioma correspondiente es L( G)={0,1*}.