Descarga la aplicación para disfrutar aún más
Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!
tema6_automatas_pila
mario_roldan123
Compartir
Vista previa del material en texto
6.
Autómatas
a
Pila
Araceli
Sanchis
de
Miguel
Agapito
Ledezma
Espino
José
A.
Iglesias
Mar<nez
Beatriz
García
Jiménez
Juan
Manuel
Alonso
Weber
Grado
Ingeniería
InformáDca
Teoría
de
Autómatas
y
Lenguajes
Formales
Introducción
Definición
Equivalencias
Lenguajes
Tipo
2
A.
Sa
nc
hi
s,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
2
Lenguajes
Generales
Lenguajes
Dependientes
del
Contexto
Lenguajes
Independientes
del
Contexto
No
Deterministas
Lenguajes
Aceptados
por
Autómatas
a
Pila
Deterministas
Lenguajes
Regulares
Jerarquía
de
Lenguajes
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
3
Jerarquía
de
Lenguajes
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
4
Gramá;cas
Independientes
Contexto
Lenguajes
Independientes
Contexto
Autómatas
a
Pila
Gramá;cas
Regulares
Lenguajes
Regulares
(ER)
Autómatas
Finitos
Limitaciones
de
los
AF
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
5
Falta
de
memoria
No
pueden
reconocer
expresiones
matemáDcas,
pej.
(2x+(2+n/25)),
mas
general
el
lenguaje
XnYn
( (
) )
q
r
s
....
Para
cada
gramáDca
G
independiente
del
contexto,
existe
un
autómata
de
pila
M
tal
que
L(G)=L(M)
Para
cada
autómata
de
pila
M,
existe
una
gramáDca
G
independiente
del
contexto
tal
que
L(M)=L(G)
Existe
un
lenguaje
independiente
del
contexto
que
no
es
el
lenguaje
aceptado
por
ningún
autómata
de
pila
determinista
Teoremas
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
6
1
2
3
Introducción
Definición
Equivalencias
Lenguajes
Tipo
2
A.
Sa
nc
hi
s,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
7
De<inición
de
AP
Ao
...
...
B
PILA
/
2
)
5
)
Q
CONTROL
DE
ESTADOS
CINTA
Movimiento
de
la
cinta
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
8
Aceptación
por
estados
<inales
1
0
1
1
0
Ao
B
...
qf
CINTA
PILA
Movimiento
de
la
cinta
Palabra
leída
Pila
NO
necesariamente
vacía
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
9
Aceptación
por
vaciado
de
pila
1
0
1
1
0
q
CINTA
PILA
Movimiento
de
la
cinta
Palabra
leída
Pila
NECESARIAMENTE
vacía
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
10
De<inición
formal
AF
qo
F
Σ
Q
f
AP
qo
Σ
Q
f
F
Γ
Ao
Gestión
de Pila
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
11
Palabras:
x,
y,
z,
ax,
ay...
Palabras:
X,
Y,
Z,
AX,
AY...
Q
=
{p,q,r,...}
Σ
:
alfabeto
de
entrada
Γ
:
alfabeto
de
pila
Q
:
conjunto
finito
de
estados
Ao
∈
Γ
:
símbolo
inicial
de
la
pila
qo
∈
Q
:
estado
inicial
del
autómata
f
:
función
de
transición
F
⊂
Q
:
conjunto
de
estados
finales
AP:
(Σ,
Γ,
Q,
Ao,
qo,
f,
F)
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
12
Transición
1. Leer
un
símbolo
de
la
entrada
2. Extraer
un
símbolo
de
la
pila
3. Insertar
una
palabra
en
la
pila
4. Pasar
a
un
nuevo
estado
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
13
q
qn
a,A;Yn
f(q,a,A)={(q1,Z1),(q2,
Z2),...,(qn,
Zn)}
(q,a,A;qn,Yn)
f
:
Q
x
(Σ
∪
{λ}
)
x
Γ
→
P(Q
x
Γ
*)
Q
x
Σ
x
Γ
Q
x
λ
x
Γ
Transiciones
dependientes
de
la
entrada
Transiciones
independientes
de
la
entrada
Q
x
Γ*
P
(Q
x
Γ*)
AP
Deterministas
AP
No
Deterministas
Función
de
Transición
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
14
T.
independientes
de
la
entrada
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
15
Sea la transición:
f(q, λ ,A) = {(q1 ,Z1), (q2, Z2),...,(qn, Zn)}
donde:
q, qi ∈ Q
A ∈ Γ
Zi ∈ Γ*
q
..
..
..
a
..
...
...
A
z
X
(q,
az,
AX)
→
(p,
az,
X)
f(q,λ,A)
=
(p,
λ)
p
T.
independientes
de
la
entrada
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
16
T.
dependientes
de
la
entrada
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
17
Sea
la
transición:
f(q,a,A)
=
{(q1,Z1),
(q2,Z2),...,(qn,Zn)}
donde:
q,
qi
∈
Q
a
∈
Σ
A
∈
Γ
Zi
∈
Γ*
..
..
..
a
..
...
...
A
q
X
(q,
az,
AX)
→
(p,
z,
X)
f(q,a,A)
=
(p,
λ)
p
a
z
T.
dependientes
de
la
entrada
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
18
Descripción
Instantánea
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
19
Permite
describir
sencillamente
la
configuración
del
AP
en
cada
momento
Terna
(q,x,z)
donde:
ConDene:
• el
estado
actual
(q)
• lo
que
queda
por
leer
de
la
entrada
(x)
y
• el
símbolo
en
la
cima
de
la
pila
(z)
q∈Q,
x∈Σ*,
z∈Γ*
Descripción
Instantánea
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
20
Movimiento:
(q,ay,AX)⊢(p,y,YX)
describe
el
paso
de
una
descripción
instantánea
a
otra
Sucesión
de
movimientos:
(q,ay,AX)
⊢*(p,y,YX)
representa
que
desde
la
primera
descripción
instantánea
se
puede
alcanzar
la
segunda
Autómatas
a
Pila
Deterministas
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
21(Σ,Γ,Q,A0,q0,f,F)
es
determinista
si
verifica:
∀q∈Q,
A∈Γ,
|
f
(q,λ,A)
|
>0
⇒
f
(q,a,A)=Φ
∀a∈Σ
∀q∈Q,
A∈Γ,
∀a∈Σ
∪{λ},
|
f
(q,a,A)
|
<2
si
(p,
x,
y;
q,
z)
y
(p,
x,
y;
r,
w)
son
transiciones
de
un
autómata
a
pila
determinista
entonces
q≡r,
z=w
Lenguaje
aceptado
por
un
AP
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
22
Por
vaciado
de
pila
LVAP={x|(q0,x,A0)
⊢*(p,λ,λ),
p∈Q,
x∈Σ*}
Por
estado
final
LFAP={x|(q0,x,A0)⊢*(p,λ,X),
p∈F,
x∈Σ*,X∈Γ*}
Ejemplo
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
23
LENGUAJE:
algunas
instrucciones
var
::=
num;
(asignación)
if
cond
then
BLOQUE
(asignación
ó
if)
if
cond
then
BLOQUE
(asignación
ó
if)
else
BLOQUE
(asignación
ó
if)
Ejemplo
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
24
AP=
({if,
then,
else,
::=,
var,
num,
cond,
;},
{S,
B,
C,
F,
N,
P,
T,
E},
{q},
q,
S,
f,
φ)
f(q,
var,
S)
=
{(q,
FNP)}
f(q,
if,
S)
=
{(q,
CTBP),
(q,
CTBEBP)}
f(q,
if,
B)
=
{(q,
CTB),
(q,
CTBEB)}
f(q,
var,
B)
=
{(q,
FN)}
f(q,
cond,
C)
=
{(q,
λ)}
f(q,
::=,
F)
=
{(q,
λ)}
f(q,
num,
N)
=
{(q,
λ)}
f(q,
;,
P)
=
{(q,
λ)}
f(q,
then,
T)
=
{(q,
λ)}
f(q,
else,
E)
=
{(q,
λ)}
ELEMENTOS
DE
Γ
S
→
Símbolo
inicial
F
→
::=
N
→
Numero
P
→
;
C
→
Condición
T
→
Then
B
→
Bloque
E
→
Else
f(q,
var,
S)
=
{(q,
FNP)}
f(q,
if,
S)
=
{(q,
CTBP),
(q,
CTBEBP)}
f(q,
if,
B)
=
{(q,
CTB),
(q,
CTBEB)}
f(q,
var,
B)
=
{(q,
FN)}
f(q,
cond,
C)
=
{(q,
λ)}
f(q,
::=,
F)
=
{(q,
λ)}
f(q,
num,
N)
=
{(q,
λ)}
f(q,
;,
P)
=
{(q,
λ)}
f(q,
then,
T)
=
{(q,
λ)}
f(q,
else,
E)
=
{(q,
λ)}
if cond var then ::= num ;
S
q
Ejemplo
25
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
P
T
B
C
if cond var then ::= num ;
q
f(q,
var,
S)
=
{(q,
FNP)}
f(q,
if,
S)
=
{(q,
CTBP),
(q,
CTBEBP)}
f(q,
if,
B)
=
{(q,
CTB),
(q,
CTBEB)}
f(q,
var,
B)
=
{(q,
FN)}
f(q,
cond,
C)
=
{(q,
λ)}
f(q,
::=,
F)
=
{(q,
λ)}
f(q,
num,
N)
=
{(q,
λ)}
f(q,
;,
P)
=
{(q,
λ)}
f(q,
then,
T)
=
{(q,
λ)}
f(q,
else,
E)
=
{(q,
λ)}
Ejemplo
26
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
f(q,
var,
S)
=
{(q,
FNP)}
f(q,
if,
S)
=
{(q,
CTBP),
(q,
CTBEBP)}
f(q,
if,
B)
=
{(q,
CTB),
(q,
CTBEB)}
f(q,
var,
B)
=
{(q,
FN)}
f(q,
cond,
C)
=
{(q,
λ)}
f(q,
::=,
F)
=
{(q,
λ)}
f(q,
num,
N)
=
{(q,
λ)}
f(q,
;,
P)
=
{(q,
λ)}
f(q,
then,
T)
=
{(q,
λ)}
f(q,
else,
E)
=
{(q,
λ)}
P
T
B
if cond var then ::= num ;
q
Ejemplo
27
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
P
B
if cond var then ::= num ;
q
f(q,
var,
S)
=
{(q,
FNP)}
f(q,
if,
S)
=
{(q,
CTBP),
(q,
CTBEBP)}
f(q,
if,
B)
=
{(q,
CTB),
(q,
CTBEB)}
f(q,
var,
B)
=
{(q,
FN)}
f(q,
cond,
C)
=
{(q,
λ)}
f(q,
::=,
F)
=
{(q,
λ)}
f(q,
num,
N)
=
{(q,
λ)}
f(q,
;,
P)
=
{(q,
λ)}
f(q,
then,
T)
=
{(q,
λ)}
f(q,
else,
E)
=
{(q,
λ)}
Ejemplo
28
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
P
F
N
if cond var then ::= num ;
q
f(q,
var,
S)
=
{(q,
FNP)}
f(q,
if,
S)
=
{(q,
CTBP),
(q,
CTBEBP)}
f(q,
if,
B)
=
{(q,
CTB),
(q,
CTBEB)}
f(q,
var,
B)
=
{(q,
FN)}
f(q,
cond,
C)
=
{(q,
λ)}
f(q,
::=,
F)
=
{(q,
λ)}
f(q,
num,
N)
=
{(q,
λ)}
f(q,
;,
P)
=
{(q,
λ)}
f(q,
then,
T)
=
{(q,
λ)}
f(q,
else,
E)
=
{(q,
λ)}
Ejemplo
29
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
f(q,
var,
S)
=
{(q,
FNP)}
f(q,
if,
S)
=
{(q,
CTBP),
(q,
CTBEBP)}
f(q,
if,
B)
=
{(q,
CTB),
(q,
CTBEB)}
f(q,
var,
B)
=
{(q,
FN)}
f(q,
cond,
C)
=
{(q,
λ)}
f(q,
::=,
F)
=
{(q,
λ)}
f(q,
num,
N)
=
{(q,
λ)}
f(q,
;,
P)
=
{(q,
λ)}
f(q,
then,
T)
=
{(q,
λ)}
f(q,
else,
E)
=
{(q,
λ)}
P
N
if cond var then ::= num ;
q
Ejemplo
30
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
f(q,
var,
S)
=
{(q,
FNP)}
f(q,
if,
S)
=
{(q,
CTBP),
(q,
CTBEBP)}
f(q,
if,
B)
=
{(q,
CTB),
(q,
CTBEB)}
f(q,
var,
B)
=
{(q,
FN)}
f(q,
cond,
C)
=
{(q,
λ)}
f(q,
::=,
F)
=
{(q,
λ)}
f(q,
num,
N)
=
{(q,
λ)}
f(q,
;,
P)
=
{(q,
λ)}
f(q,
then,
T)
=
{(q,
λ)}
f(q,
else,
E)
=
{(q,
λ)}
P
if cond var then ::= num ;
q
Ejemplo
31
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
if cond var then ::= num ;
q
Pila vacía
Sentencia reconocida
Ejemplo
32
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
Introducción
Definición
Equivalencias
Lenguajes
Tipo
2
33
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
Equivalencias
34
Teorema
Para
cada
autómata
de
pila
que
acepte
cadenas
sin
vaciar
su
pila,
existe
un
autómata
equivalente
pero
que
vacía
su
pila
antes
de
llegar
a
un
estado
de
aceptación.
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
Paso
de
APF
a
APV
1.
Nuevo
símbolo
para
la
pila
2.
Dos
estados
nuevos
3.
Valor
inicial
de
la
pila
4.
Nuevo
estado
inicial
5.
SIN
estados
finales
APF
=
(Σ,
Γ,
Q,
A0,
q0,
f,
F)
APV
=(Σ,
Γ∪⎨B⎬,
Q
∪⎨p,r⎬,
B,
p,
f’,
φ)
35
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
Paso
de
APF
a
APV
p
q0
λ,B;
A0B
APF
=
(Σ,
Γ,
Q,
A0,
q0,
f,
F)
APV
=(Σ,
Γ∪⎨B⎬,
Q
∪⎨p,r⎬,
B,
p,
f’,
φ)
f’
se
define
así:
qi
qj
a,
A;
Z
qi,
qj
∈Q,
a
∈
Σ
∪
{λ},
A
∈
Γ,
Z
∈
Γ*
qf
r
λ,A;
λ
∀
qf
∈
F,
A
∈
Γ∪
⎨B⎬
qf
r
λ,A;
λ
∀
A
∈
Γ∪
⎨B⎬
36
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
Paso
de
APV
a
APF
p
q0
λ,B;
A0B
q
r*
λ,B;
λ
APV=(Σ,
Γ,
Q,
A0,
q0
,
f,
φ)
→
APF=(Σ,
Γ∪⎨B⎬,
Q
∪⎨p,
r⎬,
B,
p,
f’,
{r})
f'
se
define
así:
f‘(p,
λ,B)
=
(q0,
A0B)
f(q,
a,
A)
=
f‘(q,
a,
A)
∀
q
∈
Q,
a
∈
Σ
∪
{λ}
,
A∈
Γ
(r,
λ)
∈
f‘(q,
λ,
B)
∀
q
∈
Q,
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
Introducción
Definición
Equivalencias
Lenguajes
Tipo
2
38
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
De
Gramática
Tipo
2
a
APV
39
Dada
una
G2
en
FNG,
construir
un
APV:
Se
obDene
un
APV
con
un
solo
estado
entrada
pila
inicial
de
pila
G
=
(ΣT,
ΣN,
S,
P)
APV
=
(ΣT,
ΣN,
⎨q⎬,
S,
q,
f,
φ)
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
De
Gramática
Tipo
2
a
APV
40
f
se
define
como:
(q,
Z)
∈
f(q,
a,
A)
f(q,
a,
A)
=
(q,
Z)
si
existe
una
producción
del
Dpo
A
::=
a
Z
es
decir:
f(q,
a,
A)
=
{(q,
Z),
(q,
λ)}
f(q,
a,
A)
=
(q,
λ)
si
existe
una
producción
del
Dpo
A
::=
a
A::=
aZ
⎢
aD
⎢b
⇒
f(q,
a,
A)=
{(q,
Z),
(q,
D)}
f(q,
b,
A)
=
(q,
λ)
dada
una
producción:
Si
S::=
λ
⇒
(q,λ)
∈
f(q,λ,S)
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
De
Gramática
Tipo
2
a
APF
41
Dada
una
G2,
construir
un
APF
G
=
(ΣT,
ΣN,
S,
P)
APV
=
(ΣT,
Γ,
Q,
A0,
q0,
f,
{q2})
donde:
Γ=
ΣT
∪
ΣN
∪
{A0},
donde
A0
∉
ΣT
∪
ΣN
Q={q0,
q1,
q2}
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
De
Gramática
Tipo
2
a
APF
42
f
se
define
como:
f
(q0,
λ,
A0)
=
{q1,
SA0}
∀A
∈
ΣN,
si
A
::=
α
∈
P,
(α
∈
Σ*)
⇒
(q1,
α)
∈
f
(q1,
λ,
A)
es
decir:
f
(q1,
λ,
A)
=
{…,
(q1,
α)
,
…}
∀
a
∈
ΣT,
(q1,
λ)
∈
f
(q1,a,a)
es
decir
f
(q1,a,a)
=
{…,
(q1,λ),…
}
f
(q1,
λ,
A0)
=
{q2,A0}
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
De
APV
a
Gramática
Tipo
2
43
Dado
un
APV,
construir
una
G2
tal
que
L(G2)
=
L(APV)
APV
=
(Σ,
Γ,
Q,
A0,
q0,
f,
φ)
G
=
(ΣT,
ΣN,
S,
P)
{S}
∪
{
(pAq)
|
p,
q
∈
Q,
A
∈
Γ}
Para
construir
P:
1. S::=
(q0,
A0
,q)
∀
q
∈
Q
(se
eligen
las
que
empiezan
por
q0A0)
2. De
cada
transición
f(p,a,A)
=
(q,
BB’B’’....B’’’)
donde:
A,B,B’,B’’,…,B’’’
∈
Γ
;
a
∈
Σ
∪
{λ}
se
obDene:
(p
A
z
)
::=
a
(
q
B
r
)
(
r
B’
s
)
s
...
y
(
y
B’’’
z
)
3. De
cada
transición
f(
p,
a,
A)
=
(q,
λ)
se
obDenen:
(
p,A,q
)
::=
a
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
o
Bibliogra<ía
• Libro
Básico
1
Bibliograwa.
Enrique
Alfonseca
Cubero,
Manuel
Alfonseca
Cubero,
Roberto
Moriyón
Salomón.
Teoría
de
autómatas
y
lenguajes
formales.
McGraw-‐Hill
(2007).
Capítulo
4
y
Apartado
8.1
• Libro
Básico
2
Bibliograwa.
John
E.
Hopcroz,
Rajeev
Motwani,
Jeffrey
D.Ullman.
Introducción
a
la
teoría
de
autómatas,
lenguajes
y
computación
(3ª
edición).
Ed,
Pearson
Addison
Wesley.
Capítulo
6
• Libro
Básico
4
Bibliograwa.
Manuel
Alfonseca,
Justo
Sancho,
Miguel
Mar<nez
Orga.
Teoría
de
lenguajes,
gramáDcas
y
autómatas.
Publicaciones
R.A.E.C.
1997
Capítulo
10
44
A.
S
an
ch
is
,
A
.
L
ed
ez
m
a,
J.
Ig
le
si
as
,
B
.
G
ar
cí
a,
J.
A
lo
ns
oMateriales relacionados
66 pag.UOC _ Grado en Ingeniería Informática _ Prácticas de Programación _ Estructura
Materiales Generales
10 pag.
106 pag.
16 pag.
Compartir