Perito

Tema 2: Autómatas finitos
´ ´ Departamento de Sistemas Informaticos y Computacion

DSIC - UPV

http://www.dsic.upv.es

– p.

´ Tema 2: Automatas finitos
• Autómata finito determinista (AFD).

Formas de representación de un AFD: ◦ Diagrama de transiciones. ◦ Tabla de transiciones.
• Autómata finito no determinista (AFN). • Equivalencia AFN - AFD • Autómata finito no determinista contransiciones vacías

(AFλ).
• Gramáticas. Definiciones • Gramáticas. Jerarquía de Chomsky • Equivalencia AFλ - AFN • Equivalencia Autómata Finito - Gramática Regular

DSIC - UPV

http://www.dsic.upv.es

– p.

´ Automata finito determinista
• Un autómata finito determinista es una 5-tupla

A = (Q, Σ, δ, q0 , F ) donde: ◦ Q es un conjunto finito de estados ◦ Σ es un conjunto finito de símboloso alfabeto. ◦ δ : Q × Σ → Q es una función parcial llamada función de transición ◦ q0 ∈ Q estado inicial ◦ F ⊆ Q conjunto de estados finales
a1 a2 a3 an

Memoria Finita

DSIC - UPV

http://www.dsic.upv.es

– p.

´ Automata finito determinista
A = ({q0 , q1 , q2 }, {a, b}, δ, q0 , {q0 , q1 }) δ(q0 , a)= q0 δ(q0 , b)= q1
a b

δ(q1 , a)= q2 δ(q1 , b)= q1

δ(q2 , a)= q2 δ(q2 , b)= q2a
q0

b b
q1

a,b a
q2

q0 q1 q2

q0 q2 q2

q1 q1 q2

DSIC - UPV

http://www.dsic.upv.es

– p.

´ Automata finito determinista
• Extensión de la función de transición a cadenas

ˆ δ : Q × Σ∗ → Q ∀q ∈ Q, x ∈ Σ∗ , a ∈ Σ ˆ ◦ δ(q, λ) = q ˆ ˆ ◦ δ(q, xa) = δ(δ(q, x), a)
• Lenguaje aceptado por un AFD

L(A) = {x ∈ Σ∗ | δ(q0 , x) ∈ F }

DSIC - UPV

http://www.dsic.upv.es– p.

´ Automata finito no determinista
• Un autómata finito no determinista es una 5-tupla

A = (Q, Σ, δ, q0 , F ) donde: ◦ Q, Σ, q0 ∈ Q y F ⊆ Q el mismo conjunto de estados, alfabeto, estado inicial y conjunto de estados finales que en la definición de AFD ◦ δ : Q × Σ → 2Q es una función parcial llamada función de transición ˆ • Extensión de δ a cadenas δ : Q × Σ∗ → 2Q ∀q ∈ Q, x ∈ Σ∗ , a ∈ Σˆ ◦ δ(q, λ) = {q} ˆ ◦ δ(q, xa) =
ˆ p∈δ(q,x)

δ(p, a)

• Lenguaje aceptado por un AFN:

ˆ L(A) = {x ∈ Σ∗ | δ(q0 , x) ∩ F = ∅}
DSIC - UPV

http://www.dsic.upv.es

– p.

´ Automata finito no determinista
A = ({q0 , q1 , q2 }, {a, b, c}, δ, q0 , {q0 , q1 , q2 }) δ(q0 , a)= {q0 , q1 , q2 } δ(q0 , b)= {q1 , q2 } δ(q0 , c)= {q2 }
a b

δ(q1 , a)= ∅ δ(q1 , b)= {q1 , q2 } δ(q1 , c)= {q2 }c

δ(q2 , a)= ∅ δ(q2 , b)= ∅ δ(q2 , c)= {q2 }

a
q0

b a,b
q1

c b,c
q2

q0 q1 q2

{q0 , q1 , q2 } ∅ ∅

{q1 , q2 } {q1 , q2 } ∅

{q2 } {q2 } {q2 }

a,b,c

DSIC - UPV

http://www.dsic.upv.es

– p.

´ Automata finito no determinista
• Equivalencia entre AFN y AFD

Sea A = (Q, Σ, δ, q0 , F ) un AFN.
′ Construimos un AFD A′ = (Q′ , Σ, δ ′ , q0 , F ′ ) tal que L(A) =L(A′ ) de la siguiente forma:

◦ Q′ = 2Q ′ ◦ q0 = {q0 } ◦ F ′ = {q ′ ∈ Q′ | q ′ ∩ F = ∅} ◦ δ ′ (q ′ , a) = δ(q, a) : q ′ ∈ Q, a ∈ Σ
q∈q ′

DSIC - UPV

http://www.dsic.upv.es

– p.

´ Automata finito no determinista
• ejercicios:

q0

a

q1

a,b

q2

q0

b

q1

a b

q2

a,b,c

a,b

a

DSIC - UPV

http://www.dsic.upv.es

– p.

´ Automata finito nodeterminista con transiciones vac´as ı
• Un autómata finito no determinista con transiciones vacías

es una 5-tupla A = (Q, Σ, δ, q0 , F ) donde: ◦ Q, Σ, q0 ∈ Q y F ⊆ Q el mismo conjunto de estados, alfabeto, estado inicial y conjunto de estados finales que en la definición de AFD y AFN ◦ δ : Q × (Σ ∪ {λ}) → 2Q es una función parcial llamada función de transición
• λ-clausura de un estado q ∈ Q (λ −clausura(q)): conjunto

de estados que pueden alcanzarse desde q sin consumir símbolo. Dado P ⊆ Q, λ − clausura(P ) =
p∈P

λ − clausura(p)

DSIC - UPV

http://www.dsic.upv.es

– p. 1

´ Automata finito no determinista con transiciones vac´as ı
ˆ • Extensión de δ a cadenas δ : Q × Σ∗ → 2Q ∀q ∈ Q, x ∈ Σ∗ , a ∈ Σ ˆ ◦ δ(q, λ) = λ − clausura(q) ˆ ◦ δ(q, xa) = λ − clausura
ˆ p∈δ(q,x)...