Modelos de Computación I Tema 2: Autómatas Finitos Serafín Moral Departamento 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 para buscar palabras, estructuras u otros patrones (p.e. páginas web). Software para comprobar la corrección de cualquier tipo de sistemas 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 un alumno por una asignatura, por ejemplo, Modelos de Computació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

Modelos de Computación ITema 2: Autómatas Finitos– p.5/88

Ejemplo Introductorio

Inicio

P

Febr.

N

Dec2

Modelos de Computación ITema 2: Autómatas Finitos– p.5/88

Ejemplo Introductorio

Inicio

P

Febr.

S

Dec1

A N

Fin1

Dec2

Modelos de Computación ITema 2: Autómatas Finitos– p.5/88

Ejemplo Introductorio P

Inicio

P

Febr.

S

Sept1.

Dec1

A N

Fin1

Dec2

Modelos de Computación ITema 2: Autómatas Finitos– p.5/88

Ejemplo Introductorio S P

Inicio

P

Febr.

S

Sept1.

A

Fin2

Dec1

A N

Fin1

Dec2

Modelos de Computación ITema 2: Autómatas Finitos– p.5/88

Ejemplo Introductorio S

Sept1.

P

Inicio

P

S

Febr.

A

Fin2

Dec1

A N

Fin1 P

Dec2

N

N

Sept2.

Dec3

Modelos de Computación ITema 2: Autómatas Finitos– p.5/88

Ejemplo Introductorio S

Sept1.

P

Inicio

P

S

Febr.

A

Dec1

A N

Fin2

A

Fin1 P

Dec2

N

Sept2. S

N

Dec3

Modelos de Computación ITema 2: Autómatas Finitos– p.5/88

Ejemplo Introductorio S

Sept1.

P

Inicio

P

S

Febr.

A

Dec1

A N

Fin2

A

Fin1

N

P

Dec2

Sept2.

N

S

Dec3

N P

Dic. Modelos de Computación ITema 2: Autómatas Finitos– p.5/88

Ejemplo Introductorio S

Sept1.

P

Inicio

P

S

Febr.

A

Dec1

A N

Fin2

A

Fin1

N

P

Dec2

Sept2.

N

S

Dec3

N

S

P

Fin3

A

Dic. 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 estados finales.

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 estados finales están indicados con una doble circunferencia. a a

q0

q1 b a

b

b q2

Modelos de Computación ITema 2: Autómatas Finitos– p.8/88

Cálculo Asociado. Traza 1 q0

0

0 q1

1

Modelos de Computación ITema 2: Autómatas Finitos– p.9/88

Cálculo Asociado. Traza 1 q0

0

0 q1

1 1 0 0 q0

q1

Modelos de Computación ITema 2: Autómatas Finitos– p.9/88

Cálculo Asociado. Traza 1 q0

0

0 q1

1 1 0 0


q0

q1

q0

q1



1 0 0

Modelos de Computación ITema 2: Autómatas Finitos– p.9/88

Cálculo Asociado. Traza 1 q0

0

0 q1

1 1 0 0

1 0 0 q0

q1



q1



q0

1 0 0 q1 

q0

Modelos de Computación ITema 2: Autómatas Finitos– p.9/88

Cálculo Asociado. Traza 1 q0

0

0 q1

1 1 0 0

1 0 0 q0

1 0 0 

q1

Estado final SI

q0

q1

1 0 0 q0

q1



q1



q0

Modelos de Computación ITema 2: Autómatas Finitos– p.9/88

PROCESO DE CALCULO Autó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 a una 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 de configuraciones 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

0

0

q1

1 1 0 0

(100, q0 ) ` (00, q0 ) ` (0, q1 ) ` (ε, q1 ) ∗

(100, q0 ) ` (ε, q1 ), 100 aceptada 1 0 0 q0

1 0 0

1 0 0 q1

q0

q1



q1

q0

Estado final SI

q0

q1

1

Modelos de Computación ITema 2: Autómatas Finitos– p.12/88

Ejemplo 0 q0

1

0 q1

1

Modelos de Computación ITema 2: Autómatas Finitos– p.13/88

Ejemplo 0 q0

1

0 q1

1 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 S

R B, D, Z, H

E

RF B S, Z, D

B, H, S

B, D, Z, H, S

R: Estado de espera RD: Recepción de datos S: Comienza recepción H: Cabecera de fichero D: Datos

H

Z

RD D

RF: Estado de recepción de ficheros E: Error B: Fin de recepción Z: Fin de fichero 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 → | → | → | . → . → . E Modelos de Computación ITema 2: Autómatas Finitos– p.15/88

Autómata Finito T es el conjunto de los símbolos terminales. E, +, −

q2 0, . . . , 9

q0

q8

0, . . . , 9

. 0, . . . , 9

+, −, .

0, . . . , 9

E

q3

q1

E, +, −, .

0, . . . , 9 E, +, −, .

0, . . . , 9

q4 E, +, −, .

+, −

q5

0, . . . , 9

q7

0, . . . , 9 +, −

T

E, +, −, .

q6 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 quintupla M = (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.17/88

Ejemplo 0, 1

0, 1

q0

0

q1

1

q2

0

q3

0

q4

1

q5

0

q6

Se pueden usar también diagramas de transición. Puede haber estados que para una entrada tenga dos transiciones. Por ejemplo, q0 cuando lee 0 puede quedarse en q0 o pasar a q1 . También puede haber estados que para una entrada no tengan ninguna transición: desde q1 no se puede leer el 0. Acepta el conjunto de las palabras que tienen a 010010 como subcadena: palabras que se pueden leer pasando de q0 a un estado final. Modelos de Computación ITema 2: Autómatas Finitos– p.18/88

Ejemplos También es no-determinista: b r0

a

r1

c

r2

Acepta cadenas formadas por una a, una sucesión de b y una c.

Modelos de Computación ITema 2: Autómatas Finitos– p.19/88

Ejemplos También es no-determinista: b r0

a

c

r1

r2

Acepta cadenas formadas por una a, una sucesión de b y una c. Se puede transformar en uno determinista que acepte el mismo lenguaje añadiéndole un estado de error donde vayan todas las transiciones no definidas en el autómata anterior: b r0

a b, c

r1 a r3

c

r2

a, b, c a, b, c

Modelos de Computación ITema 2: Autómatas Finitos– p.19/88

Ejemplo: Constantes reales Autómata determinista: E, +, −

q2 0, . . . , 9

q0

q8

0, . . . , 9

. 0, . . . , 9

+, −, .

0, . . . , 9

E

q3

q1

E, +, −, .

0, . . . , 9 E, +, −, .

0, . . . , 9

q4 E, +, −, .

+, −

q5

0, . . . , 9

q7

0, . . . , 9 +, −

T

E, +, −, .

q6 E, .

E, .

Modelos de Computación ITema 2: Autómatas Finitos– p.20/88

Ejemplo: Constantes reales Autómata no determinista:

q2 0, . . . , 9

0, . . . , 9

.

q0

0, . . . , 9

0, . . . , 9

q3

q8

q5

0, . . . , 9 E

0, . . . , 9

0, . . . , 9

q4

0, . . . , 9 +, −

+, −

q1

q6

Modelos de Computación ITema 2: Autómatas Finitos– p.21/88

PROCESO DE CALCULO Autó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 varias configuraciones distintas en un paso de cálculo, e incluso a ninguna.

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 de configuraciones 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, a)

q∈B

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 desde cualquiera 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-Determis Podemos considerar que todos los autómatas deterministas son también autómatas no-deterministas, en los que δ(q, a) tiene siempre un y sólo un estado. Así, todo lenguaje L aceptado por un autómata determinista es aceptado también por un autómata no-determinista (él mismo). Con los autómatas no-deterministas no aceptamos más lenguajes que con los deterministas: todo lenguaje aceptado por un autómata no-determinista lo será también por uno determinista (lo veremos a continuación). Con los autómatas no-deterministas no ampliamos la familia de lenguajes aceptados por los autómtas deterministas. Simplemente, tenemos más opciones para representar 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 determinista ¯ q¯0 , F) ¯ A, δ, ¯ dado por asociado a M, al autómata M¯ = (Q, Q¯ = ℘(Q) q¯0 = {q0 } ¯δ(B, a) = δ∗ (B, a) = S δ(q, a) q∈B / F¯ = {B ∈ ℘(Q) | B ∩ F 6= 0}

Dado un autómata no determinista se le hace corresponder uno determinista que recorre todos los caminos al mismo tiempo. Un autómata no-determinista y su determinista asociado aceptan el mismo lenguaje Modelos de Computación ITema 2: Autómatas Finitos– p.26/88

Ejemplo 0, 1

0, 1

q0

0

q1

1

q2

0

q3

0

q4

1

q5

0

q6

{q0 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1

1

q2

0

q3

0

q4

1

q5

0

q6

1 {q0 }

0

{q0 , q1 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

q1

1

q2

0

q3

0

q4

1

q5

0

q6

0

1 {q0 }

0

0

{q0 , q1 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

q1

1

q2

0

q3

0

q4

1

q5

0

q6

0

1 {q0 }

0

0

{q0 , q1 }

1

{q0 , q2 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

q1

1

q2

0

q3

0

1 {q0 }

0

0

{q0 , q1 }

1

{q0 , q2 }

0

1

q4 0

q5

0

q6

{q0 , q1 , q3 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

{q0 , q1 }

1

{q0 , q2 }

0

1

q4 0

q5

0

q6

{q0 , q1 , q3 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

{q0 , q1 }

1

{q0 , q2 }

0

1

q4 0

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

{q0 , q1 }

1

{q0 , q2 }

0

1

q4 0 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

1

q4 0

{q0 , q2 } 0

1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 } 0 {q0 , q2 , q5 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 } 0 {q0 , q2 , q5 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 {q0 , q1 , q3 , q6 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 {q0 , q1 , q3 , q6 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 {q0 , q1 , q4 , q6 }

0

{q0 , q1 , q3 , q6 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 {q0 , q1 , q4 , q6 }

0

{q0 , q1 , q3 , q6 } 1 {q0 , q2 , q6 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 {q0 , q1 , q6 }

0

{q0 , q1 , q4 , q6 }

0

{q0 , q1 , q3 , q6 } 1 {q0 , q2 , q6 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 {q0 , q1 , q6 }

0

{q0 , q1 , q4 , q6 } 1 {q0 , q2 , q5 , q6 }

0

{q0 , q1 , q3 , q6 } 1 {q0 , q2 , q6 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 {q0 , q1 , q6 }

0

{q0 , q1 , q4 , q6 } 1 {q0 , q2 , q5 , q6 }

0

{q0 , q1 , q3 , q6 } 0 1 {q0 , q2 , q6 }

Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 {q0 , q1 , q6 } {q0 , q6 }

0

{q0 , q1 , q4 , q6 } 1 {q0 , q2 , q5 , q6 }

0

{q0 , q1 , q3 , q6 } 0 1 {q0 , q2 , q6 }

1 Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 {q0 }

0

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 }

1

0 {q0 , q2 , q5 } 0

{q0 , q1 , q6 } {q0 , q6 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 0

{q0 , q1 , q4 , q6 } 1 {q0 , q2 , q5 , q6 }

0

{q0 , q1 , q3 , q6 } 0 1 {q0 , q2 , q6 }

1 Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 0

{q0 }

1

q2

0

q3

0

0

{q0 , q1 }

1

0 {q0 , q2 , q5 } 0

{q0 , q1 , q6 } 1

0

{q0 , q2 }

1

{q0 , q6 }

1

q4

1 1

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 0

{q0 , q1 , q4 , q6 } 1 {q0 , q2 , q5 , q6 }

0

{q0 , q1 , q3 , q6 } 0 1 {q0 , q2 , q6 }

1 Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 0

{q0 }

1

q2

0

q3

0

0

{q0 , q1 }

1

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

1

{q0 , q6 }

1 1

0 {q0 , q1 , q6 }

1

q4

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 0

{q0 , q1 , q4 , q6 } 1 {q0 , q2 , q5 , q6 }

0

0

{q0 , q1 , q3 , q6 } 0 1 {q0 , q2 , q6 }

1 Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 0

{q0 }

1

q2

0

q3

0

0 1

{q0 , q1 }

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

1

{q0 , q6 }

1 1

0 {q0 , q1 , q6 }

1

q4

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 0 1

{q0 , q1 , q4 , q6 } 1 {q0 , q2 , q5 , q6 }

0

0

{q0 , q1 , q3 , q6 } 0 1 {q0 , q2 , q6 }

1 Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 0

{q0 }

1

q2

0

q3

0

0 1

{q0 , q1 }

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

0 1

{q0 , q6 }

1 1

0 {q0 , q1 , q6 }

1

q4

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 0 1

{q0 , q1 , q4 , q6 } 1 {q0 , q2 , q5 , q6 }

0

0

{q0 , q1 , q3 , q6 } 0 1 {q0 , q2 , q6 }

1 Modelos de Computación ITema 2: Autómatas Finitos– p.27/88

Ejemplo 0, 1

0, 1

q0

0

q1 1

1 0

{q0 }

1

q2

0

q3

0

0 1

{q0 , q1 }

0

{q0 , q2 }

1

0 {q0 , q2 , q5 }

0 1

{q0 , q6 } 1

1 1

0 {q0 , q1 , q6 }

1

q4

q5

0

q6

{q0 , q1 , q3 } 0 {q0 , q1 , q4 }

0 0 1

{q0 , q1 , q4 , q6 } 1 {q0 , q2 , q5 , q6 }

0

0

{q0 , q1 , q3 , q6 } 0 1 {q0 , q2 , q6 }

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 quintupla M = (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 qj

ε

qk

ε

qs

ql

a

qm

ε

qn

a

qt

ε

qw

a qi

ε

ε qr

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 0

q0

2

1 ε

q1

ε

q2

Modelos de Computación ITema 2: Autómatas Finitos– p.30/88

Ejemplo 0

q0

2

1 ε

q1

ε

q2

El lenguaje aceptado es L = {0i 1 j 2k : i, j, k ≥ 0}.

Modelos de Computación ITema 2: Autómatas Finitos– p.30/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b

q3

Modelos de Computación ITema 2: Autómatas Finitos– p.31/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b

q3 El lenguaje generado es L = {ai b2 j ck : 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.

0, 1 q0 0 0, 1 p0 1

0, 1 q1

1

q2

1

q3

0

q4 0, 1

p1

0

p2

0

p3

0

p4

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.

0, 1 q0 0 r0

0, 1 p0 1

0, 1 q1

1

q2

1

q3

0

q4 0, 1

p1

0

p2

0

p3

0

p4

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.

ε r0

ε

0, 1 q0 0 0, 1 p0 1

0, 1 q1

1

q2

1

q3

0

q4 0, 1

p1

0

p2

0

p3

0

p4

Modelos de Computación ITema 2: Autómatas Finitos– p.32/88

PROCESO DE CALCULO Para un Autómata Finito con Transiciones Nulas 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, u) ` (p, v)) si y solo si se da una de las condiciones ((u = av) ∧ p ∈ δ(q, a)) ((u = v) ∧ p ∈ δ(q, ε))

(caso: ((q, av) ` (p, v))) (caso: ((q, v) ` (p, v)))

De una configuración se puede pasar a varias configuraciones distintas en un paso de cálculo, e incluso a ninguna. 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 de configuraciones 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ómata no determinista con transiciones nulas M que acepta el mismo lenguaje: L(M) = L(M) Es inmediato: sería un autómata en el que para cada símbolo del alfabeto de entrada hay siempre una opción y / para cada estado δ(q, ε) = 0.

Modelos de Computación ITema 2: Autómatas Finitos– p.35/88

AFD ↔ ε-AFND Dado un autómata finito determinista M existe un autómata no determinista con transiciones nulas M que acepta el mismo lenguaje: L(M) = L(M) Es inmediato: sería un autómata en el que para cada símbolo del alfabeto de entrada hay siempre una opción y / para cada estado δ(q, ε) = 0. Dado un autómata finito no determinista con transiciones nulas M existe un autómata finito determinista M que acepta el mismo lenguaje: L(M) = L(M)

Modelos de Computación ITema 2: Autómatas Finitos– p.35/88

Ejemplo 0 q0

2

1 ε

q1

ε

q2

{q0 , q1 , q2 }

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 }

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 }

1

{q1 , q2 }

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 }

1

{q1 , q2 }

2 {q2 }

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 }

1

{q1 , q2 }

2 {q2 }

0 0/

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 }

1 1

{q1 , q2 }

2 {q2 }

0 0/

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 } 2 {q2 }

1 1

{q1 , q2 } 0

2 0/

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 } 2 {q2 }

1 1

2 0, 1

{q1 , q2 } 0 0/

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 } 2

1 1

2 0, 1

{q2 }

{q1 , q2 } 0 0/

2

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 } 2

1 1

2 0, 1

{q2 } 2

{q1 , q2 } 0 0/ 0, 1, 2

Modelos de Computación ITema 2: Autómatas Finitos– p.36/88

Ejemplo 0 q0

2

1 ε

ε

q1

q2

0 {q0 , q1 , q2 } 2

1 1

2 0, 1

{q2 } 2

{q1 , q2 } 0 0/ 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) =

S

q∈P Cl(q)

Autómata Finito Determinista M = (Q, A, δ, q0 , F) Q = ℘(Q) δ(P, a) = Cl( q0 = Cl(q0 )

S

q∈P δ(q, a))

/ F = {P : P ∩ F 6= 0} Modelos de Computación ITema 2: Autómatas Finitos– p.37/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

{q0 , q1 , q2 }

Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

{q0 , q1 , q2 } a {q1 , q2 }

Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

{q0 , q1 , q2 }

b

{q3 }

a {q1 , q2 }

Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

{q0 , q1 , q2 } a {q1 , q2 }

b

{q3 }

c {q2 }

Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

{q0 , q1 , q2 } a {q1 , q2 }

b

{q3 }

c {q2 }

0/

a Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

b {q0 , q1 , q2 } a {q1 , q2 }

b

{q3 }

c {q2 }

0/

a Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

b b

{q0 , q1 , q2 } a {q1 , q2 }

{q3 }

c c

{q2 }

0/

a Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

b b

{q0 , q1 , q2 } a {q1 , q2 }

{q3 } a, c

c c

{q2 }

0/

a Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

b b b

{q0 , q1 , q2 } a {q1 , q2 }

{q3 } a, c

c c

{q2 }

0/

a Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

b b b

{q0 , q1 , q2 } a {q1 , q2 }

{q3 }

c

a, c

c

a, b, c

{q2 }

0/

a Modelos de Computación ITema 2: Autómatas Finitos– p.38/88

Ejemplo q0

a, ε

c, ε

q1 b

q2

b q3

b b b

{q0 , q1 , q2 } a {q1 , q2 }

{q3 }

c

a, c

c

a, b, c

{q2 }

a, b, c 0/

a 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 la siguiente 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 S entonces 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 lenguaje RS. 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

Modelos de Computación ITema 2: Autómatas Finitos– p.40/88

Ejemplos A = {0, 1} 00 El conjunto {00}

Modelos de Computación ITema 2: Autómatas Finitos– p.40/88

Ejemplos A = {0, 1} 00 El conjunto {00} 01∗ + 0

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 una sucesión de unos.

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 una sucesión de unos. (1 + 10)∗

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 una sucesión de unos. (1 + 10)∗ Conjunto de palabras en las que los ceros están precedidos siempre por unos

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 una sucesión de unos. (1 + 10)∗ Conjunto de palabras en las que los ceros están precedidos siempre por unos (0 + 1)∗ 011

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 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

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 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∗

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 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

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 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∗

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 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

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 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 - Alfabeto {0, 1} Construir una expresión regular para las palabras con un número par de ceros.

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 de ceros. 1∗ (01∗ 01∗ )∗

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 de ceros. 1∗ (01∗ 01∗ )∗ Construir una expresión regular para las palabras que contengan a 0110 como subcadena.

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 de ceros. 1∗ (01∗ 01∗ )∗ Construir una expresión regular para las palabras que contengan a 0110 como subcadena. (0 + 1)∗ 0110(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 de ceros. 1∗ (01∗ 01∗ )∗ Construir una expresión regular para las palabras que contengan a 0110 como subcadena. (0 + 1)∗ 0110(0 + 1)∗ Construir una expresión regular para el conjunto de palabras que empiezan por 000 y después no aparece nunca más esta cadena.

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 de ceros. 1∗ (01∗ 01∗ )∗ Construir una expresión regular para las palabras que contengan a 0110 como subcadena. (0 + 1)∗ 0110(0 + 1)∗ Construir una expresión regular para el conjunto de palabras que empiezan por 000 y después no aparece nunca más esta cadena. (000)(1 + 10 + 100)∗

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 de ceros. 1∗ (01∗ 01∗ )∗ Construir una expresión regular para las palabras que contengan a 0110 como subcadena. (0 + 1)∗ 0110(0 + 1)∗ Construir una expresión regular para el conjunto de palabras que empiezan por 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 a 000 o a 101 como subcadena

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 de ceros. 1∗ (01∗ 01∗ )∗ Construir una expresión regular para las palabras que contengan a 0110 como subcadena. (0 + 1)∗ 0110(0 + 1)∗ Construir una expresión regular para el conjunto de palabras que empiezan por 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 a 000 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

9.

(r1 + r2 )r3 = r1 r3 + r2 r3

2. r1 + (r2 + r3 ) = (r1 + r2 ) + r3

10.

r+ + ε = r ∗

3. r1 (r2 r3 ) = (r1 r2 )r3

11.

r∗ + ε = r ∗

12.

(r + ε)∗ = r∗

13.

(r + ε)+ = r∗

14.

(r∗1 + r∗2 )∗ = (r1 + r2 )∗

15.

(r∗1 r∗2 )∗ = (r1 + r2 )∗

4. rε = r 5. r0/ = 0/ 6. r + 0/ = r 7. ε∗ = ε 8. r1 (r2 + r3 ) = r1 r2 + r1 r3

Modelos de Computación ITema 2: Autómatas Finitos– p.42/88

Equivalencia Autómatas - Expresiones Regular La familia de los lenguajes aceptados por los autómatas finitos coincide con la familia de lenguajes que pueden representarse mediante expresiones regulares. Esto se demostrará comprobando: Dada una expresión regular, existe un autómata que acepta el mismo lenguaje que el representado por la expresión regular. Dado un autómata finito existe siempre una expresión regular que representa el lenguaje aceptado por el autómata. La primera transformación es más útil, ya que inicialmente los lenguajes se representan mediante expresiones regulares 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 lenguaje asociado a esta expresión regular.

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 lenguaje asociado 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:

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 lenguaje asociado 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/

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 lenguaje asociado 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

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 lenguaje asociado 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

ε

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 lenguaje asociado 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

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 lenguaje asociado 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

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 lenguaje asociado 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

a

q1

Modelos de Computación ITema 2: Autómatas Finitos– p.44/88

Autómatas Compuestos: Unión Si M1 es el autómata que acepta el mismo lenguaje que el representado por r1 y M2 el que acepta el mismo lenguaje que el de r2 , entonces Unión (r1 + r2 )

q11 q01 qi1

q12 q02 q j2

M1 M2

Modelos de Computación ITema 2: Autómatas Finitos– p.45/88

Autómatas Compuestos: Unión Si M1 es el autómata que acepta el mismo lenguaje que el representado por r1 y M2 el que acepta el mismo lenguaje que el de r2 , entonces Unión (r1 + r2 )

q11 q01 qi1

M1

q0 q12 q02 q j2

M2

Modelos de Computación ITema 2: Autómatas Finitos– p.45/88

Autómatas Compuestos: Unión Si M1 es el autómata que acepta el mismo lenguaje que el representado por r1 y M2 el que acepta el mismo lenguaje que el de r2 , entonces Unión (r1 + r2 )

q11 q01

ε q0

qi1 ε

q12 q02 q j2

M1 M2

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 la siguiente forma. Si M1 = (Q1 , A, δ1 , q10 , F1 ) y M2 = (Q2 , A, δ2 , q20 , F2 ) / entonces el autómata que acepta la unión es con Q1 ∩ Q2 = 0, M = (Q, A, δ, q0 , F) donde

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 la siguiente forma. Si M1 = (Q1 , A, δ1 , q10 , F1 ) y M2 = (Q2 , A, δ2 , q20 , F2 ) / entonces el autómata que acepta la unión es con Q1 ∩ Q2 = 0, M = (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 , ε) = {q10 , q20 } F = F1 ∪ F2 Modelos 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 (r1 r2 ) es

q11 q01

q12 q02 q j2

qi1

M1

M2 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 (r1 r2 ) es

q11 q01

q12 q02 q j2

qi1

M1

M2 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 (r1 r2 ) es

q11 q01

q12

ε ε

q02 q j2

qi1

M1

M2 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 expresar de la siguiente forma. Si M1 = (Q1 , A, δ1 , q10 , F1 ) y / entonces el autómata que M2 = (Q2 , A, δ2 , q20 , F2 ) con Q1 ∩ Q2 = 0, acepta la concatenación es M = (Q, A, δ, q0 , F) donde:

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 expresar de la siguiente forma. Si M1 = (Q1 , A, δ1 , q10 , F1 ) y / entonces el autómata que M2 = (Q2 , A, δ2 , q20 , F2 ) con Q1 ∩ Q2 = 0, acepta 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, ε) ∪ {q20 } 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

q11 q01 qi1

M1

Modelos de Computación ITema 2: Autómatas Finitos– p.50/88

Autómatas Compuestos: Clausura Clausura: El autómata para r∗1 es

ε q11 q01 qi1

M1

ε

Modelos de Computación ITema 2: Autómatas Finitos– p.50/88

Autómatas Compuestos: Clausura Clausura: El autómata para r∗1 es

ε

q0

ε

q11 q01 qi1

M1

ε

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:

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 , ε) = {q10 } 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 el asociado a la expresión regular (0 + 10)∗ 011

Modelos de Computación ITema 2: Autómatas Finitos– p.52/88

Ejemplo Encontrar un autómata que acepte el mismo lenguaje que el asociado a la expresión regular (0 + 10)∗ 011

q1

1

q2

1

Modelos de Computación ITema 2: Autómatas Finitos– p.52/88

Ejemplo Encontrar un autómata que acepte el mismo lenguaje que el asociado a la expresión regular (0 + 10)∗ 011

q1

1

q2

1

q3

0

q4

0

Modelos de Computación ITema 2: Autómatas Finitos– p.52/88

Ejemplo Encontrar un autómata que acepte el mismo lenguaje que el asociado a la expresión regular (0 + 10)∗ 011

q1

1

q2

ε

q3

0

q4

10

Modelos de Computación ITema 2: Autómatas Finitos– p.52/88

Ejemplo Encontrar un autómata que acepte el mismo lenguaje que el asociado a la expresión regular (0 + 10)∗ 011 0

q5

q1

1

q2

ε

q6

q3

0

0

q4

10

Modelos de Computación ITema 2: Autómatas Finitos– p.52/88

Ejemplo Encontrar un autómata que acepte el mismo lenguaje que el asociado a la expresión regular (0 + 10)∗ 011 0

q5

ε

0+10

q6

q7 ε

q1

1

q2

ε

q3

0

q4

Modelos de Computación ITema 2: Autómatas Finitos– p.52/88

Ejemplo Encontrar un autómata que acepte el mismo lenguaje que el asociado a la expresión regular (0 + 10)∗ 011 ε ε

q8

ε

0

q5

(0 + 10)∗ q6

q7 ε

q1

1

q2

ε

q3

0

q4

ε

Modelos de Computación ITema 2: Autómatas Finitos– p.52/88

Ejemplo Encontrar un autómata que acepte el mismo lenguaje que el asociado a la expresión regular (0 + 10)∗ 011 ε ε

q8

ε

0

q5

(0 + 10)∗ q6

q7

q9 ε

q1

1

q2

ε

q3

0

0

q10

ε

q11

1

q12

ε

q13

1

q14

011 q4

ε

Modelos de Computación ITema 2: Autómatas Finitos– p.52/88

Ejemplo Encontrar un autómata que acepte el mismo lenguaje que el asociado a la expresión regular (0 + 10)∗ 011 ε ε

q8

ε

0

q5

q6

ε

q7

q9 ε

q1

1

q2

ε

q3

0

ε

q4

0

q10

ε

q11

1

q12

ε

q13

1

q14

(0 + 10)∗ 011 Autómata Resultado

ε ε

Modelos de Computación ITema 2: Autómatas Finitos– p.52/88

Autómata → Expresión Regular Si L es aceptado por un autómata finito determinista, entonces puede venir expresado mediante una expresión regular. Sea el autómata M = (Q, A, δ, q1 , F), Q = {q1 , . . . , qn } y q1 es el estado inicial. Sea Rkij el conjunto de las cadenas de A∗ que premiten pasar del estado qi al estado q j y no pasa por ningún estado intermedio de numeración mayor que k (qi y q j si pueden tener numeración mayor que k). Rkij se puede definir de forma recursiva: R0i j

=

(

{a : δ(qi , a) = q j } {a : δ(qi , a) = qi } ∪ {ε}

si i 6= j si i = j

Modelos de Computación ITema 2: Autómatas Finitos– p.53/88

Demostración Para k ≥ 1, tenemos que Rkij está compuesto de dos tipos de palabras: Palabras que para ir de qi a q j no pasan por qk : pertenecen a Rk−1 ij Palabras que para ir de qi a q j pasan por qk . Una palabra de este lenguaje está compuesta de tres partes:

Modelos de Computación ITema 2: Autómatas Finitos– p.54/88

Demostración Para k ≥ 1, tenemos que Rkij está compuesto de dos tipos de palabras: Palabras que para ir de qi a q j no pasan por qk : pertenecen a Rk−1 ij Palabras que para ir de qi a q j pasan por qk . Una palabra de este lenguaje está compuesta de tres partes:

qi

x ∈ Rk−1 ik

qk

Modelos de Computación ITema 2: Autómatas Finitos– p.54/88

Demostración Para k ≥ 1, tenemos que Rkij está compuesto de dos tipos de palabras: Palabras que para ir de qi a q j no pasan por qk : pertenecen a Rk−1 ij Palabras que para ir de qi a q j pasan por qk . Una palabra de este lenguaje está compuesta de tres partes:

qi

x ∈ Rk−1 ik

... qk

Modelos de Computación ITema 2: Autómatas Finitos– p.54/88

Demostración Para k ≥ 1, tenemos que Rkij está compuesto de dos tipos de palabras: Palabras que para ir de qi a q j no pasan por qk : pertenecen a Rk−1 ij Palabras que para ir de qi a q j pasan por qk . Una palabra de este lenguaje está compuesta de tres partes: k−1 y1 ∈ Rk−1 y ∈ R m kk . . . kk x ∈ Rk−1 ik qi qk

Modelos de Computación ITema 2: Autómatas Finitos– p.54/88

Demostración Para k ≥ 1, tenemos que Rkij está compuesto de dos tipos de palabras: Palabras que para ir de qi a q j no pasan por qk : pertenecen a Rk−1 ij Palabras que para ir de qi a q j pasan por qk . Una palabra de este lenguaje está compuesta de tres partes: k−1 y1 ∈ Rk−1 y ∈ R m kk . . . kk k−1 k−1 z ∈ R x ∈ Rik kj qj qi qk

Modelos de Computación ITema 2: Autómatas Finitos– p.54/88

Demostración k−1 y1 ∈ Rk−1 y ∈ R kk . . . m kk k−1 k−1 z ∈ R x ∈ Rik kj qj qi qk

Modelos de Computación ITema 2: Autómatas Finitos– p.55/88

Demostración k−1 y1 ∈ Rk−1 y ∈ R kk . . . m kk k−1 k−1 z ∈ R x ∈ Rik kj qj qi qk


k−1 ∗ Rkk ,

Como la palabra y1 . . . ym ∈ entonces la palabra completa está en
k−1 k−1 ∗ k−1 Rik Rkk Rk j

Modelos de Computación ITema 2: Autómatas Finitos– p.55/88

Demostración k−1 y1 ∈ Rk−1 y ∈ R kk . . . m kk k−1 k−1 z ∈ R x ∈ Rik kj qj qi qk


k−1 ∗ Rkk ,

Como la palabra y1 . . . ym ∈ entonces la palabra completa está en
k−1 k−1 ∗ k−1 Rik Rkk Rk j Uniendo las dos partes, obtenemos: Rkij

=

k−1 Rk−1 ∪ R ij ik


k−1 ∗ k−1 Rkk Rk j Modelos de Computación ITema 2: Autómatas Finitos– p.55/88

Demostración Expresión regular asociada a Rkij −→ rkij Para k = 0 es inmediato. (

si i 6= j a1 + . . . + a l = a1 + . . . + 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 rkij , calculadas las rk−1 ij r0ij

k−1 k−1 ∗ k−1 Rkij = Rk−1 ∪ R ij ik (Rkk ) Rk j

−→

k−1 k−1 ∗ k−1 rk−1 + r ij ik (rkk ) rkj 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) =

[

Rn1 j

q j ∈F

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 1 q1

0 0

q2

1

q3

0, 1

Modelos de Computación ITema 2: Autómatas Finitos– p.58/88

Ejemplo 1 q1

0 0

q2

1

q3

0, 1

0 =ε r11 0 =0 r12 0 =1 r13 0 =0 r21 0 =ε r22 0 =1 r23 0 =0 / r31 0 = 0+1 r32 0 =ε r33 Modelos de Computación ITema 2: Autómatas Finitos– p.58/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                                   Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

 1 0 0 0 ∗ 0  = r + r (r ) r r  11 11 11 11 11                                

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

 1 0 0 0 ∗ 0 ∗  = r + r (r ) r = ε + ε(ε) ε r  11 11 11 11 11                                

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

 1 0 0 0 ∗ 0 ∗  = r + r (r ) r = ε + ε(ε) ε = ε r  11 11 11 11 11                                

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

 1 0 0 0 ∗ 0 ∗  = r + r (r ) r = ε + ε(ε) ε = ε r  11 11 11 11 11    1 0 0 0 ∗ 0  r = r + r (r ) r12  12 12 11 11                           

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

 1 0 0 0 ∗ 0 ∗  = r + r (r ) r = ε + ε(ε) ε = ε r  11 11 11 11 11    1 0 0 0 ∗ 0 ∗  r = r + r (r ) r = 0 + ε(ε) 0  12 12 11 11 12                           

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

 1 0 0 0 ∗ 0 ∗  = r + r (r ) r = ε + ε(ε) ε = ε r  11 11 11 11 11    1 0 0 0 ∗ 0 ∗  r = r + r (r ) r = 0 + ε(ε) 0=0  12 12 11 11 12                           

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

 1 0 0 0 ∗ 0 ∗  = r + r (r ) r = ε + ε(ε) ε = ε r  11 11 11 11 11    1 0 0 0 ∗ 0 ∗  r = r + r (r ) r = 0 + ε(ε) 0=0  12 12 11 11 12   1 0 0 0 ∗ 0 ∗   r = r + r (r ) r = 1 + ε(ε) 1  13 13 11 11 13                      

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

 1 0 0 0 ∗ 0 ∗  = r + r (r ) r = ε + ε(ε) ε = ε r  11 11 11 11 11    1 0 0 0 ∗ 0 ∗  r = r + r (r ) r = 0 + ε(ε) 0=0  12 12 11 11 12   1 0 0 0 ∗ 0 ∗   r = r + r (r ) r = 1 + ε(ε) 1=1  13 13 11 11 13                      

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                 

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε

                 Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                 

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0

                 Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                 

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0

                 Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                 

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0 = ε + 00

                 Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                                  

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0 = ε + 00 1 0 0 0 ∗ 0 r23 = r23 + r21 (r11 ) r13 = 1 + 0(ε)∗ 1

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                                  

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0 = ε + 00 1 0 0 0 ∗ 0 r23 = r23 + r21 (r11 ) r13 = 1 + 0(ε)∗ 1 = 1 + 01

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                                  

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0 = ε + 00 1 0 0 0 ∗ 0 r23 = r23 + r21 (r11 ) r13 = 1 + 0(ε)∗ 1 = 1 + 01 1 0 0 0 ∗ 0 / ∗ε r31 = r31 + r31 (r11 ) r11 = 0/ + 0(ε)

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                                  

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0 = ε + 00 1 0 0 0 ∗ 0 r23 = r23 + r21 (r11 ) r13 = 1 + 0(ε)∗ 1 = 1 + 01 1 0 0 0 ∗ 0 / ∗ ε = 0/ r31 = r31 + r31 (r11 ) r11 = 0/ + 0(ε)

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                                  

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0 = ε + 00 1 0 0 0 ∗ 0 r23 = r23 + r21 (r11 ) r13 = 1 + 0(ε)∗ 1 = 1 + 01 1 0 0 0 ∗ 0 / ∗ ε = 0/ r31 = r31 + r31 (r11 ) r11 = 0/ + 0(ε) 1 0 0 0 ∗ 0 / ∗0 r32 = r32 + r31 (r11 ) r12 = 0 + 1 + 0(ε)

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                                  

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0 = ε + 00 1 0 0 0 ∗ 0 r23 = r23 + r21 (r11 ) r13 = 1 + 0(ε)∗ 1 = 1 + 01 1 0 0 0 ∗ 0 / ∗ ε = 0/ r31 = r31 + r31 (r11 ) r11 = 0/ + 0(ε) 1 0 0 0 ∗ 0 / ∗0 = 0 + 1 r32 = r32 + r31 (r11 ) r12 = 0 + 1 + 0(ε)

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                                  

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0 = ε + 00 1 0 0 0 ∗ 0 r23 = r23 + r21 (r11 ) r13 = 1 + 0(ε)∗ 1 = 1 + 01 1 0 0 0 ∗ 0 / ∗ ε = 0/ r31 = r31 + r31 (r11 ) r11 = 0/ + 0(ε) 1 0 0 0 ∗ 0 / ∗0 = 0 + 1 r32 = r32 + r31 (r11 ) r12 = 0 + 1 + 0(ε) 1 0 0 0 ∗ 0 / ∗1 r33 = r33 + r31 (r11 ) r13 = ε + 0(ε)

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo                                   

0 r11 =ε 0 r12 =0 0 r13 =1 0 r21 =0 0 r22 =ε 0 r23 =1 0 r31 = 0/ 0 = 0+1 r32 0 r33 =ε

                                  

1 0 0 0 ∗ 0 = r11 + r11 (r11 ) r11 = ε + ε(ε)∗ ε = ε r11 1 0 0 0 ∗ 0 r12 = r12 + r11 (r11 ) r12 = 0 + ε(ε)∗ 0 = 0 1 0 0 0 ∗ 0 r13 = r13 + r11 (r11 ) r13 = 1 + ε(ε)∗ 1 = 1 1 0 0 0 ∗ 0 r21 = r21 + r21 (r11 ) r11 = 0 + 0(ε)∗ ε = 0 1 0 0 0 ∗ 0 r22 = r22 + r21 (r11 ) r12 = ε + 0(ε)∗ 0 = ε + 00 1 0 0 0 ∗ 0 r23 = r23 + r21 (r11 ) r13 = 1 + 0(ε)∗ 1 = 1 + 01 1 0 0 0 ∗ 0 / ∗ ε = 0/ r31 = r31 + r31 (r11 ) r11 = 0/ + 0(ε) 1 0 0 0 ∗ 0 / ∗0 = 0 + 1 r32 = r32 + r31 (r11 ) r12 = 0 + 1 + 0(ε) 1 0 0 0 ∗ 0 / ∗1 = ε r33 = r33 + r31 (r11 ) r13 = ε + 0(ε)

Modelos de Computación ITema 2: Autómatas Finitos– p.59/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0  r11  11 12 22 21                                                                  

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗  r11  11 12 22 21                                                                  

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗  r11  11 12 22 21    2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00)  r  12 12 12 22 22                                                             

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗  r11  11 12 22 21    2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗  r  12 12 12 22 22                                                             

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗  r11  11 12 22 21    2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗  r  12 12 12 22 22     2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01)  r  13 13 12 22 23                                                       

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗  r11  11 12 22 21    2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗  r  12 12 12 22 22     2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1  r  13 13 12 22 23                                                       

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                                                    

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 r21 21 22 22 21

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                                                    

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                                                    

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) r22 22 22 22 22

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                                                    

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) = r22 22 22 22 22

(00)∗

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                                                    

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) = r22 22 22 22 22

(00)∗ 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 01 + (ε + 00)(ε + 00)∗ (1 + 01) r23 23 22 22 23

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                                                    

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) = r22 22 22 22 22

(00)∗ 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 01 + (ε + 00)(ε + 00)∗ (1 + 01) = r23 23 22 22 23

0∗ 1

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                  

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) = r22 22 22 22 22

(00)∗ 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 01 + (ε + 00)(ε + 00)∗ (1 + 01) = r23 23 22 22 23

 0∗ 1      2 = r 1 + r 1 (r 1 )∗ r 1 = 0 ∗0  / r + (0 + 1)(ε + 00)  31 31 32 22 21                          

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                  

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) = r22 22 22 22 22

(00)∗ 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 01 + (ε + 00)(ε + 00)∗ (1 + 01) = r23 23 22 22 23

 0∗ 1      2 = r 1 + r 1 (r 1 )∗ r 1 = 0 ∗0 =  / r + (0 + 1)(ε + 00)  31 31 32 22 21      (0 + 1)(00)∗ 0                     

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                  

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) = r22 22 22 22 22

(00)∗ 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 01 + (ε + 00)(ε + 00)∗ (1 + 01) = r23 23 22 22 23

      2 = r 1 + r 1 (r 1 )∗ r 1 =  r  31 31 32 22 21          2 = r 1 + r 1 (r 1 )∗ r 1 =  r  32 32 32 22 22               

0∗ 1 0/ + (0 + 1)(ε + 00)∗ 0 = (0 + 1)(00)∗ 0 0 + 1 + (0 + 1)(ε + 00)∗ (ε + 00)

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                  

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) = r22 22 22 22 22

(00)∗ 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 01 + (ε + 00)(ε + 00)∗ (1 + 01) = r23 23 22 22 23

      2 = r 1 + r 1 (r 1 )∗ r 1 =  r  31 31 32 22 21          2 = r 1 + r 1 (r 1 )∗ r 1 =  r  32 32 32 22 22               

0∗ 1 0/ + (0 + 1)(ε + 00)∗ 0 = (0 + 1)(00)∗ 0 0 + 1 + (0 + 1)(ε + 00)∗ (ε + 00) = (0 + 1)(00)∗

Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                  

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) = r22 22 22 22 22

(00)∗ 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 01 + (ε + 00)(ε + 00)∗ (1 + 01) = r23 23 22 22 23

      2 = r 1 + r 1 (r 1 )∗ r 1 =  r  31 31 32 22 21          2 = r 1 + r 1 (r 1 )∗ r 1 =  r  32 32 32 22 22           2 = r 1 + r 1 (r 1 )∗ r 1 =  r33  33 32 22 23   

0∗ 1 0/ + (0 + 1)(ε + 00)∗ 0 = (0 + 1)(00)∗ 0 0 + 1 + (0 + 1)(ε + 00)∗ (ε + 00) = (0 + 1)(00)∗ ε + (0 + 1)(ε + 00)∗ (1 + 01) Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo

                    

1 =ε r11 1 =0 r12 1 =1 r13 1 =0 r21 1 = ε + 00 r22

   1 = 1 + 01  r  23     1 =0  / r  31    1 = 0+1   r32     1 r33 = ε

                                  

2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 0(ε + 00)∗ 0 = (00)∗ r11 11 12 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + 0(ε + 00)∗ (ε + 00) = 0(00)∗ r12 12 12 22 22 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 0(ε + 00)∗ (1 + 01) = 0∗ 1 r13 13 12 22 23 2 = r 1 + r 1 (r 1 )∗ r 1 = 0 + (ε + 00)(ε + 00)∗ 0 = (00)∗ 0 r21 21 22 22 21 2 = r 1 + r 1 (r 1 )∗ r 1 = ε + 00 + (ε + 00)(ε + 00)∗ (ε + 00) = r22 22 22 22 22

(00)∗ 2 = r 1 + r 1 (r 1 )∗ r 1 = 1 + 01 + (ε + 00)(ε + 00)∗ (1 + 01) = r23 23 22 22 23

      2 = r 1 + r 1 (r 1 )∗ r 1 =  r  31 31 32 22 21          2 = r 1 + r 1 (r 1 )∗ r 1 =  r  32 32 32 22 22           2 = r 1 + r 1 (r 1 )∗ r 1 =  r33  33 32 22 23   

0∗ 1 0/ + (0 + 1)(ε + 00)∗ 0 = (0 + 1)(00)∗ 0 0 + 1 + (0 + 1)(ε + 00)∗ (ε + 00) = (0 + 1)(00)∗ ε + (0 + 1)(ε + 00)∗ (1 + 01) = ε + (0 + 1)0∗ 1 Modelos de Computación ITema 2: Autómatas Finitos– p.60/88

Ejemplo 2 = (00)∗ r11 2 = 0(00)∗ r12 2 = 0∗ 1 r13 2 = (00)∗ 0 r21 2 = (00)∗ r22 2 = 0∗ 1 r23 2 = (0 + 1)(00)∗ 0 r31 2 = (0 + 1)(00)∗ r32 2 = ε + (0 + 1)0∗ 1 r33

Finalmente la expresión regular para el lenguaje aceptado es: 3 + r3 = r12 13

Modelos de Computación ITema 2: Autómatas Finitos– p.61/88

Ejemplo 2 = (00)∗ r11 2 = 0(00)∗ r12 2 = 0∗ 1 r13 2 = (00)∗ 0 r21 2 = (00)∗ r22 2 = 0∗ 1 r23 2 = (0 + 1)(00)∗ 0 r31 2 = (0 + 1)(00)∗ r32 2 = ε + (0 + 1)0∗ 1 r33

Finalmente la expresión regular para el lenguaje aceptado es: 3 + r 3 = r 2 + r 2 (r 2 )∗ r 2 + r 2 + r 2 (r 2 )∗ r 2 = r12 12 13 33 32 13 13 33 33 13

Modelos de Computación ITema 2: Autómatas Finitos– p.61/88

Ejemplo 2 = (00)∗ r11 2 = 0(00)∗ r12 2 = 0∗ 1 r13 2 = (00)∗ 0 r21 2 = (00)∗ r22 2 = 0∗ 1 r23 2 = (0 + 1)(00)∗ 0 r31 2 = (0 + 1)(00)∗ r32 2 = ε + (0 + 1)0∗ 1 r33

Finalmente la expresión regular para el lenguaje aceptado es: 3 + r 3 = r 2 + r 2 (r 2 )∗ r 2 + r 2 + r 2 (r 2 )∗ r 2 = r12 12 13 33 32 13 13 33 33 13

0(00)∗ + 0∗ 1(ε + (0 + 1)0∗ 1)∗ (0 + 1)(00)∗ + 0∗ 1 + 0∗ 1(ε + (0 + 1)0∗ 1)∗ (ε + (0 + 1)0∗ 1) =

Modelos de Computación ITema 2: Autómatas Finitos– p.61/88

Ejemplo 2 = (00)∗ r11 2 = 0(00)∗ r12 2 = 0∗ 1 r13 2 = (00)∗ 0 r21 2 = (00)∗ r22 2 = 0∗ 1 r23 2 = (0 + 1)(00)∗ 0 r31 2 = (0 + 1)(00)∗ r32 2 = ε + (0 + 1)0∗ 1 r33

Finalmente la expresión regular para el lenguaje aceptado es: 3 + r 3 = r 2 + r 2 (r 2 )∗ r 2 + r 2 + r 2 (r 2 )∗ r 2 = r12 12 13 33 32 13 13 33 33 13

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 Caracteres Normales +, ∗ | [. . .] [a − b] [^. . .] ? {nombre} {n} {n, m} ∗ ". . ." ^,$

Significado Ellos mismos Superíndices +,* La unión de los lenguajes Cualquier símbolo entre corchetes todos los caracteres entre a y b El complementario de [. . .] 0 ó 1 repetición de lo anterior Se substituye la e.r. nombre n repeticiones de la anterior e.r. 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 nombre2 nombrei %%

er1 er2 eri declaglobal1 declaglobal2 declalocal1 declalocal2 accion1; accion2; accion3;

er1 er2 er3 %% 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 ejecuta las acciones. main() – Programa principal. Por defecto sólo llama a yylex(). Se puede redefinir después de los últimos % % yywrap() – Función que se ejecuta cuando yylex() encuentra un fin de fichero. 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 digito signo suc enter real1 real2 int

[a-zA-Z] [0-9] (\-|\+) ({digito}+) ({signo}?{suc}) ({enter}\.{digito}*) ({signo}?\.{suc}) ent=0, real=0, ident=0, sumaent=0;

int

i;

%% {enter}

{ent++; sscanf(yytext,"%d",&i); sumaent += i; printf("Numero entero %s\n",yytext);} {real++; printf("Num. real %s\n",yytext);} {ident++; printf("identificador %s\n",yytext);} {;}

({real1}|{real2}) {car}({car}|{digito})* .|\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 o números de teléfono en páginas web). Fueron centrales en el desarrollo de Unix: K. Thompson (1968) Regular expressions search algorithms. Comm. ACM. 11, 419–422. Existen intrucciones como grep: ’Global (Searh for) Regular Expressions and Print’ K. Thompson está desarrollando un sistema de comunicaciones para teléfonos basado en máquinas de estado finito, desarrollando un lenguaje para crear las má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 en http://www.4guysfromrolla.com/webtech/120400-1.shtml contiene 4 aplicaciones de expresiones regulares, desde verificación de direcciones de correo electró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 en navegadores. Podeis leer un artículo sobre expresiones regulares y Java en: http://developer.java.sun.com/developer/technicalArticles/releases/1.4regex/ En la dirección http://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 tienen la forma A → uB 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 tienen la forma A → uB A→u Lineales por la izquierda.- Cuando todas las producciones tienen la 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→ε

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)∗

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ómata Si L es un lenguaje generado por una gramática regular, entonces existe un autómata finito determinista que lo reconoce. L es un lenguaje generado por la gramática G = (V, T, P, S) lineal por la derecha. 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:

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] 1 [10A]

0

ε

[A] ε [ε]

Modelos de Computación ITema 2: Autómatas Finitos– p.72/88

Gramáticas Lineales por la Izquierda Gramática lineal por la izquierda, G = (V, T, P, S) 1. Consideraremos la gramática G0 = (V, T, P0 , S) donde P0 = {A → α : A → α−1 ∈ P} Es inmediato que L(G0 ) = L(G)−1 . 2. Sea M 0 el autómata finito no-determinista que acepta el lenguaje L(G0 ). 3. Calcular M a partir de M 0 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 )

0 −1

= L(G )

0 −1

= L(G)


−1 −1

= L(G)

Modelos de Computación ITema 2: Autómatas Finitos– p.73/88

Ejemplo S → S10, S→0 Para construir un AFND con transiciones nulas que acepte este lenguaje se dan los siguientes pasos:

Modelos de Computación ITema 2: Autómatas Finitos– p.74/88

Ejemplo S → S10, S→0 Para construir un AFND con transiciones nulas que acepte este lenguaje se dan los siguientes pasos: Invertir la parte derecha de las producciones: S → 01S S→0

Modelos de Computación ITema 2: Autómatas Finitos– p.74/88

Ejemplo S → S10, S→0 Para construir un AFND con transiciones nulas que acepte este lenguaje se dan los siguientes pasos: Invertir la parte derecha de las producciones: S → 01S S→0 Construir el AFND con transiciones nulas asociado [S] 1 [1S]

ε

[0]

0

[ε]

ε

0

[01S] Modelos de Computación ITema 2: Autómatas Finitos– p.74/88

Ejemplo Cont. [S] 1 [1S]

ε

[0]

0

[ε]

ε

0

[01S]

Modelos de Computación ITema 2: Autómatas Finitos– p.75/88

Ejemplo Cont. ε

[S]

0

[0]

[ε]

ε

1 [1S]

[01S]

0

Invertimos el autómata [S]

ε

[ε]

ε

1 [1S]

[0]

0

0

[01S] 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 L puede generarse mediante una gramática lineal por la derecha y por una lineal por la izquierda.

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 L puede generarse mediante una gramática lineal por la derecha y por una lineal por la izquierda. Sea L = L(M) donde M = (Q, A, δ, q, F) es un autómata finito determinista. La gramática lineal por la derecha es G = (Q, A, P, q0 ) donde las variables son los estados, la variable inicial es q0 y P contiene las producciones, p → aq, si δ(p, a) = q p → ε,

si p ∈ F

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 L puede generarse mediante una gramática lineal por la derecha y por una lineal por la izquierda. Sea L = L(M) donde M = (Q, A, δ, q, F) es un autómata finito determinista. La gramática lineal por la derecha es G = (Q, A, P, q0 ) donde las variables son los estados, la variable inicial es q0 y P contiene las producciones, p → aq, si δ(p, a) = q p → ε,

si p ∈ F

Para el caso de una gramática lineal por la izquierda, invertimos el autómata, construímos la gramática lineal por la derecha asociada e invertimos 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: 0 q0 q1 1 0

q2

1

0, 1

Modelos de Computación ITema 2: Autómatas Finitos– p.77/88

Ejemplo: Gramática Lineal por la Derecha Consideremos el autómata: 0 q0 q1 1 0

q2

1

0, 1

La gramática es (variable inicial q0 ): q0 → 0q1 ,

q0 → 1q2 ,

q2 → 0q0 ,

q1 → 0q2 ,

q2 → 1q1 ,

q1 → 1q2

q2 → ε

Modelos de Computación ITema 2: Autómatas Finitos– p.77/88

Ejemplo: Gramática Lineal por la Izquierda Autómata de Partida: 0 q0 1 0

q1 1

0, 1

q2

Modelos de Computación ITema 2: Autómatas Finitos– p.78/88

Ejemplo: Gramática Lineal por la Izquierda Autómata de Partida: 0 q0 1 0 q2

q1 1

Invertimos el autómata: 0 q0 q1 1

0, 1

0

q2

1

0, 1

Modelos de Computación ITema 2: Autómatas Finitos– p.78/88

Ejemplo: Gramática Lineal por la Izquierda Autómata de Partida: 0 q0 1 0

Invertimos el autómata: 0 q0 q1

q1 1

1 0, 1

0

q2

1

q2

0, 1

La gramática asociada a este autómata es (variable inicial q2 ): q1 → 0q0 ,

q2 → 1q0 ,

q0 → 0q2 ,

q2 → 0q1 ,

q1 → 1q2 ,

q2 → 1q1

q0 → ε

Modelos de Computación ITema 2: Autómatas Finitos– p.78/88

Ejemplo: Gramática Lineal por la Izquierda Autómata de Partida: 0 q0 1 0

Invertimos el autómata: 0 q0 q1

q1 1

1 0, 1

0

q2

1

q2

0, 1

La gramática asociada a este autómata es (variable inicial q2 ): q1 → 0q0 ,

q2 → 1q0 ,

q0 → 0q2 ,

q2 → 0q1 ,

q1 → 1q2 ,

q2 → 1q1

q0 → ε

Invertimos la parte derecha de las producciones: q1 → q0 0,

q2 → q0 1,

q0 → q2 0,

q2 → q1 0,

q1 → q2 1,

q 2 → q1 1

q0 → ε Modelos de Computación ITema 2: Autómatas Finitos– p.78/88

Máquinas de Estado Finito Má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 su salida correspondiente. Si el autómata lee la cadena u y pasa por los estados q0 q1 ...qn entonces produce la salida: λ(q0 )λ(q1 ) . . . λ(qn ) Para la cadena vacía: λ(q0 ). Modelos de Computación ITema 2: Autómatas Finitos– p.79/88

Ejemplo

   

α

3





4 







2



1



Control de semáforos en un cruce.

β

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, por defecto, 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áforo para 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 posibles colores 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)

Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0 (V, R,V, R)

Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0 (V, R,V, R)

(0, 1), (1, 1)

q1 (A, R, A, R)

Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0 (V, R,V, R)

(0, 1), (1, 1)

q1 (A, R, A, R)

A

q2 (R, R, R,V )

Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0 (V, R,V, R)

(0, 1), (1, 1)

(0, 1), (1, 1) q1 (A, R, A, R)

A

q2 (R, R, R,V )

Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0 (V, R,V, R)

(0, 1), (1, 1)

(0, 1), (1, 1) q1 (A, R, A, R)

A

q2 (R, R, R,V )

(1, 0) q3 (V, R, A, R)

Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0

(0, 1), (1, 1)

(0, 1), (1, 1)

(V, R,V, R)

q1 (A, R, A, R)

A

q2 (R, R, R,V )

(1, 0) q3 (V, R, A, R) A q4 (V,V, R, R)

Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0

(0, 1), (1, 1)

(0, 1), (1, 1)

(V, R,V, R)

q1

A

(A, R, A, R)

q2 (R, R, R,V )

(1, 0) q3 (V, R, A, R) A q4 (V,V, R, R) (1, 0), (1, 1) Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0

(0, 1), (1, 1)

(0, 1), (1, 1)

(V, R,V, R)

q1

q2

A

(A, R, A, R)

(1, 0)

(R, R, R,V )

(0, 0), (1, 0)

q3

q5

(V, R, A, R)

(R, R, R, A) A q4 (V,V, R, R) (1, 0), (1, 1) Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0

(0, 1), (1, 1)

(V, R,V, R) (1, 0)

q1

(0, 1), (1, 1)

q2

A

(A, R, A, R)

(R, R, R,V )

(0, 0), (0, 1) (0, 0), (1, 0)

q3

q5

(V, R, A, R)

(R, R, R, A) A q4 (V,V, R, R) (1, 0), (1, 1) Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0

(0, 1), (1, 1)

(V, R,V, R) (1, 0)

q1

(0, 1), (1, 1)

q2

A

(A, R, A, R)

(R, R, R,V )

(0, 0), (0, 1) (0, 0), (1, 0)

q3

q5

(V, R, A, R)

(R, R, R, A) A

(1, 0), (1, 1) q4 (V,V, R, R) (1, 0), (1, 1) Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0

(0, 1), (1, 1)

(V, R,V, R) (1, 0)

q1

(0, 1), (1, 1)

(A, R, A, R)

(R, R, R,V )

(0, 0), (0, 1) (0, 0), (1, 0)

q3

q5

(V, R, A, R)

(R, R, R, A) A

q6 (V, A, R, R)

q2

A

(1, 0), (1, 1) q4

(0, 0)

(V,V, R, R) (1, 0), (1, 1) Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0

(0, 1), (1, 1)

(V, R,V, R) (1, 0)

A

q1

(0, 1), (1, 1)

(A, R, A, R)

(R, R, R,V )

(0, 0), (0, 1) (0, 0), (1, 0)

q3

q5

(V, R, A, R)

(R, R, R, A) A

q6 (V, A, R, R)

q2

A

(1, 0), (1, 1) q4

(0, 0)

(V,V, R, R) (1, 0), (1, 1) Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0

(0, 1), (1, 1)

(V, R,V, R) (1, 0)

A

q1

(0, 1), (1, 1)

(A, R, A, R)

(R, R, R,V )

(0, 0), (0, 1) (0, 0), (1, 0)

q3

q5

(V, R, A, R)

(R, R, R, A) A

q6 (V, A, R, R)

q2

A

(1, 0), (1, 1) q4

(0, 0)

(0, 1)

(V,V, R, R)

q7 (A, A, R, R)

(1, 0), (1, 1) Modelos de Computación ITema 2: Autómatas Finitos– p.82/88

Máquina de Moore (0, 0) q0

(0, 1), (1, 1)

(V, R,V, R) (1, 0)

A

q1

(0, 1), (1, 1)

(A, R, A, R)

(R, R, R,V )

(0, 0), (0, 1) (0, 0), (1, 0)

q3

q5

(V, R, A, R)

(R, R, R, A) A

q6 (V, A, R, R)

q2

A

(1, 0), (1, 1) q4

(0, 0)

A

(0, 1)

(V,V, R, R)

q7 (A, A, R, R)

(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, excepto que λ es una aplicación de Q × A en B, λ : Q×A → B es decir, que la salida depende del estado en el que está el autómata y del símbolo leido.

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, excepto que λ es una aplicación de Q × A en B, λ : Q×A → B es decir, que la salida depende del estado en el que está el autómata y del símbolo leido. Si la entrada es a1 . . . an y pasa por los estados q0 , q1 , . . . , qn , la salida 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. 0/0 1/0

q0

q1

1/1 0/1

0/0

q2

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ón viene dada por las siguientes reglas, Primer símbolo:

0→0

Siguientes símbolos Si el anterior es un 0: Si el anterior es un 1:

1→1 0 → 0, 0 → 1,

1→1 1→0

La máquina de Mealy que realiza esta codificación es la siguiente: 0/0

1/0

1/1 q0

0/1

q1

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 0 , se dicen equivalentes sii para todo u ∈ A∗ , TM (u) = bTM0 (u) donde b es la salida correspondiente al estado inicial de la máquina de Moore M. Teorema: Dada una máquina de Moore M existe una máquina de Mealy M 0 equivalente. Teorema: Dada una máquina de Mealy M existe una máquina de Moore M 0 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 0 = (Q, A, B, δ, λ0, q0 ), donde λ0 (q, a) = λ(δ(q, a))

Ejemplo 0

1

q0 /1

1

q1 /0 0

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 0 = (Q, A, B, δ, λ0, q0 ), donde λ0 (q, a) = λ(δ(q, a))

Ejemplo 0

1

q0 /1

1

q1 /0 0

0/1 1/0

q0

1/0

q1 0/1

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 = (Q0 , A, B, δ0 , λ0 , q00 ) donde Q0 = Q × B δ0 ((q, b), a) = (δ(q, a), λ(q, a)) λ0 (q, b) = b q00 = (q0 , b), donde b ∈ B, cualquiera.

Modelos de Computación ITema 2: Autómatas Finitos– p.88/88

Ejemplo 1/0

q0

q1

1/1 0/0

0/1

0/0

q2

1/1

Modelos de Computación ITema 2: Autómatas Finitos– p.89/88

Ejemplo 1/0

q0

q1

1/1 0/0

0/1

0/0

q2

1/1

(q0 , 0)

(q1 , 0)

(q2 , 0)

0

0

0

(q0 , 1)

(q1 , 1)

(q2 , 1)

1

1

1

Modelos de Computación ITema 2: Autómatas Finitos– p.89/88

Ejemplo 1/0

q0

q1

1/1 0/0

0/1

0/0

q2

0

1/1

(q0 , 0)

(q1 , 0)

(q2 , 0)

0

0

0

(q0 , 1)

(q1 , 1)

(q2 , 1)

1

1

1

Modelos de Computación ITema 2: Autómatas Finitos– p.89/88

Ejemplo 1/0

q0

q1

1/1 0/0

0/1

q2

0 (q0 , 0)

0/0 1/1

(q1 , 0)

(q2 , 0)

0

0

0

(q0 , 1)

(q1 , 1)

(q2 , 1)

1

1

1

1

Modelos de Computación ITema 2: Autómatas Finitos– p.89/88

Ejemplo 1/0

q0

q1

1/1 0/0

0/1

q2

0 (q0 , 0)

(q1 , 0)

1

0 0

1/1 (q2 , 0)

0

0 1

0 0 0

1

(q0 , 1) 1

0/0

(q1 , 1) 1

1

1 (q2 , 1)

0

1

1

Modelos de Computación ITema 2: Autómatas Finitos– p.89/88