Tema2 UC3M TALF SANCHIS LEDEZMA IGLESIAS JIMENEZ ALONSO
Sanchis
de
Miguel
Agapito
Ledezma
Espino
José
A.
Iglesias
Mar
Beatriz
García
Jiménez
Juan
Manuel
Alonso
Weber
Grado
Ingeniería
InformáDca
Teoría
de
Autómatas
y
Lenguajes
Formales
A.
Sanchis,
A.
Ledezma,
J.A.
Iglesias,
B.
García,
J.
M.Alonso
2.Teoría
de Autómatas
Tipos
de
autómatas
Aplicaciones
Lenguajes
Formales
A.
Sanchis,
A.
Ledezma,
J.A.
Iglesias,
B.
García,
J.
M.Alonso
Introducción
2
• Se
trata
de
saber
qué
(y
qué
no)
se
puede
computar.
Y
además…
cómo
de
rápido,
con
cuánta
memoria y
con
qué
modelo
de
computación.
A.
Sanchis,
A.
Ledezma,
J.A.
Iglesias,
B.
García,
J.
M.Alonso
Introducción
y
de6iniciones
3
• Qué
se
enDende
por
computación?
• La
Teoría
de
Autómatas
se
centra
en
la
computación
en
sí,
no
en
detalles
sobre
disposiDvos de
entrada
y
salida.
(Así,
no
se
trata
de
crear
modelos
matemáDcos
para
un
video
juego,
por
ejemplo).
A.
Sanchis,
A.
Ledezma,
J.A.
Iglesias,
B.
García,
J.
M.Alonso
Introducción
y
de6iniciones
4
Definición
RAE
autómata.
(Del
lat.
automăta,
t.
f.
de
-‐tus,
y este
del
gr.
αὐτόματος,
espontáneo).
1. m.
Instrumento
o
aparato
que
encierra
dentro
de
sí
el
mecanismo
que
le
imprime
determinados
movimientos.
2. m.
Máquina
que
imita
la
figura
y
los
movimientos
de
un
ser
animado.
3. m.
coloq.
Persona
estúpida
o
excesivamente
débil, que
se
deja
dirigir
por
otra.
A.
Sanchis,
A.
Ledezma,
J.A.
Iglesias,
B.
García,
J.
M.Alonso
Autómata
5
Autómata:
Modelo
MatemáDco
de
computación.
DisposiDvo
abstracto
con
capacidad
de
computación.
Teoría
de
Autómatas:
Abstracción
de
cualquier
Dpo
de computador
y/o
lenguaje
de
programación.
Desglose
en
sus
elementos
básicos
(Entrada,
Estado,
Transición,
Salidas
y
elementos
auxiliares)
A.
Sanchis,
A.
Ledezma,
J.A.
Iglesias,
B.
García,
J.
M.Alonso
Modelo
Matemático
6
Tipos
de
autómatas
Aplicaciones
Lenguajes
Formales
A.
Sanchis,
A.
Ledezma,
J.A.
Iglesias,
B.
García,
J.
M.Alonso
Introducción
7
Autómatas
Finitos
(y
máquinas
secuenciales)
Autómatas
ProbabilísDcos
Autómatas
a
Pila
Células
de
Mc
Culloch-‐Piks
Máquinas
de
Turing
Autómatas
Celulares
Redes
de
Neuronas
ArDficiales
A.
Sanchis, A.
Ledezma,
J.A.
Iglesias,
B.
García,
J.
M.Alonso
Tipos
de
autómatas
8
Autómatas
Finitos
(y
m
áquinas
secuenciales)
Turing
estudió
una
máquina
abstracta
con
la
misma
capacidad
que
los
Autómatas
ProbabilísDcos
computadores
actuales
desde
el
punto
de
vista
de
lo
que son
capaces
de
hacer.
Autómatas
a
Pila
Células
de
Mc
Culloch-‐Piks
Máquinas
de
Turing
Autómatas
Celulares
Redes
de
Neuronas
ArDficiales
A.
Sanchis,
A.
Ledezma,
J.A.
Iglesias,
B.
García,
J.
M.Alonso
Tipos
de
autómatas
9
Autómatas
Finitos
(y
máquinas
secuenciales)...
Regístrate para leer el documento completo.