Upload
vothuan
View
217
Download
0
Embed Size (px)
Citation preview
Modelos de Computación ITema 2: Autómatas Finitos
Serafín MoralDepartamento de Ciencias de la Computación
Modelos de Computación ITema 2: Autómatas Finitos– p.1/88
Contenido
Autómata Finito Determinista
Autómata Finito No-Determinista
Autómata Finito con Transiciones Nulas
Expresiones Regulares
Gramáticas Regulares
Autómatas con Salida: Máquinas de Moore y de Mealy
Modelos de Computación ITema 2: Autómatas Finitos– p.2/88
Importancia de los autómatas finitos
Son importantes en las siguientes tareas:
Software para el diseño y verificación de circuitos digitales.
Construcción de analizadores léxicos de compiladores.
Software para analizar grandes conjuntos de textos parabuscar palabras, estructuras u otros patrones (p.e. páginasweb).
Software para comprobar la corrección de cualquier tipo desistemas que tengan un número finito de estados diferenes(p.e. protocolos de comunicación).
Modelos de Computación ITema 2: Autómatas Finitos– p.3/88
Ejemplo Introductorio
Vamos a diseñar un autómata que reconozca el paso de unalumno por una asignatura, por ejemplo, Modelos deComputación I.El alfabeto de entrada contendrá los siguientes elementos:
P: El alumno se presenta a un examen.
N: El alumno no se presenta a un examen.
A: El alumno aprueba un examen.
S: El alumno suspende un examen.
Modelos de Computación ITema 2: Autómatas Finitos– p.4/88
Ejemplo Introductorio
Inicio Febr.
Dec2
P
N
Modelos de Computación ITema 2: Autómatas Finitos– p.5/88
Ejemplo Introductorio
Inicio Febr.
Dec2
Fin1
Dec1P
NA
S
Modelos de Computación ITema 2: Autómatas Finitos– p.5/88
Ejemplo Introductorio
Inicio Febr.
Dec2
Fin1
Dec1
Sept1.
P
NA
SP
Modelos de Computación ITema 2: Autómatas Finitos– p.5/88
Ejemplo Introductorio
Inicio Febr.
Dec2
Fin1
Dec1
Sept1. Fin2
P
NA
SP
AS
Modelos de Computación ITema 2: Autómatas Finitos– p.5/88
Ejemplo Introductorio
Inicio Febr.
Dec2
Fin1
Dec1
Sept1. Fin2
Sept2.
Dec3
P
NA
SP
N
AS
N
P
Modelos de Computación ITema 2: Autómatas Finitos– p.5/88
Ejemplo Introductorio
Inicio Febr.
Dec2
Fin1
Dec1
Sept1. Fin2
Sept2.
Dec3
P
NA
SP
N
AS
N
P
A
S
Modelos de Computación ITema 2: Autómatas Finitos– p.5/88
Ejemplo Introductorio
Inicio Febr.
Dec2
Fin1
Dec1
Sept1. Fin2
Sept2.
Dec3
Dic.
P
NA
SP
N
AS
N
P
A
S
P
N
Modelos de Computación ITema 2: Autómatas Finitos– p.5/88
Ejemplo Introductorio
Inicio Febr.
Dec2
Fin1
Dec1
Sept1. Fin2
Sept2.
Dec3
Dic.Fin3
P
NA
SP
N
AS
N
P
A
S
P
A
N
S
Modelos de Computación ITema 2: Autómatas Finitos– p.5/88
AUTOMATA FINITO DETERMINISTA
Un autómata finito es una quintupla M = (Q,A,δ,q0,F) donde
Q es un conjunto finito llamado conjunto de estados
A es un alfabeto llamado alfabeto de entrada
δ es una aplicación llamada función de transición
δ : Q×A → Q
q0 es un elemento de Q, llamado estado inicial
F es un subconjunto de Q, llamado conjunto de estadosfinales.
Modelos de Computación ITema 2: Autómatas Finitos– p.6/88
Ejemplo
Sea el autómata M = (Q,A,q0,δ,F), donde
Q = {q0,q1,q2}
A = {a,b}
La función de transición viene dada por:
δ(q0,a) = q1, δ(q0,b) = q2,
δ(q1,a) = q1, δ(q1,b) = q2,
δ(q2,a) = q1, δ(q2,b) = q0
F = {q1}
Modelos de Computación ITema 2: Autómatas Finitos– p.7/88
Diagrama de Transición
Es un grafo en el que:
Hay un nodo por cada estado
Por cada transición δ(q,a) = p hay un arco de q a p con la etiqueta a.
El estado inicial está indicado con un ángulo entrante. Los estadosfinales están indicados con una doble circunferencia.
q0 q1
q2
a
b
bba
a
Modelos de Computación ITema 2: Autómatas Finitos– p.8/88
Cálculo Asociado. Traza
q0 q1
0
1
1 0
1 0 0
q0 q1
1 0 0
q0 q1
1 0 0
q0 q1
1 0 0
q0 q1Estado finalSI
Modelos de Computación ITema 2: Autómatas Finitos– p.9/88
Cálculo Asociado. Traza
q0 q1
0
1
1 0
1 0 0
q0 q1
�
1 0 0
q0 q1
1 0 0
q0 q1
1 0 0
q0 q1Estado finalSI
Modelos de Computación ITema 2: Autómatas Finitos– p.9/88
Cálculo Asociado. Traza
q0 q1
0
1
1 0
1 0 0
q0 q1
�
1 0 0
q0 q1
�
1 0 0
q0 q1
1 0 0
q0 q1Estado finalSI
Modelos de Computación ITema 2: Autómatas Finitos– p.9/88
Cálculo Asociado. Traza
q0 q1
0
1
1 0
1 0 0
q0 q1
�
1 0 0
q0 q1
�
1 0 0
q0 q1
�
1 0 0
q0 q1Estado finalSI
Modelos de Computación ITema 2: Autómatas Finitos– p.9/88
Cálculo Asociado. Traza
q0 q1
0
1
1 0
1 0 0
q0 q1
�
1 0 0
q0 q1
�
1 0 0
q0 q1
�
1 0 0
q0 q1
Estado finalSI
Modelos de Computación ITema 2: Autómatas Finitos– p.9/88
PROCESO DE CALCULOAutómata M = (Q,A,δ,q0,F)
Descripción Instantánea o Configuración:Un elemento de Q×A∗: (q,u).
Configuración Inicial para u ∈ A∗: (q0,u)
Relación paso de cálculo entre dos configuraciones:
((q,au) ` (p,u)) ⇔ δ(q,a) = p)
De una configuración sólo se puede pasar a lo máximo auna configuración en un paso de cálculo.
Modelos de Computación ITema 2: Autómatas Finitos– p.10/88
Proceso de Cálculo
Relación de cálculo entre dos configuraciones:
((q,u)∗
` (p,v)) si y solo si existe una sucesión deconfiguraciones C0, . . . ,Cn tales que C0 = (q,u),Cn = (p,v) y∀i ≤ n−1,Ci `Ci+1.
Lenguaje Aceptado por un Autómata Finito
L(M) = {u ∈ A∗ : (q0,u)∗
` (q,ε),q ∈ F}
Las palabras de L(M) se dicen aceptadas por el autómata.
Modelos de Computación ITema 2: Autómatas Finitos– p.11/88
Ejemplo. Cálculo Asociado
q0 q1
(100,q0) ` (00,q0) ` (0,q1) ` (ε,q1)
(100,q0)∗
` (ε,q1), 100 aceptada
0
1
1 0
1 0 0
q0 q1
1 0 0
q0 q1
�
1 0 0
q0 q1
�
1 0 0
q0 q1
Estado finalSI
Modelos de Computación ITema 2: Autómatas Finitos– p.12/88
Ejemplo
q0 q1
1
1
0 0
Acepta el conjunto de palabras con un número impar de 1.
Modelos de Computación ITema 2: Autómatas Finitos– p.13/88
Ejemplo
q0 q1
1
1
0 0
Acepta el conjunto de palabras con un número impar de 1.
Modelos de Computación ITema 2: Autómatas Finitos– p.13/88
Comunicaciones Correctas
R RF
E RD
S
B
HZB,D,Z,H
B,H,S
S,Z,D
B,D,Z,H,S D
R: Estado de espera RF: Estado de recepción de ficheros
RD: Recepción de datos E: Error
S: Comienza recepción B: Fin de recepciónH: Cabecera de fichero Z: Fin de ficheroD: Datos
Modelos de Computación ITema 2: Autómatas Finitos– p.14/88
Constantes Reales
Gramática G = (V,T,P,S), donde
T = {+,−,E,0,1, . . . .,9, .}
V = {< Signo >,< Digito >,< Natural >,< Entero >,< Real >}
S =< Real >
P contiene las siguientes producciones
< Signo >→ +|−
< Digito >→ 0|1|2|3|4|5|6|7|8|9
<Natural>→<Digito> | <Digito><Natural>
<Entero>→<Natural> | <Signo><Natural>
<Real>→<Entero> | <Entero>.
<Real>→<Entero> . <Natural>
<Real>→<Entero> . <Natural> E <Entero>
Modelos de Computación ITema 2: Autómatas Finitos– p.15/88
Autómata FinitoT es el conjunto de los símbolos terminales.
q0
q2
q1
q3
q8
q4
q5
q6
q7
+,−
0, . . . ,9
0, . . . ,9
. 0, . . . ,9E
0, . . . ,9
+,−
0, . . . ,9
E,+,−, .
E,+,−, .
0, . . . ,9 0, . . . ,9 0, . . . ,9
T
+,−, .E,+,−
E, .
E,+,−, .
E,+,−, .
E, .
Modelos de Computación ITema 2: Autómatas Finitos– p.16/88
Autómatas Finitos No Deterministas
Un autómata finito no determista es una quintuplaM = (Q,A,δ,q0,F) en la que
Q es un conjunto finito llamado conjunto de estados
A es un alfabeto llamado alfabeto de entrada
δ es una aplicación llamada función de transición
δ : Q×A →℘(Q)
q0 es un elemento de Q, llamado estado inicial
F es un subconjunto de Q, llamado conjunto de estadosfinales.
Modelos de Computación ITema 2: Autómatas Finitos– p.17/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
Se pueden usar también diagramas de transición.
Puede haber estados que para una entrada tenga dostransiciones. Por ejemplo, q0 cuando lee 0 puede quedarse en q0
o pasar a q1.
También puede haber estados que para una entrada no tenganninguna transición: desde q1 no se puede leer el 0.
Acepta el conjunto de las palabras que tienen a 010010 comosubcadena: palabras que se pueden leer pasando de q0 a unestado final.
Modelos de Computación ITema 2: Autómatas Finitos– p.18/88
EjemplosTambién es no-determinista:
r0 r1 r2a c
b
Acepta cadenas formadas por una a, una sucesión de b y una c.
Se puede transformar en uno determinista que acepte el mismolenguaje añadiéndole un estado de error donde vayan todas lastransiciones no definidas en el autómata anterior:
r0 r1 r2
r3
a c
b,ca
a,b,c
b
a,b,c
Modelos de Computación ITema 2: Autómatas Finitos– p.19/88
EjemplosTambién es no-determinista:
r0 r1 r2a c
b
Acepta cadenas formadas por una a, una sucesión de b y una c.Se puede transformar en uno determinista que acepte el mismolenguaje añadiéndole un estado de error donde vayan todas lastransiciones no definidas en el autómata anterior:
r0 r1 r2
r3
a c
b,ca
a,b,c
b
a,b,c Modelos de Computación ITema 2: Autómatas Finitos– p.19/88
Ejemplo: Constantes realesAutómata determinista:
q0
q2
q1
q3
q8
q4
q5
q6
q7
+,−
0, . . . ,9
0, . . . ,9
. 0, . . . ,9E
0, . . . ,9
+,−
0, . . . ,9
E,+,−, .
E,+,−, .
0, . . . ,9 0, . . . ,9 0, . . . ,9
T
+,−, .E,+,−
E, .
E,+,−, .
E,+,−, .
E, .
Modelos de Computación ITema 2: Autómatas Finitos– p.20/88
Ejemplo: Constantes realesAutómata no determinista:
q0
q2
q1
q3
q8
q4
q5
q6
+,−
0, . . . ,9
0, . . . ,9
. 0, . . . ,9E
0, . . . ,9
+,−
0, . . . ,9
0, . . . ,9 0, . . . ,9 0, . . . ,9
Modelos de Computación ITema 2: Autómatas Finitos– p.21/88
PROCESO DE CALCULOAutómata no determinista M = (Q,A,δ,q0,F)
Descripción Instantánea o Configuración:Un elemento de Q×A∗: (q,u).
Configuración Inicial para u ∈ A∗: (q0,u)
Relación paso de cálculo entre dos configuraciones:
((q,au) ` (p,v)) ⇔ p ∈ δ(q,a))
De una configuración se puede pasar a variasconfiguraciones distintas en un paso de cálculo, e incluso aninguna.
Modelos de Computación ITema 2: Autómatas Finitos– p.22/88
Proceso de Cálculo
Relación de cálculo entre dos configuraciones:
((q,u)∗
` (p,v)) si y solo si existe una sucesión deconfiguraciones C0, . . . ,Cn tales que C0 = (q,u),Cn = (p,v) y∀i ≤ n−1,Ci `Ci+1.
Lenguaje Aceptado por un AF no-determinista
L(M) = {u ∈ A∗ : ∃q ∈ F,(q0,u)∗
` (q,ε)}
Las palabras de L(M) se dicen aceptadas por el autómata.
Modelos de Computación ITema 2: Autómatas Finitos– p.23/88
Definiciones
Dado un autómata M = (Q,A,δ,q0,F), definimos
Si B ⊆ Q,δ∗(B,a) =
⋃
q∈B
δ(q,a)
Si B ⊆ Q,
δ∗(B,ε) = B
δ∗(B,au) = δ∗(δ∗(B,a),u)
δ∗(q,u) = δ∗({q},u)
δ∗(B,u) es igual a todos los estados a los que se puede llegar desdecualquiera de los estados de B después de leer la palabra u.
Modelos de Computación ITema 2: Autómatas Finitos– p.24/88
Equivalencia Aut. Deterministas ↔ No-Determistas
Podemos considerar que todos los autómatasdeterministas son también autómatas no-deterministas, enlos que δ(q,a) tiene siempre un y sólo un estado.
Así, todo lenguaje L aceptado por un autómata deterministaes aceptado también por un autómata no-determinista (élmismo).
Con los autómatas no-deterministas no aceptamos máslenguajes que con los deterministas: todo lenguajeaceptado por un autómata no-determinista lo será tambiénpor uno determinista (lo veremos a continuación).
Con los autómatas no-deterministas no ampliamos lafamilia de lenguajes aceptados por los autómtasdeterministas. Simplemente, tenemos más opciones pararepresentar un lenguaje. Modelos de Computación ITema 2: Autómatas Finitos– p.25/88
Aut. No Determinista → Aut. Determinista
Dado un AFND M = (Q,A,δ,q0,F) se llama autómata deterministaasociado a M, al autómata M̄ = (Q̄,A, δ̄, q̄0, F̄) dado por
Q̄ =℘(Q)
q̄0 = {q0}
δ̄(B,a) = δ∗(B,a) =⋃
q∈B δ(q,a)
F̄ = {B ∈℘(Q) | B∩F 6= /0}
Dado un autómata no determinista se le hace corresponder unodeterminista que recorre todos los caminos al mismo tiempo.
Un autómata no-determinista y su determinista asociado aceptan elmismo lenguaje
Modelos de Computación ITema 2: Autómatas Finitos– p.26/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0}
{q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1}
{q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0
1
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1}
{q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0
1 0
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2}
{q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1
1 0
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 01 0
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 01 0
1
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5}
{q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5}
{q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
01
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5}
{q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
001
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
01
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6}
{q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
01
0
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6}
{q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6}
{q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
0
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6}
{q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6}
{q0,q2,q6}
0 1 0
0
1
011
0
10
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6}
{q0,q2,q6}
0 1 0
0
1
011
0
100
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6}
{q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
10
10
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6}
{q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
100
10
1 01
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
100
10
1 01
1
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
100
10
1 0
0
1
1
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
100
10
1 0
0
1
1
1
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
100
1 00
1 0
0
1
1
1
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
100
1 0
1
0
1 0
0
1
1
1
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
100
1 0
1
00
1 0
0
1
1
1
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
Ejemplo
q0 q1 q2 q3 q4 q5 q60 1 0 0 1 0
0,1 0,1
{q0} {q0,q1} {q0,q2} {q0,q1,q3}
{q0,q2,q5} {q0,q1,q4}
{q0,q1,q6} {q0,q1,q4,q6} {q0,q1,q3,q6}
{q0,q6} {q0,q2,q5,q6} {q0,q2,q6}
0 1 0
0
1
011
0
100
1 0
1
00
1 0
0
1
1
1
1
Modelos de Computación ITema 2: Autómatas Finitos– p.27/88
AF No Deterministas con Transiciones Nulas
Un autómata finito no determinista con transiciones nulas es una quintuplaM = (Q,A,δ,q0,F) en la que
Q es un conjunto finito llamado conjunto de estados
A es un alfabeto llamado alfabeto de entrada
δ es una aplicación llamada función de transición
δ : Q× (A∪{ε}) →℘(Q)
q0 es un elemento de Q, llamado estado inicial
F es un subconjunto de Q, llamado conjunto de estados finales.
Modelos de Computación ITema 2: Autómatas Finitos– p.28/88
Opciones
q j qk qs
qi ql qm qn
qr qt qw
a
a
ε
ε
a
ε ε
ε
ε
Desde el estado qi se puede llegar a los estados:q j,qk,qs,qm,qn,qt ,qw después de leer una a.
Modelos de Computación ITema 2: Autómatas Finitos– p.29/88
Ejemplo
q0 q1 q2ε ε
0 1 2
El lenguaje aceptado es L = {0i1 j2k : i, j,k ≥ 0}.
Modelos de Computación ITema 2: Autómatas Finitos– p.30/88
Ejemplo
q0 q1 q2ε ε
0 1 2
El lenguaje aceptado es L = {0i1 j2k : i, j,k ≥ 0}.
Modelos de Computación ITema 2: Autómatas Finitos– p.30/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
El lenguaje generado es L = {aib2 jck : i,k = 0,1 y j ≥ 0}.
Modelos de Computación ITema 2: Autómatas Finitos– p.31/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
El lenguaje generado es L = {aib2 jck : i,k = 0,1 y j ≥ 0}.
Modelos de Computación ITema 2: Autómatas Finitos– p.31/88
Utilidad
Conjunto de palabras que tienen a 0110 o a 1000 como subcadena.
q0 q1 q2 q3 q4
r0
p0 p1 p2 p3 p4
0,1 0,1
0,1 0,1
0 1 1 0
1 0 0 0
Modelos de Computación ITema 2: Autómatas Finitos– p.32/88
Utilidad
Conjunto de palabras que tienen a 0110 o a 1000 como subcadena.
q0 q1 q2 q3 q4
r0
p0 p1 p2 p3 p4
0,1 0,1
0,1 0,1
0 1 1 0
1 0 0 0
Modelos de Computación ITema 2: Autómatas Finitos– p.32/88
Utilidad
Conjunto de palabras que tienen a 0110 o a 1000 como subcadena.
q0 q1 q2 q3 q4
r0
p0 p1 p2 p3 p4
0,1 0,1
0,1 0,1
0 1 1 0
1 0 0 0
ε
ε
Modelos de Computación ITema 2: Autómatas Finitos– p.32/88
PROCESO DE CALCULOPara un Autómata Finito con Transiciones NulasM = (Q,A,δ,q0,F)
Descripción Instantánea o Configuración:Un elemento de Q×A∗: (q,u).
Configuración Inicial para u ∈ A∗: (q0,u)
Relación paso de cálculo entre dos configuraciones:((q,u) ` (p,v)) si y solo si se da una de las condiciones
((u = av)∧ p ∈ δ(q,a)) (caso: ((q,av) ` (p,v)))((u = v)∧ p ∈ δ(q,ε)) (caso: ((q,v) ` (p,v)))
De una configuración se puede pasar a variasconfiguraciones distintas en un paso de cálculo, e incluso aninguna.
Modelos de Computación ITema 2: Autómatas Finitos– p.33/88
Proceso de Cálculo
Relación de cálculo entre dos configuraciones:
((q,u)∗
` (p,v)) si y solo si existe una sucesión deconfiguraciones C0, . . . ,Cn tales que C0 = (q,u),Cn = (p,v) y∀i ≤ n−1,Ci `Ci+1.
Lenguaje Aceptado por un ε-AF no-determinista
L(M) = {u ∈ A∗ : ∃q ∈ F,(q0,u)∗
` (q,ε)}
Las palabras de L(M) se dicen aceptadas por el autómata.
Modelos de Computación ITema 2: Autómatas Finitos– p.34/88
AFD ↔ ε-AFND
Dado un autómata finito determinista M existe un autómatano determinista con transiciones nulas M que acepta elmismo lenguaje: L(M) = L(M)Es inmediato: sería un autómata en el que para cadasímbolo del alfabeto de entrada hay siempre una opción ypara cada estado δ(q,ε) = /0.
Dado un autómata finito no determinista con transicionesnulas M existe un autómata finito determinista M queacepta el mismo lenguaje: L(M) = L(M)
Modelos de Computación ITema 2: Autómatas Finitos– p.35/88
AFD ↔ ε-AFND
Dado un autómata finito determinista M existe un autómatano determinista con transiciones nulas M que acepta elmismo lenguaje: L(M) = L(M)Es inmediato: sería un autómata en el que para cadasímbolo del alfabeto de entrada hay siempre una opción ypara cada estado δ(q,ε) = /0.
Dado un autómata finito no determinista con transicionesnulas M existe un autómata finito determinista M queacepta el mismo lenguaje: L(M) = L(M)
Modelos de Computación ITema 2: Autómatas Finitos– p.35/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2}
{q1,q2}
{q2} /0
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2}
{q1,q2}
{q2} /0
0
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2} {q1,q2}
{q2} /0
1
0
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2} {q1,q2}
{q2}
/0
1
2
0
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2} {q1,q2}
{q2} /0
1
2 0
0
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2} {q1,q2}
{q2} /0
1
2 0
0 1
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2} {q1,q2}
{q2} /0
1
2 02
0 1
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2} {q1,q2}
{q2} /0
1
2 020,1
0 1
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2} {q1,q2}
{q2} /0
1
2 020,1
0 1
2
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2} {q1,q2}
{q2} /0
1
2 020,1
0 1
2 0,1,2
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
Ejemplo
q0 q1 q2ε ε
0 1 2
{q0,q1,q2} {q1,q2}
{q2} /0
1
2 020,1
0 1
2 0,1,2
Modelos de Computación ITema 2: Autómatas Finitos– p.36/88
ε-AFND → autómata determinista
Dado M = (Q,A,δ,q0,F) se define:Clasura de un estado:
Cl(q)= {p : ∃p1, . . . , pn, p1 = q,qn = p, pi ∈ δ(pi−1,ε) (i = 2, . . . ,n)}
Clasura de un conjunto de estados: Cl(P) =⋃
q∈PCl(q)
Autómata Finito Determinista M = (Q,A,δ,q0,F)
Q =℘(Q)
δ(P,a) = Cl(⋃
q∈P δ(q,a))
q0 = Cl(q0)
F = {P : P∩F 6= /0}Modelos de Computación ITema 2: Autómatas Finitos– p.37/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2}
{q3}
{q1,q2} {q2} /0
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2}
{q3}
{q1,q2}
{q2} /0
a
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2} {q3}
{q1,q2}
{q2} /0
a
b
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2} {q3}
{q1,q2} {q2}
/0
a
b
c
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2} {q3}
{q1,q2} {q2} /0
a
b
c
a
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2} {q3}
{q1,q2} {q2} /0
a
b
c
a
b
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2} {q3}
{q1,q2} {q2} /0
a
b
c
c
a
b
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2} {q3}
{q1,q2} {q2} /0
a
b
c
c
a,c
a
b
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2} {q3}
{q1,q2} {q2} /0
a
b
c
c
a,c
a
bb
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2} {q3}
{q1,q2} {q2} /0
a
b
c
c
a,c
a,b,c
a
bb
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
Ejemplo
q0 q1 q2
q3
b b
a,ε c,ε
{q0,q1,q2} {q3}
{q1,q2} {q2} /0
a
b
c
c
a,c
a,b,c
a
bb
a,b,c
Modelos de Computación ITema 2: Autómatas Finitos– p.38/88
EXPRESIONES REGULARES
Si A es un alfabeto, una expresión regular sobre este alfabeto se define de lasiguiente forma:
/0 es una expresión regular que denota el lenguaje vacío.
ε es una expresión regular que denota el lenguaje {ε}.
Si a ∈ A, a es una expresión regular que denota el lenguaje {a}
Si r y s son expresiones regulares denotando los lenguajes R y Sentonces definimos las siguientes operaciones:
Unión: (r+ s) es una expresión regular que denota el lenguaje R∪S.
Concatenación: (rs) es una expresión regular que denota el lenguajeRS.
Clausura: r∗ es una expresión regular que denota el lenguaje R∗.
Modelos de Computación ITema 2: Autómatas Finitos– p.39/88
Ejemplos
A = {0,1}
00
El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen
una sucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidos
siempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguida
de una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienenuna sucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0
Conjunto de palabras que empiezan por 0 y después tienenuna sucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗
Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011
Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗
Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗
Conjunto de palabras formadas por una sucesión de ceros
seguida de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros seguida
de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos
A = {0,1}00 El conjunto {00}
01∗ +0 Conjunto de palabras que empiezan por 0 y después tienen unasucesión de unos.
(1+10)∗ Conjunto de palabras en las que los ceros están precedidossiempre por unos
(0+1)∗011 Conjunto de palabras que terminan en 011
0∗1∗ Conjunto de palabras formadas por una sucesión de ceros seguidade una suceción de unos. Ambas sucesiones pueden ser vacías
00∗11∗ Conjunto de palabras formadas por una sucesión de ceros seguida
de una suceción de unos. Niguna de las sucesiones puede ser vacía
A r∗r se le denota como r+. La última expresión regular quedaría 0+1+
Modelos de Computación ITema 2: Autómatas Finitos– p.40/88
Ejemplos - Alfabeto {0,1}Construir una expresión regular para las palabras con un número par deceros.
1∗ (01∗01∗)∗
Construir una expresión regular para las palabras que contengan a 0110como subcadena.
(0+1)∗0110(0+1)∗
Construir una expresión regular para el conjunto de palabras que empiezanpor 000 y después no aparece nunca más esta cadena.
(000)(1+10+100)∗
Construir una expresión regular para el conjunto de palabras que tienen a000 o a 101 como subcadena
(0+1)∗(000+101)(0+1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.41/88
Ejemplos - Alfabeto {0,1}Construir una expresión regular para las palabras con un número par deceros.
1∗ (01∗01∗)∗
Construir una expresión regular para las palabras que contengan a 0110como subcadena.
(0+1)∗0110(0+1)∗
Construir una expresión regular para el conjunto de palabras que empiezanpor 000 y después no aparece nunca más esta cadena.
(000)(1+10+100)∗
Construir una expresión regular para el conjunto de palabras que tienen a000 o a 101 como subcadena
(0+1)∗(000+101)(0+1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.41/88
Ejemplos - Alfabeto {0,1}Construir una expresión regular para las palabras con un número par deceros.
1∗ (01∗01∗)∗
Construir una expresión regular para las palabras que contengan a 0110como subcadena.
(0+1)∗0110(0+1)∗
Construir una expresión regular para el conjunto de palabras que empiezanpor 000 y después no aparece nunca más esta cadena.
(000)(1+10+100)∗
Construir una expresión regular para el conjunto de palabras que tienen a000 o a 101 como subcadena
(0+1)∗(000+101)(0+1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.41/88
Ejemplos - Alfabeto {0,1}Construir una expresión regular para las palabras con un número par deceros.
1∗ (01∗01∗)∗
Construir una expresión regular para las palabras que contengan a 0110como subcadena.
(0+1)∗0110(0+1)∗
Construir una expresión regular para el conjunto de palabras que empiezanpor 000 y después no aparece nunca más esta cadena.
(000)(1+10+100)∗
Construir una expresión regular para el conjunto de palabras que tienen a000 o a 101 como subcadena
(0+1)∗(000+101)(0+1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.41/88
Ejemplos - Alfabeto {0,1}Construir una expresión regular para las palabras con un número par deceros.
1∗ (01∗01∗)∗
Construir una expresión regular para las palabras que contengan a 0110como subcadena.
(0+1)∗0110(0+1)∗
Construir una expresión regular para el conjunto de palabras que empiezanpor 000 y después no aparece nunca más esta cadena.
(000)(1+10+100)∗
Construir una expresión regular para el conjunto de palabras que tienen a000 o a 101 como subcadena
(0+1)∗(000+101)(0+1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.41/88
Ejemplos - Alfabeto {0,1}Construir una expresión regular para las palabras con un número par deceros.
1∗ (01∗01∗)∗
Construir una expresión regular para las palabras que contengan a 0110como subcadena.
(0+1)∗0110(0+1)∗
Construir una expresión regular para el conjunto de palabras que empiezanpor 000 y después no aparece nunca más esta cadena.
(000)(1+10+100)∗
Construir una expresión regular para el conjunto de palabras que tienen a000 o a 101 como subcadena
(0+1)∗(000+101)(0+1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.41/88
Ejemplos - Alfabeto {0,1}Construir una expresión regular para las palabras con un número par deceros.
1∗ (01∗01∗)∗
Construir una expresión regular para las palabras que contengan a 0110como subcadena.
(0+1)∗0110(0+1)∗
Construir una expresión regular para el conjunto de palabras que empiezanpor 000 y después no aparece nunca más esta cadena.
(000)(1+10+100)∗
Construir una expresión regular para el conjunto de palabras que tienen a000 o a 101 como subcadena
(0+1)∗(000+101)(0+1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.41/88
Ejemplos - Alfabeto {0,1}Construir una expresión regular para las palabras con un número par deceros.
1∗ (01∗01∗)∗
Construir una expresión regular para las palabras que contengan a 0110como subcadena.
(0+1)∗0110(0+1)∗
Construir una expresión regular para el conjunto de palabras que empiezanpor 000 y después no aparece nunca más esta cadena.
(000)(1+10+100)∗
Construir una expresión regular para el conjunto de palabras que tienen a000 o a 101 como subcadena
(0+1)∗(000+101)(0+1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.41/88
Propiedades de las Expresiones Regulares
1. r1 + r2 = r2 + r1
2. r1 +(r2 + r3) = (r1 + r2)+ r3
3. r1(r2r3) = (r1r2)r3
4. rε = r
5. r /0 = /0
6. r+ /0 = r
7. ε∗ = ε
8. r1(r2 + r3) = r1r2 + r1r3
9. (r1 + r2)r3 = r1r3 + r2r3
10. r+ + ε = r∗
11. r∗ + ε = r∗
12. (r+ ε)∗ = r∗
13. (r+ ε)+ = r∗
14. (r∗1 + r∗2)∗ = (r1 + r2)
∗
15. (r∗1r∗2)∗ = (r1 + r2)
∗
Modelos de Computación ITema 2: Autómatas Finitos– p.42/88
Equivalencia Autómatas - Expresiones Regulares
La familia de los lenguajes aceptados por los autómatasfinitos coincide con la familia de lenguajes que puedenrepresentarse mediante expresiones regulares.
Esto se demostrará comprobando:
Dada una expresión regular, existe un autómata queacepta el mismo lenguaje que el representado por laexpresión regular.Dado un autómata finito existe siempre una expresiónregular que representa el lenguaje aceptado por elautómata.
La primera transformación es más útil, ya que inicialmentelos lenguajes se representan mediante expresionesregulares y después necesitamos algoritmos (autómatas)que reconozcan estos lenguajes. Modelos de Computación ITema 2: Autómatas Finitos– p.43/88
Expresión Regular → Autómata
Dada una expresión regular existe un audómata finito que acepta el lenguajeasociado a esta expresión regular.
Vamos a demostrar que existe un AFND con transiciones nulas. A partir de él se
podría construir el autómata determinista asociado.
La construcción del autómata va a ser recursiva.
Para las expresiones regulares iniciales tenemos los siguiente autómatas:
/0 q0
ε q0
a q0 q1a
Modelos de Computación ITema 2: Autómatas Finitos– p.44/88
Expresión Regular → Autómata
Dada una expresión regular existe un audómata finito que acepta el lenguajeasociado a esta expresión regular.
Vamos a demostrar que existe un AFND con transiciones nulas. A partir de él sepodría construir el autómata determinista asociado.
La construcción del autómata va a ser recursiva.
Para las expresiones regulares iniciales tenemos los siguiente autómatas:
/0 q0
ε q0
a q0 q1a
Modelos de Computación ITema 2: Autómatas Finitos– p.44/88
Expresión Regular → Autómata
Dada una expresión regular existe un audómata finito que acepta el lenguajeasociado a esta expresión regular.
Vamos a demostrar que existe un AFND con transiciones nulas. A partir de él sepodría construir el autómata determinista asociado.
La construcción del autómata va a ser recursiva.
Para las expresiones regulares iniciales tenemos los siguiente autómatas:
/0
q0
ε q0
a q0 q1a
Modelos de Computación ITema 2: Autómatas Finitos– p.44/88
Expresión Regular → Autómata
Dada una expresión regular existe un audómata finito que acepta el lenguajeasociado a esta expresión regular.
Vamos a demostrar que existe un AFND con transiciones nulas. A partir de él sepodría construir el autómata determinista asociado.
La construcción del autómata va a ser recursiva.
Para las expresiones regulares iniciales tenemos los siguiente autómatas:
/0 q0
ε q0
a q0 q1a
Modelos de Computación ITema 2: Autómatas Finitos– p.44/88
Expresión Regular → Autómata
Dada una expresión regular existe un audómata finito que acepta el lenguajeasociado a esta expresión regular.
Vamos a demostrar que existe un AFND con transiciones nulas. A partir de él sepodría construir el autómata determinista asociado.
La construcción del autómata va a ser recursiva.
Para las expresiones regulares iniciales tenemos los siguiente autómatas:
/0 q0
ε
q0
a q0 q1a
Modelos de Computación ITema 2: Autómatas Finitos– p.44/88
Expresión Regular → Autómata
Dada una expresión regular existe un audómata finito que acepta el lenguajeasociado a esta expresión regular.
Vamos a demostrar que existe un AFND con transiciones nulas. A partir de él sepodría construir el autómata determinista asociado.
La construcción del autómata va a ser recursiva.
Para las expresiones regulares iniciales tenemos los siguiente autómatas:
/0 q0
ε q0
a q0 q1a
Modelos de Computación ITema 2: Autómatas Finitos– p.44/88
Expresión Regular → Autómata
Dada una expresión regular existe un audómata finito que acepta el lenguajeasociado a esta expresión regular.
Vamos a demostrar que existe un AFND con transiciones nulas. A partir de él sepodría construir el autómata determinista asociado.
La construcción del autómata va a ser recursiva.
Para las expresiones regulares iniciales tenemos los siguiente autómatas:
/0 q0
ε q0
a
q0 q1a
Modelos de Computación ITema 2: Autómatas Finitos– p.44/88
Expresión Regular → Autómata
Dada una expresión regular existe un audómata finito que acepta el lenguajeasociado a esta expresión regular.
Vamos a demostrar que existe un AFND con transiciones nulas. A partir de él sepodría construir el autómata determinista asociado.
La construcción del autómata va a ser recursiva.
Para las expresiones regulares iniciales tenemos los siguiente autómatas:
/0 q0
ε q0
a q0 q1a
Modelos de Computación ITema 2: Autómatas Finitos– p.44/88
Autómatas Compuestos: UniónSi M1 es el autómata que acepta el mismo lenguaje que elrepresentado por r1 y M2 el que acepta el mismo lenguaje que el der2, entonces
Unión (r1 + r2)
M1
M2
q01
q11
qi1
q02
q12
q j2
Modelos de Computación ITema 2: Autómatas Finitos– p.45/88
Autómatas Compuestos: UniónSi M1 es el autómata que acepta el mismo lenguaje que elrepresentado por r1 y M2 el que acepta el mismo lenguaje que el der2, entonces
Unión (r1 + r2)
q0
M1
M2
q01
q11
qi1
q02
q12
q j2
Modelos de Computación ITema 2: Autómatas Finitos– p.45/88
Autómatas Compuestos: UniónSi M1 es el autómata que acepta el mismo lenguaje que elrepresentado por r1 y M2 el que acepta el mismo lenguaje que el der2, entonces
Unión (r1 + r2)
q0
M1
M2
q01
q11
qi1
q02
q12
q j2
ε
ε
Modelos de Computación ITema 2: Autómatas Finitos– p.45/88
Unión: Expresión Matemática
En lenguaje matemático, la unión se puede expresar de lasiguiente forma. Si M1 = (Q1,A,δ1,q1
0,F1) y M2 = (Q2,A,δ2,q20,F2)
con Q1 ∩Q2 = /0, entonces el autómata que acepta la unión esM = (Q,A,δ,q0,F) donde
Q = Q1 ∪Q2 ∪{q0},donde q0 6∈ (Q1 ∪Q2) es un nuevo estado.
δ viene definida porδ(q,a) = δ1(q,a) si q ∈ Q1
δ(q,a) = δ2(q,a) si q ∈ Q2
δ(q0,a) = /0 si a ∈ Aδ(q0,ε) = {q1
0,q20}
F = F1 ∪F2
Modelos de Computación ITema 2: Autómatas Finitos– p.46/88
Unión: Expresión Matemática
En lenguaje matemático, la unión se puede expresar de lasiguiente forma. Si M1 = (Q1,A,δ1,q1
0,F1) y M2 = (Q2,A,δ2,q20,F2)
con Q1 ∩Q2 = /0, entonces el autómata que acepta la unión esM = (Q,A,δ,q0,F) donde
Q = Q1 ∪Q2 ∪{q0},donde q0 6∈ (Q1 ∪Q2) es un nuevo estado.
δ viene definida porδ(q,a) = δ1(q,a) si q ∈ Q1
δ(q,a) = δ2(q,a) si q ∈ Q2
δ(q0,a) = /0 si a ∈ Aδ(q0,ε) = {q1
0,q20}
F = F1 ∪F2Modelos de Computación ITema 2: Autómatas Finitos– p.46/88
Autómatas Compuestos: Concatenación
Concatenación:El autómata para la expresión (r1r2) es
M1 M2
q01 q02
q11
qi1
q12
q j2
Modelos de Computación ITema 2: Autómatas Finitos– p.47/88
Autómatas Compuestos: Concatenación
Concatenación:El autómata para la expresión (r1r2) es
M1 M2
q01 q02
q11
qi1
q12
q j2
Modelos de Computación ITema 2: Autómatas Finitos– p.48/88
Autómatas Compuestos: Concatenación
Concatenación:El autómata para la expresión (r1r2) es
M1 M2
q01 q02
q11
qi1
q12
q j2
εε
Modelos de Computación ITema 2: Autómatas Finitos– p.48/88
Concatenación: Expresión Matemática
En lenguaje matemático, la concatenación se puede expresarde la siguiente forma. Si M1 = (Q1,A,δ1,q1
0,F1) yM2 = (Q2,A,δ2,q2
0,F2) con Q1 ∩Q2 = /0, entonces el autómata queacepta la concatenación es M = (Q,A,δ,q0,F) donde:
Q = Q1 ∪Q2.
δ viene definida porδ(q,a) = δ1(q,a) si q ∈ Q1 −F1
δ(q,a) = δ1(q,a) si q ∈ F1,a ∈ Aδ(q,ε) = δ1(q,ε)∪{q2
0} si q ∈ F1
δ(q,a) = δ2(q,a) si q ∈ Q2
q0 = q10
F = F2
Modelos de Computación ITema 2: Autómatas Finitos– p.49/88
Concatenación: Expresión Matemática
En lenguaje matemático, la concatenación se puede expresarde la siguiente forma. Si M1 = (Q1,A,δ1,q1
0,F1) yM2 = (Q2,A,δ2,q2
0,F2) con Q1 ∩Q2 = /0, entonces el autómata queacepta la concatenación es M = (Q,A,δ,q0,F) donde:
Q = Q1 ∪Q2.
δ viene definida porδ(q,a) = δ1(q,a) si q ∈ Q1 −F1
δ(q,a) = δ1(q,a) si q ∈ F1,a ∈ Aδ(q,ε) = δ1(q,ε)∪{q2
0} si q ∈ F1
δ(q,a) = δ2(q,a) si q ∈ Q2
q0 = q10
F = F2 Modelos de Computación ITema 2: Autómatas Finitos– p.49/88
Autómatas Compuestos: Clausura
Clausura: El autómata para r∗1 es
M1q01
q11
qi1
Modelos de Computación ITema 2: Autómatas Finitos– p.50/88
Autómatas Compuestos: Clausura
Clausura: El autómata para r∗1 es
M1q01
q11
qi1
ε
ε
Modelos de Computación ITema 2: Autómatas Finitos– p.50/88
Autómatas Compuestos: Clausura
Clausura: El autómata para r∗1 es
M1q01
q11
qi1
q0ε
ε
ε
Modelos de Computación ITema 2: Autómatas Finitos– p.50/88
Clausura: Expresión Matemática
En lenguaje matemático: si M1 = (Q1,A,δ1,q10,F1), entonces el
autómata que acepta la clausura es M = (Q,A,δ,q0,F) donde:
Q = Q1 ∪{q0}, donde q0 6∈ Q1.
δ viene definida porδ(q,a) = δ1(q,a) si q ∈ Q1 −F1
δ(q,a) = δ1(q,a) si q ∈ F1,a ∈ Aδ(q,ε) = δ1(q,ε)∪{q0} si q ∈ F1
δ(q0,a) = /0 si a ∈ Aδ(q0,ε) = {q1
0}
q0
F = F1 ∪{q0}
Modelos de Computación ITema 2: Autómatas Finitos– p.51/88
Clausura: Expresión Matemática
En lenguaje matemático: si M1 = (Q1,A,δ1,q10,F1), entonces el
autómata que acepta la clausura es M = (Q,A,δ,q0,F) donde:
Q = Q1 ∪{q0}, donde q0 6∈ Q1.
δ viene definida porδ(q,a) = δ1(q,a) si q ∈ Q1 −F1
δ(q,a) = δ1(q,a) si q ∈ F1,a ∈ Aδ(q,ε) = δ1(q,ε)∪{q0} si q ∈ F1
δ(q0,a) = /0 si a ∈ Aδ(q0,ε) = {q1
0}
q0
F = F1 ∪{q0}
Modelos de Computación ITema 2: Autómatas Finitos– p.51/88
Ejemplo
Encontrar un autómata que acepte el mismo lenguaje que elasociado a la expresión regular (0+10)∗011
q1 q2 q3 q4
q5 q6
Modelos de Computación ITema 2: Autómatas Finitos– p.52/88
Ejemplo
Encontrar un autómata que acepte el mismo lenguaje que elasociado a la expresión regular (0+10)∗011
q1 q2
1
q3 q4
q5 q6
1
Modelos de Computación ITema 2: Autómatas Finitos– p.52/88
Ejemplo
Encontrar un autómata que acepte el mismo lenguaje que elasociado a la expresión regular (0+10)∗011
q1 q2
1q3 q4
0
q5 q6
1 0
Modelos de Computación ITema 2: Autómatas Finitos– p.52/88
Ejemplo
Encontrar un autómata que acepte el mismo lenguaje que elasociado a la expresión regular (0+10)∗011
q1
q2
q2 q3 q4
10
q5 q6
1 0ε
Modelos de Computación ITema 2: Autómatas Finitos– p.52/88
Ejemplo
Encontrar un autómata que acepte el mismo lenguaje que elasociado a la expresión regular (0+10)∗011
q1
q2
q2 q3 q4
10
q5 q6
0
1 0ε
0
Modelos de Computación ITema 2: Autómatas Finitos– p.52/88
Ejemplo
Encontrar un autómata que acepte el mismo lenguaje que elasociado a la expresión regular (0+10)∗011
q1
q2
q2 q3 q4
q5 q6
0+10
q7
1 0ε
0
ε
ε
Modelos de Computación ITema 2: Autómatas Finitos– p.52/88
Ejemplo
Encontrar un autómata que acepte el mismo lenguaje que elasociado a la expresión regular (0+10)∗011
q1
q2
q2 q3 q4
q5 q6
(0+10)∗
q7q8
1 0ε
0
ε
ε
ε
ε
ε
Modelos de Computación ITema 2: Autómatas Finitos– p.52/88
Ejemplo
Encontrar un autómata que acepte el mismo lenguaje que elasociado a la expresión regular (0+10)∗011
q1
q2
q2 q3 q4
q5 q6
(0+10)∗
q7q8 q9 q10 q11 q12 q13 q14
0111 0ε
0
ε
ε
ε 0 ε 11 ε
ε
ε
Modelos de Computación ITema 2: Autómatas Finitos– p.52/88
Ejemplo
Encontrar un autómata que acepte el mismo lenguaje que elasociado a la expresión regular (0+10)∗011
q1
q2
q2 q3 q4
q5 q6
q7q8 q9 q10 q11 q12 q13 q14
(0+10)∗011
Autómata Resultado
1 0ε
0
ε
ε
ε 0 ε 11 εε
ε
ε
εε
Modelos de Computación ITema 2: Autómatas Finitos– p.52/88
Autómata → Expresión RegularSi L es aceptado por un autómata finito determinista, entoncespuede venir expresado mediante una expresión regular.
Sea el autómata M = (Q,A,δ,q1,F), Q = {q1, . . . ,qn} y q1 es elestado inicial.Sea Rk
i j el conjunto de las cadenas de A∗ que premiten pasar delestado qi al estado q j y no pasa por ningún estado intermediode numeración mayor que k (qi y q j si pueden tener numeraciónmayor que k).Rk
i j se puede definir de forma recursiva:
R0i j =
{
{a : δ(qi,a) = q j} si i 6= j{a : δ(qi,a) = qi}∪{ε} si i = j
Modelos de Computación ITema 2: Autómatas Finitos– p.53/88
Demostración
Para k ≥ 1, tenemos que Rki j está compuesto de dos tipos de
palabras:
Palabras que para ir de qi a q j no pasan por qk: pertenecena Rk−1
i j
Palabras que para ir de qi a q j pasan por qk.Una palabra de este lenguaje está compuesta de trespartes:
Modelos de Computación ITema 2: Autómatas Finitos– p.54/88
Demostración
Para k ≥ 1, tenemos que Rki j está compuesto de dos tipos de
palabras:
Palabras que para ir de qi a q j no pasan por qk: pertenecena Rk−1
i j
Palabras que para ir de qi a q j pasan por qk.Una palabra de este lenguaje está compuesta de trespartes:
qi qk
x ∈ Rk−1ik
Modelos de Computación ITema 2: Autómatas Finitos– p.54/88
Demostración
Para k ≥ 1, tenemos que Rki j está compuesto de dos tipos de
palabras:
Palabras que para ir de qi a q j no pasan por qk: pertenecena Rk−1
i j
Palabras que para ir de qi a q j pasan por qk.Una palabra de este lenguaje está compuesta de trespartes:
qi qk
x ∈ Rk−1ik
. . .
Modelos de Computación ITema 2: Autómatas Finitos– p.54/88
Demostración
Para k ≥ 1, tenemos que Rki j está compuesto de dos tipos de
palabras:
Palabras que para ir de qi a q j no pasan por qk: pertenecena Rk−1
i j
Palabras que para ir de qi a q j pasan por qk.Una palabra de este lenguaje está compuesta de trespartes:
qi qk
x ∈ Rk−1ik
. . .y1 ∈ Rk−1
kk ym ∈ Rk−1kk
Modelos de Computación ITema 2: Autómatas Finitos– p.54/88
Demostración
Para k ≥ 1, tenemos que Rki j está compuesto de dos tipos de
palabras:
Palabras que para ir de qi a q j no pasan por qk: pertenecena Rk−1
i j
Palabras que para ir de qi a q j pasan por qk.Una palabra de este lenguaje está compuesta de trespartes:
qi qk
x ∈ Rk−1ik
. . .y1 ∈ Rk−1
kk ym ∈ Rk−1kk
q j
z ∈ Rk−1k j
Modelos de Computación ITema 2: Autómatas Finitos– p.54/88
Demostración
qi qk
x ∈ Rk−1ik
. . .y1 ∈ Rk−1
kk ym ∈ Rk−1kk
q j
z ∈ Rk−1k j
Como la palabra y1 . . .ym ∈(
Rk−1kk
)∗, entonces la palabra
completa está enRk−1
ik
(
Rk−1kk
)∗Rk−1
k j
Uniendo las dos partes, obtenemos:
Rki j = Rk−1
i j ∪Rk−1ik
(
Rk−1kk
)∗Rk−1
k j
Modelos de Computación ITema 2: Autómatas Finitos– p.55/88
Demostración
qi qk
x ∈ Rk−1ik
. . .y1 ∈ Rk−1
kk ym ∈ Rk−1kk
q j
z ∈ Rk−1k j
Como la palabra y1 . . .ym ∈(
Rk−1kk
)∗, entonces la palabra
completa está enRk−1
ik
(
Rk−1kk
)∗Rk−1
k j
Uniendo las dos partes, obtenemos:
Rki j = Rk−1
i j ∪Rk−1ik
(
Rk−1kk
)∗Rk−1
k j
Modelos de Computación ITema 2: Autómatas Finitos– p.55/88
Demostración
qi qk
x ∈ Rk−1ik
. . .y1 ∈ Rk−1
kk ym ∈ Rk−1kk
q j
z ∈ Rk−1k j
Como la palabra y1 . . .ym ∈(
Rk−1kk
)∗, entonces la palabra
completa está enRk−1
ik
(
Rk−1kk
)∗Rk−1
k j
Uniendo las dos partes, obtenemos:
Rki j = Rk−1
i j ∪Rk−1ik
(
Rk−1kk
)∗Rk−1
k j
Modelos de Computación ITema 2: Autómatas Finitos– p.55/88
DemostraciónExpresión regular asociada a Rk
i j −→ rkij
Para k = 0 es inmediato.
r0ij =
{
a1 + . . .+al si i 6= ja1 + . . .+al + ε si i = j
donde {a1, . . . ,al} es el conjunto {a : δ(qi,a) = q j}.Si este conjunto es vacío la expresión regular sería:
r0ij =
{
/0 si i 6= jε si i = j
Cálculo de las expresiones rki j, calculadas las rk−1
i j
Rki j = Rk−1
i j ∪Rk−1ik (Rk−1
kk )∗Rk−1k j −→ rk−1
ij + rk−1ik (rk−1
kk )∗rk−1kj
Modelos de Computación ITema 2: Autómatas Finitos– p.56/88
Demostración
Expresión Regular del lenguaje aceptado por el autómata
L(M) =⋃
q j∈F
Rn1 j
Por tanto, L(M) viene denotado por la expresión regular
rn1j1
+ . . .+ rn1jk
donde F = {q j1, . . . ,q jk}.
Modelos de Computación ITema 2: Autómatas Finitos– p.57/88
Ejemplo
q1 q2 q30 1
0 0,1
1
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.58/88
Ejemplo
q1 q2 q30 1
0 0,1
1
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.58/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011
= ε+ ε(ε)∗ε = εr1
12 = r012 + r0
11(r011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε
= εr1
12 = r012 + r0
11(r011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012
= 0+ ε(ε)∗0 = 0r1
13 = r013 + r0
11(r011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0
= 0r1
13 = r013 + r0
11(r011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1
= 1r1
21 = r021 + r0
21(r011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε
= 0r1
22 = r022 + r0
21(r011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0
= ε+00r1
23 = r023 + r0
21(r011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1
= 1+01r1
31 = r031 + r0
31(r011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε
= /0r1
32 = r032 + r0
31(r011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0
= 0+1r1
33 = r033 + r0
31(r011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1
= ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r011 = ε
r012 = 0
r013 = 1
r021 = 0
r022 = ε
r023 = 1
r031 = /0
r032 = 0+1
r033 = ε
r111 = r0
11 + r011(r
011)
∗r011 = ε+ ε(ε)∗ε = ε
r112 = r0
12 + r011(r
011)
∗r012 = 0+ ε(ε)∗0 = 0
r113 = r0
13 + r011(r
011)
∗r013 = 1+ ε(ε)∗1 = 1
r121 = r0
21 + r021(r
011)
∗r011 = 0+0(ε)∗ε = 0
r122 = r0
22 + r021(r
011)
∗r012 = ε+0(ε)∗0 = ε+00
r123 = r0
23 + r021(r
011)
∗r013 = 1+0(ε)∗1 = 1+01
r131 = r0
31 + r031(r
011)
∗r011 = /0+ /0(ε)∗ε = /0
r132 = r0
32 + r031(r
011)
∗r012 = 0+1+ /0(ε)∗0 = 0+1
r133 = r0
33 + r031(r
011)
∗r013 = ε+ /0(ε)∗1 = ε
Modelos de Computación ITema 2: Autómatas Finitos– p.59/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0
= (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00)
= 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01)
= 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0
= (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00)
=
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01)
=
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0
=
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00)
=
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01)
=
ε+(0+1)0∗1
Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r111 = ε
r112 = 0
r113 = 1
r121 = 0
r122 = ε+00
r123 = 1+01
r131 = /0
r132 = 0+1
r133 = ε
r211 = r1
11 + r112(r
122)
∗r121 = ε+0(ε+00)∗0 = (00)∗
r212 = r1
12 + r112(r
122)
∗r122 = 0+0(ε+00)∗(ε+00) = 0(00)∗
r213 = r1
13 + r112(r
122)
∗r123 = 1+0(ε+00)∗(1+01) = 0∗1
r221 = r1
21 + r122(r
122)
∗r121 = 0+(ε+00)(ε+00)∗0 = (00)∗0
r222 = r1
22 + r122(r
122)
∗r122 = ε+00+(ε+00)(ε+00)∗(ε+00) =
(00)∗
r223 = r1
23 + r122(r
122)
∗r123 = 1+01+(ε+00)(ε+00)∗(1+01) =
0∗1
r231 = r1
31 + r132(r
122)
∗r121 = /0+(0+1)(ε+00)∗0 =
(0+1)(00)∗0
r232 = r1
32 + r132(r
122)
∗r122 = 0+1+(0+1)(ε+00)∗(ε+00) =
(0+1)(00)∗
r233 = r1
33 + r132(r
122)
∗r123 = ε+(0+1)(ε+00)∗(1+01) =
ε+(0+1)0∗1Modelos de Computación ITema 2: Autómatas Finitos– p.60/88
Ejemplo
r211 = (00)∗
r212 = 0(00)∗
r213 = 0∗1
r221 = (00)∗0
r222 = (00)∗
r223 = 0∗1
r231 = (0+1)(00)∗0
r232 = (0+1)(00)∗
r233 = ε+(0+1)0∗1
Finalmente la expresión regular para el lenguaje aceptado es:
r312 + r3
13 =
r212 + r2
13(r233)
∗r232 + r2
13 + r213(r
233)
∗r233 =
0(00)∗ +0∗1(ε+(0+1)0∗1)∗(0+1)(00)∗ +0∗1+0∗1(ε+(0+1)0∗1)∗(ε+(0+1)0∗1) =
0(00)∗ +0∗1((0+1)0∗1)∗(0+1)(00)∗ +0∗1+0∗1((0+1)0∗1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.61/88
Ejemplo
r211 = (00)∗
r212 = 0(00)∗
r213 = 0∗1
r221 = (00)∗0
r222 = (00)∗
r223 = 0∗1
r231 = (0+1)(00)∗0
r232 = (0+1)(00)∗
r233 = ε+(0+1)0∗1
Finalmente la expresión regular para el lenguaje aceptado es:
r312 + r3
13 = r212 + r2
13(r233)
∗r232 + r2
13 + r213(r
233)
∗r233 =
0(00)∗ +0∗1(ε+(0+1)0∗1)∗(0+1)(00)∗ +0∗1+0∗1(ε+(0+1)0∗1)∗(ε+(0+1)0∗1) =
0(00)∗ +0∗1((0+1)0∗1)∗(0+1)(00)∗ +0∗1+0∗1((0+1)0∗1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.61/88
Ejemplo
r211 = (00)∗
r212 = 0(00)∗
r213 = 0∗1
r221 = (00)∗0
r222 = (00)∗
r223 = 0∗1
r231 = (0+1)(00)∗0
r232 = (0+1)(00)∗
r233 = ε+(0+1)0∗1
Finalmente la expresión regular para el lenguaje aceptado es:
r312 + r3
13 = r212 + r2
13(r233)
∗r232 + r2
13 + r213(r
233)
∗r233 =
0(00)∗ +0∗1(ε+(0+1)0∗1)∗(0+1)(00)∗ +0∗1+0∗1(ε+(0+1)0∗1)∗(ε+(0+1)0∗1) =
0(00)∗ +0∗1((0+1)0∗1)∗(0+1)(00)∗ +0∗1+0∗1((0+1)0∗1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.61/88
Ejemplo
r211 = (00)∗
r212 = 0(00)∗
r213 = 0∗1
r221 = (00)∗0
r222 = (00)∗
r223 = 0∗1
r231 = (0+1)(00)∗0
r232 = (0+1)(00)∗
r233 = ε+(0+1)0∗1
Finalmente la expresión regular para el lenguaje aceptado es:
r312 + r3
13 = r212 + r2
13(r233)
∗r232 + r2
13 + r213(r
233)
∗r233 =
0(00)∗ +0∗1(ε+(0+1)0∗1)∗(0+1)(00)∗ +0∗1+0∗1(ε+(0+1)0∗1)∗(ε+(0+1)0∗1) =
0(00)∗ +0∗1((0+1)0∗1)∗(0+1)(00)∗ +0∗1+0∗1((0+1)0∗1)∗
Modelos de Computación ITema 2: Autómatas Finitos– p.61/88
Expresiones Regulares en Unix
Expresión Regular SignificadoCaracteres Normales Ellos mismos+,∗ Superíndices +,*| La unión de los lenguajes[. . .] Cualquier símbolo entre corchetes[a−b] todos los caracteres entre a y b[^. . .] El complementario de [. . .]
? 0 ó 1 repetición de lo anterior{nombre} Se substituye la e.r. nombre{n} n repeticiones de la anterior e.r.{n,m} entre n y m repeticiones de la anterior e.r.∗ El carácter ∗". . ." Los caracteres entre comillas literalmente^,$ Principio, fin de línea
Modelos de Computación ITema 2: Autómatas Finitos– p.62/88
Estructura de un fichero lex
nombre1 er1nombre2 er2nombrei eri
declaglobal1declaglobal2
% %declalocal1declalocal2
er1 accion1;er2 accion2;er3 accion3;% %definiciones de funciones en C
Modelos de Computación ITema 2: Autómatas Finitos– p.63/88
Variables y Procedimientos
yylex() – Programa que reconoce las expresiones regulares y ejecutalas acciones.
main() – Programa principal. Por defecto sólo llama a yylex(). Sepuede redefinir después de los últimos % %
yywrap() – Función que se ejecuta cuando yylex() encuentra un fin defichero. Si devuelve 1 (lo único que hace la versión por defecto) yylex()termina. Si devuelve un 0, yylex() sigue leyendo de la entrada.
yyin – Fichero de entrada (stdin por defecto)
yyout – Fichero de salida (stdout por defecto)
yytext – Variable que contiene la cadena reconocida por yylex()
yyleng – Longitud de la cadena reconocida
Modelos de Computación ITema 2: Autómatas Finitos– p.64/88
Ejemplo
car [a-zA-Z]
digito [0-9]
signo (\-|\+)
suc ({digito}+)
enter ({signo}?{suc})
real1 ({enter}\.{digito}*)
real2 ({signo}?\.{suc})
int ent=0, real=0, ident=0, sumaent=0;
%%
int i;
{enter} {ent++; sscanf(yytext,"%d",&i); sumaent += i;
printf("Numero entero %s\n",yytext);}
({real1}|{real2}) {real++; printf("Num. real %s\n",yytext);}
{car}({car}|{digito})* {ident++; printf("identificador %s\n",yytext);}
.|\n {;}
%%
yywrap()
{printf("Numero de Enteros %d, reales %d, ident %d,
Suma de Enteros %d",ent,real,ident,sumaent); return 1;}
Modelos de Computación ITema 2: Autómatas Finitos– p.65/88
Procedimiento
1. Crear fichero ejemplo con el contenido anterior
2. Ejecutar lex con el fichero creado:lex ejemplo
3. Compilar el programa que crea lex:gcc lex.yy.c -o prog -ll
4. ejecutar el programa prog
Modelos de Computación ITema 2: Autómatas Finitos– p.66/88
Aplicaciones de las Expresiones Regulares
Para búsqueda de patrones (buscar direcciones, enlaces onúmeros de teléfono en páginas web).
Fueron centrales en el desarrollo de Unix:K. Thompson (1968) Regular expressions searchalgorithms. Comm. ACM. 11, 419–422.Existen intrucciones como grep: ’Global (Searh for) RegularExpressions and Print’
K. Thompson está desarrollando un sistema decomunicaciones para teléfonos basado en máquinas deestado finito, desarrollando un lenguaje para crear lasmáquinas. Ver entrevista en:http://www.computer.org/computer/thompson.htm
Modelos de Computación ITema 2: Autómatas Finitos– p.67/88
Aplicaciones de las Expresiones Regulares
Common Applications of Regular Expressions By Richard Lowe enhttp://www.4guysfromrolla.com/webtech/120400-1.shtmlcontiene 4 aplicaciones de expresiones regulares, desde verificación de direcciones de correoelectrónico a dividir un documento en secciones para incorporarlo en una base de datos.
En http://www.webreference.com/js/column5/ podeis ver el uso de expresiones regulares ennavegadores.
Podeis leer un artículo sobre expresiones regulares y Java en:http://developer.java.sun.com/developer/technicalArticles/releases/1.4regex/
En la direcciónhttp://www.mitchenall.com/resources/library/4d/regular_expressions/index.phtml?page=2
podeis ver un ejemplo de uso de expresiones regulares en bases de datos.
Modelos de Computación ITema 2: Autómatas Finitos– p.68/88
Gramáticas Regulares ó tipo 3
Lineales por la derecha.- Cuando todas las producciones tienenla forma
A → uB
A → u
Lineales por la izquierda.- Cuando todas las producciones tienenla forma
A → Bu
A → u
Modelos de Computación ITema 2: Autómatas Finitos– p.69/88
Gramáticas Regulares ó tipo 3
Lineales por la derecha.- Cuando todas las producciones tienenla forma
A → uB
A → u
Lineales por la izquierda.- Cuando todas las producciones tienenla forma
A → Bu
A → u
Modelos de Computación ITema 2: Autómatas Finitos– p.69/88
Ejemplo
Gramática Lineal por la Derecha:
S → 0A, A → 10A, A → ε
Expresión Regular
0(10)∗
Gramática Lineal por la Izquierda:
S → S10, S → 0
Modelos de Computación ITema 2: Autómatas Finitos– p.70/88
Ejemplo
Gramática Lineal por la Derecha:
S → 0A, A → 10A, A → ε
Expresión Regular
0(10)∗
Gramática Lineal por la Izquierda:
S → S10, S → 0
Modelos de Computación ITema 2: Autómatas Finitos– p.70/88
Ejemplo
Gramática Lineal por la Derecha:
S → 0A, A → 10A, A → ε
Expresión Regular
0(10)∗
Gramática Lineal por la Izquierda:
S → S10, S → 0
Modelos de Computación ITema 2: Autómatas Finitos– p.70/88
Gramática Regular → AutómataSi L es un lenguaje generado por una gramática regular, entonces existe unautómata finito determinista que lo reconoce.L es un lenguaje generado por la gramática G = (V,T,P,S) lineal por laderecha. AFND con movimientos nulos que acepta L: M = (Q,T,δ,q,F)
donde
Q = {[α] : (α = S)∨ (∃A ∈V,u ∈ T, tales que A → uα ∈ P)}
q0 = [S]
F = {[ε]}
δ viene definida por
Si A es una variable: δ([A],ε) = {[α] : (A → α) ∈ P}
Si a ∈ T y α ∈ (T ∗V ∪T ∗), entonces
δ([aα],a) = [α]
Modelos de Computación ITema 2: Autómatas Finitos– p.71/88
Ejemplo
Sea la gramática:
S → 0A, A → 10A, A → ε
El autómata que se obtiene es el siguiente:
[S] [0A] [A]
[10A] [ε]
Modelos de Computación ITema 2: Autómatas Finitos– p.72/88
Ejemplo
Sea la gramática:
S → 0A, A → 10A, A → ε
El autómata que se obtiene es el siguiente:
[S] [0A] [A]
[10A] [ε]
Modelos de Computación ITema 2: Autómatas Finitos– p.72/88
Ejemplo
Sea la gramática:
S → 0A, A → 10A, A → ε
El autómata que se obtiene es el siguiente:
[S] [0A] [A]
[10A] [ε]
ε
ε ε
Modelos de Computación ITema 2: Autómatas Finitos– p.72/88
Ejemplo
Sea la gramática:
S → 0A, A → 10A, A → ε
El autómata que se obtiene es el siguiente:
[S] [0A] [A]
[10A] [ε]
ε
ε ε
0
1
Modelos de Computación ITema 2: Autómatas Finitos– p.72/88
Gramáticas Lineales por la IzquierdaGramática lineal por la izquierda, G = (V,T,P,S)
1. Consideraremos la gramática G′ = (V,T,P′,S) donde
P′ = {A → α : A → α−1 ∈ P}
Es inmediato que L(G′) = L(G)−1.2. Sea M′ el autómata finito no-determinista que acepta el lenguaje L(G′).3. Calcular M a partir de M′ invirtiendo el autómata:
Dejar sólo un estado final (ocurre siempre en nuestro caso).
Invertir las transiciones
Intercambiar el estado inicial y el final.
El lenguaje aceptado por M es: L(M′)−1 = L(G′)−1 =(
L(G)−1)−1
= L(G)
Modelos de Computación ITema 2: Autómatas Finitos– p.73/88
Ejemplo
S → S10, S → 0Para construir un AFND con transiciones nulas que acepte estelenguaje se dan los siguientes pasos:
Invertir la parte derecha de las producciones:S → 01SS → 0
Construir el AFND con transiciones nulas asociado
[S] [0] [ε]
[1S] [01S]
ε 0
ε
0
1
Modelos de Computación ITema 2: Autómatas Finitos– p.74/88
Ejemplo
S → S10, S → 0Para construir un AFND con transiciones nulas que acepte estelenguaje se dan los siguientes pasos:
Invertir la parte derecha de las producciones:S → 01SS → 0
Construir el AFND con transiciones nulas asociado
[S] [0] [ε]
[1S] [01S]
ε 0
ε
0
1
Modelos de Computación ITema 2: Autómatas Finitos– p.74/88
Ejemplo
S → S10, S → 0Para construir un AFND con transiciones nulas que acepte estelenguaje se dan los siguientes pasos:
Invertir la parte derecha de las producciones:S → 01SS → 0
Construir el AFND con transiciones nulas asociado
[S] [0] [ε]
[1S] [01S]
ε 0
ε
0
1
Modelos de Computación ITema 2: Autómatas Finitos– p.74/88
Ejemplo Cont.
[S] [0] [ε]
[1S] [01S]
ε 0
ε
0
1
Invertimos el autómata
[S] [0] [ε]
[1S] [01S]
ε 0
ε
0
1
Modelos de Computación ITema 2: Autómatas Finitos– p.75/88
Ejemplo Cont.
[S] [0] [ε]
[1S] [01S]
ε 0
ε
0
1
Invertimos el autómata
[S] [0] [ε]
[1S] [01S]
ε 0
ε
0
1
Modelos de Computación ITema 2: Autómatas Finitos– p.75/88
Autómata → Gramática lineal
Si L es aceptado por un Autómata Finito Determinístico entonces Lpuede generarse mediante una gramática lineal por la derecha y poruna lineal por la izquierda.
Sea L = L(M) donde M = (Q,A,δ,q,F) es un autómata finitodeterminista.La gramática lineal por la derecha es G = (Q,A,P,q0) donde lasvariables son los estados, la variable inicial es q0 y P contiene lasproducciones, p → aq, si δ(p,a) = q
p → ε, si p ∈ F
Para el caso de una gramática lineal por la izquierda, invertimos elautómata, construímos la gramática lineal por la derecha asociada einvertimos la parte derecha de las producciones.
Modelos de Computación ITema 2: Autómatas Finitos– p.76/88
Autómata → Gramática lineal
Si L es aceptado por un Autómata Finito Determinístico entonces Lpuede generarse mediante una gramática lineal por la derecha y poruna lineal por la izquierda.Sea L = L(M) donde M = (Q,A,δ,q,F) es un autómata finitodeterminista.La gramática lineal por la derecha es G = (Q,A,P,q0) donde lasvariables son los estados, la variable inicial es q0 y P contiene lasproducciones, p → aq, si δ(p,a) = q
p → ε, si p ∈ F
Para el caso de una gramática lineal por la izquierda, invertimos elautómata, construímos la gramática lineal por la derecha asociada einvertimos la parte derecha de las producciones.
Modelos de Computación ITema 2: Autómatas Finitos– p.76/88
Autómata → Gramática lineal
Si L es aceptado por un Autómata Finito Determinístico entonces Lpuede generarse mediante una gramática lineal por la derecha y poruna lineal por la izquierda.Sea L = L(M) donde M = (Q,A,δ,q,F) es un autómata finitodeterminista.La gramática lineal por la derecha es G = (Q,A,P,q0) donde lasvariables son los estados, la variable inicial es q0 y P contiene lasproducciones, p → aq, si δ(p,a) = q
p → ε, si p ∈ F
Para el caso de una gramática lineal por la izquierda, invertimos elautómata, construímos la gramática lineal por la derecha asociada einvertimos la parte derecha de las producciones.
Modelos de Computación ITema 2: Autómatas Finitos– p.76/88
Ejemplo: Gramática Lineal por la Derecha
Consideremos el autómata:q0 q1
q2
0
1
0 0,11
La gramática es (variable inicial q0):
q0 → 0q1, q0 → 1q2, q1 → 0q2, q1 → 1q2
q2 → 0q0, q2 → 1q1, q2 → ε
Modelos de Computación ITema 2: Autómatas Finitos– p.77/88
Ejemplo: Gramática Lineal por la Derecha
Consideremos el autómata:q0 q1
q2
0
1
0 0,11
La gramática es (variable inicial q0):
q0 → 0q1, q0 → 1q2, q1 → 0q2, q1 → 1q2
q2 → 0q0, q2 → 1q1, q2 → ε
Modelos de Computación ITema 2: Autómatas Finitos– p.77/88
Ejemplo: Gramática Lineal por la IzquierdaAutómata de Partida:
Invertimos el autómata:
q0 q1
q2
0
1
0 0,11
q0 q1
q2
0
0
1
0,11
La gramática asociada a este autómata es (variable inicial q2):
q1 → 0q0, q2 → 1q0, q2 → 0q1, q2 → 1q1
q0 → 0q2, q1 → 1q2, q0 → ε
Invertimos la parte derecha de las producciones:
q1 → q00, q2 → q01, q2 → q10, q2 → q11
q0 → q20, q1 → q21, q0 → ε
Modelos de Computación ITema 2: Autómatas Finitos– p.78/88
Ejemplo: Gramática Lineal por la IzquierdaAutómata de Partida: Invertimos el autómata:
q0 q1
q2
0
1
0 0,11
q0 q1
q2
0
0
1
0,11
La gramática asociada a este autómata es (variable inicial q2):
q1 → 0q0, q2 → 1q0, q2 → 0q1, q2 → 1q1
q0 → 0q2, q1 → 1q2, q0 → ε
Invertimos la parte derecha de las producciones:
q1 → q00, q2 → q01, q2 → q10, q2 → q11
q0 → q20, q1 → q21, q0 → ε
Modelos de Computación ITema 2: Autómatas Finitos– p.78/88
Ejemplo: Gramática Lineal por la IzquierdaAutómata de Partida: Invertimos el autómata:
q0 q1
q2
0
1
0 0,11
q0 q1
q2
0
0
1
0,11
La gramática asociada a este autómata es (variable inicial q2):
q1 → 0q0, q2 → 1q0, q2 → 0q1, q2 → 1q1
q0 → 0q2, q1 → 1q2, q0 → ε
Invertimos la parte derecha de las producciones:
q1 → q00, q2 → q01, q2 → q10, q2 → q11
q0 → q20, q1 → q21, q0 → ε
Modelos de Computación ITema 2: Autómatas Finitos– p.78/88
Ejemplo: Gramática Lineal por la IzquierdaAutómata de Partida: Invertimos el autómata:
q0 q1
q2
0
1
0 0,11
q0 q1
q2
0
0
1
0,11
La gramática asociada a este autómata es (variable inicial q2):
q1 → 0q0, q2 → 1q0, q2 → 0q1, q2 → 1q1
q0 → 0q2, q1 → 1q2, q0 → ε
Invertimos la parte derecha de las producciones:
q1 → q00, q2 → q01, q2 → q10, q2 → q11
q0 → q20, q1 → q21, q0 → εModelos de Computación ITema 2: Autómatas Finitos– p.78/88
Máquinas de Estado FinitoMáquinas de Moore: con salida asociada al estado
Máquinas de Mealy: con salida asociada a la transición
Máquinas de Moore
Una máquina de Moore es una sextupla{(Q,A,B,δ,λ,q0)} donde todo es igual en un AFD, excepto
B alfabeto de salida
λ : Q → B que es una aplicación que hace corresponder a cada estado susalida correspondiente.
Si el autómata lee la cadena u y pasa por los estados q0q1...qn entonces produce lasalida:
λ(q0)λ(q1) . . .λ(qn)
Para la cadena vacía: λ(q0).
Modelos de Computación ITema 2: Autómatas Finitos– p.79/88
Ejemplo
Control de semáforos en un cruce.
��
�1
��
� α2
��
� 3
� ��
4
β
Modelos de Computación ITema 2: Autómatas Finitos– p.80/88
Descripción
Hay cuatro semáforos: 1,2,3,4.
El tráfico más importante se realiza en la calle horizontal y, pordefecto, los semáforos 1 y 3 están abiertos.
Hay dos sensores que detectan si hay coches esperando: αpara el 2 y β para el 4.
Cuando se detectan coches en cualquiera de los dos semáforos,2 ó 4, se cierran los semáforos necesarios y se abre el semáforopara que pasen estos coches.
El alfabeto de entrada está formado por los pares (i, j), i, j = 0,1,donde i indica si α detecta coches y j lo mismo para β.
El alfabeto de salida estará formada por los vectores(C1,C2,C3,C4), donde Ci es el color del semáforo i. Los posiblescolores son: R (Rojo), A (Ámbar), V (Verde).
Modelos de Computación ITema 2: Autómatas Finitos– p.81/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,0)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1)
(0,0)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(0,0)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(0,0) (0,1),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
(0,0) (0,1),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
A
(0,0) (0,1),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
A
(0,0) (0,1),(1,1)
(1,0),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
A
(0,0),(1,0)
(0,0) (0,1),(1,1)
(1,0),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
A
(0,0),(1,0)
(0,0),(0,1)
(0,0) (0,1),(1,1)
(1,0),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
A
(0,0),(1,0)
(0,0),(0,1)
(1,0),(1,1)
(0,0) (0,1),(1,1)
(1,0),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
A
(0,0),(1,0)
(0,0),(0,1)
(1,0),(1,1)
(0,0)
(0,0) (0,1),(1,1)
(1,0),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
A
(0,0),(1,0)
(0,0),(0,1)
(1,0),(1,1)
(0,0)
A
(0,0) (0,1),(1,1)
(1,0),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
A
(0,0),(1,0)
(0,0),(0,1)
(1,0),(1,1)
(0,0)
(0,1)
A
(0,0) (0,1),(1,1)
(1,0),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Moore
q0
(V,R,V,R)
q1
(A,R,A,R)
q2
(R,R,R,V )
q3
(V,R,A,R)
q5
(R,R,R,A)
q6
(V,A,R,R)
q4
(V,V,R,R)
q7
(A,A,R,R)
(0,1),(1,1) A
(1,0)
A
(0,0),(1,0)
(0,0),(0,1)
(1,0),(1,1)
(0,0)
(0,1)
AA
(0,0) (0,1),(1,1)
(1,0),(1,1)
Modelos de Computación ITema 2: Autómatas Finitos– p.82/88
Máquina de Mealy
Una Máquina de Mealy es una sextupla M = (Q,A,B,δ,λ,q0)donde todo es igual que en las máquinas de Moore, exceptoque λ es una aplicación de Q×A en B,
λ : Q×A → B
es decir, que la salida depende del estado en el que está elautómata y del símbolo leido.
Si la entrada es a1 . . .an y pasa por los estados q0,q1, . . . ,qn, lasalida es
λ(q0,a1)λ(q1,a2) . . .λ(qn−1,an)
Si se le suministra ε como entrada produce ε como salida.
Modelos de Computación ITema 2: Autómatas Finitos– p.83/88
Máquina de Mealy
Una Máquina de Mealy es una sextupla M = (Q,A,B,δ,λ,q0)donde todo es igual que en las máquinas de Moore, exceptoque λ es una aplicación de Q×A en B,
λ : Q×A → B
es decir, que la salida depende del estado en el que está elautómata y del símbolo leido.
Si la entrada es a1 . . .an y pasa por los estados q0,q1, . . . ,qn, lasalida es
λ(q0,a1)λ(q1,a2) . . .λ(qn−1,an)
Si se le suministra ε como entrada produce ε como salida.
Modelos de Computación ITema 2: Autómatas Finitos– p.83/88
Ejemplo
Máquina de Mealy que calcula la división entera por tres.
q0 q1
q2
1/0
1/1
0/00/1
0/0
1/1
Modelos de Computación ITema 2: Autómatas Finitos– p.84/88
Ejemplo: Máquina Codificadora
El alfabeto de entrada es {0,1} y el de salida {0,1}. La traducciónviene dada por las siguientes reglas,
Primer símbolo: 0 → 0 1 → 1
Siguientes símbolosSi el anterior es un 0: 0 → 0, 1 → 1Si el anterior es un 1: 0 → 1, 1 → 0
La máquina de Mealy que realiza esta codificación es la siguiente:
q0 q1
1/1
0/1
0/0 1/0
si lee 0101, la salida correspondiente es 0111.
Modelos de Computación ITema 2: Autómatas Finitos– p.85/88
Máquina de Moore → Máquina de Mealy
Una máquina de Moore, M, y una Máquina de Mealy, M′, sedicen equivalentes sii para todo u ∈ A∗, TM(u) = bTM′(u) donde bes la salida correspondiente al estado inicial de la máquina deMoore M.
Teorema: Dada una máquina de Moore M existe una máquinade Mealy M′ equivalente.
Teorema: Dada una máquina de Mealy M existe una máquinade Moore M′ equivalente.
Modelos de Computación ITema 2: Autómatas Finitos– p.86/88
Mealy −→ Moore
Sea M = (Q,A,B,δ,λ,q0) una máquina de Moore,La máquina de Mealy equivalente será M′ = (Q,A,B,δ,λ′,q0),donde
λ′(q,a) = λ(δ(q,a))
Ejemplo
q0/1 q1/0
q0 q1
1
0
0 1
Modelos de Computación ITema 2: Autómatas Finitos– p.87/88
Mealy −→ Moore
Sea M = (Q,A,B,δ,λ,q0) una máquina de Moore,La máquina de Mealy equivalente será M′ = (Q,A,B,δ,λ′,q0),donde
λ′(q,a) = λ(δ(q,a))
Ejemplo
q0/1 q1/0 q0 q1
1
0
1/0
0/1
0 1 0/1 1/0
Modelos de Computación ITema 2: Autómatas Finitos– p.87/88
Máquina de Mealy → Máquina de Moore
Sea M = (Q,A,B,δ,λ,q0) una máquina de Mealy.La máquina de Moore será: M = (Q′,A,B,δ′,λ′,q′
0) donde
Q′ = Q×B
δ′((q,b),a) = (δ(q,a),λ(q,a))
λ′(q,b) = b
q′0 = (q0,b), donde b ∈ B, cualquiera.
Modelos de Computación ITema 2: Autómatas Finitos– p.88/88
Ejemplo
q0 q1
q2
1/0
1/1
0/00/10/0
1/1
(q0,0)
0
(q1,0)
0
(q2,0)
0
(q0,1)
1
(q1,1)
1
(q2,1)
1
Modelos de Computación ITema 2: Autómatas Finitos– p.89/88
Ejemplo
q0 q1
q2
1/0
1/1
0/00/10/0
1/1
(q0,0)
0
(q1,0)
0
(q2,0)
0
(q0,1)
1
(q1,1)
1
(q2,1)
1
0
Modelos de Computación ITema 2: Autómatas Finitos– p.89/88
Ejemplo
q0 q1
q2
1/0
1/1
0/00/10/0
1/1
(q0,0)
0
(q1,0)
0
(q2,0)
0
(q0,1)
1
(q1,1)
1
(q2,1)
1
1
0
Modelos de Computación ITema 2: Autómatas Finitos– p.89/88