papel deco

Teoría de la computación
José A. Rodríguez Melquiades

Unidad I:

Lenguajes y máquinas

Motivación



La teoría de autómatas
computacionales abstractos.

es

el

estudio



Los dispositivos abstractos son modelos de computaciones reales.



Las computaciones son validadas en:
Laptops,
 Teléfonos celulares,
 …




¿Porqué se necesitan modelosabstractos?.

de

dispositivos

1. Computadores simples:

BATERIA

Entrada : Interrruptor (switch).
Salida

: Foco encendido.

Acciones: flip switch.

Estados : Prendido, apagado.

f
BATERIA

inicio

encendido

apagado

f

Entrada: Interruptor.
Salida: Foco encendido.
Acciones: f para “flip switch”.
Estados: Encendido, apagado.

Foco esta encendido si y
solamente siexiste una
cantidad impar de flips.

1
1

inicio

2

BATERIA

Estados: Encendido, apagado.

2

2

1
apagado

Acciones: 1 para “flip switch 1”.
2 para “flip switch 2”.

1
2

2

Entrada: Interruptores 1 y 2.

apagado

apagado

encendido

1

Foco esta encendido si y
solamente
si
ambos
interruptores fueron flipped
una cantidad impar de veces

2. Problema dediseño:
1

BATERIA

2
3

?

4
5

¿ Se puede diseñar un circuito, donde la luz este encendida si y
solamente si todos los interruptores son flipped exactamente la
misma cantidad de veces?

Respuesta:


Tales dispositivos son difíciles, por la razón de que ellos pueden
ser diseñados de muchas maneras.



Representándolos
como
abstractos o autómatas.

dispositivoscomputacionales

3. Controlador para una puerta automática

Se encuentran en los domicilios, supermercados y las salidas,
los cuales se abren cuando una persona se acerca.

La puerta automática tiene un sensor en la parte delantera
para detectar a la persona que se esta acercando. Otro sensor
es colocado en la parte interior de la puerta de modo que el
controlador pueda validarlos.Detector en
la
parte
delantera

Detector en
la
parte
interior

Puerta

Estados del controlador: Abierto (ab),
Cerrado (ce).

Condiciones:
(a) Delantero (D): La persona esta sobre la plataforma en frente de la
puerta.
(b) Posterior (P): La persona esta sobre la plataforma detrás de la
puerta.
(c) Ambos (A): Las personas están en las dos plataformas.
(d) Ninguno (N): No haypersonas sobre las plataformas.

D, P, A

P, A,N
D
Cerrado

Abierto

N

Dispositivos computacionales en Teoría de la Computación

Finite automata

Dispositivo sin memoria
pequeños computadores.

usado

para

modelar

Push-down automata

Dispositivo con memoria que puede ser accesado de
un modo restringido. Se usa para modelar
analizadores sintácticos, etc.

TuringMachines

Dispositivo con mucha memoria que es usado para
modelar cualquier dispositivo.

Time-bounded Turing
Machines

Dispositivo con mucha memoria, pero que tiene
tiempo de ejecución limitado. Se usa para modelar
programas que corren en tiempo razonable.

Formalización en Teoría de la Computación



Formalización de un problema:

¿Un dispositivo A puede solucionar un problema B?

Respuesta:


Es necesario un modo formal para describir los problemas que
deseamos solucionar.

Problemas en Teoría de la Computación



Son los siguientes:



Dado un número n, ¿ n es divisible por 15?



Dadas dos palabras w y w’, ¿ ellas son iguales ?





Dada una palabra w, ¿ w contiene la subpalabra “computa”?

Dada la expresión(()()), ¿cadaparéntesis izquierdo coincide con aquel
que esta a la derecha ?

La respuesta para estas interrogantes tienen como respuesta un
“si/no”.

Conceptos

básicos

Alfabeto


Alfabeto:




Es un conjunto de símbolos, denotado por .

Ejemplos:


 = {a,b}.



 = {a, b, c, d, …, z}: Conjunto de letras.



 = {0, 1, …, 9}

: Conjunto de dígitos.



 = {a, b, …,...