maquinas abstractas

1

Teoría de la Computación

Máquinas Abstractas

2

Máquinas Abstractas

Autómatas Finitos Lenguajes Regulares

Autómatas con Pila Lenguajes Independientes del Contexto

Máquinas de Turing Lenguajes Sensibles al Contexto Computabilidad, Decidibilidad

3

Autómatas Finitos

AF = ( Q, , , q0, F) Q :conj. Finito de estados :alfabeto finito de entrada :función de transición, :Qx Q q0 Q: estado inicial F Q: conj. de estados finales

Representación matriz grafo

4

d: dígitod

dd

7d

d

d

d

6

54

3

21

E

E

+,-

d E + - 1 22 2 5 3 3 44 4 5 5 7 6 66 7 7 7

*

*

5

Autómatas FinitosMovimiento:

si (q, s) = q’ entonces (q, sw) (q’, w) Sea w *, w es aceptada o reconocida

por AF, si (q0, w) * (q, ), q F

L(AF)={w w * y (q0, w) * (q, ), q F}

Sea AF = ( Q, , , q0, F) un autómata finito, p Q es accesible desde q Q, si existe una palabra tal que (q, x) = p

ProblemaAFD AFND

6

Autómatas con Pila

AP = ( Q, , , , q0, z0, F) Q :conj. Finito de estados :alfabeto finito de entrada : alfabeto finito de la pila :función de transición,

:Q({}) Q*

q0 Q: estado inicial

z0 : símbolo inicial de la pila F Q: conj. de estados finales

7

Autómatas con Pila Interpretación

(q0,s,z)={(p1,1), ..., (pm,m)}, q0 piQ s z j*

(q0,,z)={(p1,1), ..., (pm,m)}, q0 pi Q z j *

Movimiento: si (q’, ) (q, s, z) entonces (q, sw, z) (q’, w, ),

q, q’Q s w* z ,*

Sea w *, w es aceptada o reconocida por AP, si (q0, w, z0) *(q,,) con qF * ó

(q0, w, z0) *(q,,) termina con pila vacía

L(AP)={w (q0, w, z0) *(q,,) para qF *} ó {(q0, w, z0) *(q,,)}

8

q0 q1

0,0/000,z/0z 1,0/

1,0/

,z/

,z/

¿Lenguaje?

¿APD?

9

Máquinas de Turing

T = ( Q, , , , q0, Δ, F) Q : conj. Finito de estados : alfabeto finito de entrada, Δ , : alfabeto finito de la cinta :función de transición,

:Q Q{I,D}, I,D movimientos

q0 Q: estado inicial

Δ : blanco F Q: conj. de estados finales

10

Máquinas de TuringConfiguración: (1, q, 2)

qQ, estado actual, 1* string a la izquierda de la cabeza,

2* string a la derecha de la cabeza

si 2=, la cabeza examina un blanco

Movimiento: Si (q,xi)=(p,y,I), entonces

(x1...xi-2xi-1,q,xi...xn) (x1...xi-2,p,xi-1yxi+1...xn)

Si (q,xi)=(p,y,D), entonces(x1...xi-1,q,xixi+1...xn) (x1...xi-1y,p,xi+1...xn)

L(T)={w w * y (q0, w) * (1, p, 2) para algún pF y 1,2*}

11

Ejemplo

q0 (q1,x,D) (q3,y,D)q1 (q1,0,D) (q2,y,I) (q1,y,D)q2 (q2,0,I) (q0,x,D) (q2,y,I)

*q4q3 (q3,y,D) (q4,Δ,D)

0 1 x y Δ

0/x,Dy/y,D

0/0,D

1/y,I

y/y,D

0/0,I

x/x,D

y/y,I

q0

q1

q2

q3 q4

y/y,D

Δ /Δ,D

12

Máquinas de Turing

Construya una MT que acepte {anbncnn0}Def. : Un lenguaje es recursivamente

enumerable (RE) si es aceptado por una Máquina de Turing Las palabras son enumeradas o listadas por la

MT

Hay lenguajes recursivamente enumerables semi decidibles

La clase de lenguajes recursivamente enumerables decidibles se conoce como la clase de lenguajes recursivos

13

Máquinas de Turing

Teorema: Si un lenguaje es recursivo,

entonces es recursivamente enumerable

Teorema: Si L es un lenguaje recursivo,

entonces su complemento -L también es recursivo

14

Máquinas de Turing

Def. : Una MT implementa una función string f(w)=u, si se cumple q0w * qfu, donde q0 es estado inicial y qf es estado final

Def. : Una función string f es Turing computable, si existe una MT, T = ( Q, , , , q0, Δ, F), para la cual q0w * qfu , para algún qfF, cuando f(w)=u

La definición anterior, se puede extender fácilmente a funciones algebraicas f(n,m)=n+m transformar anbam en an+mb

15

Construcción de Máquinas de Turing

Combinación de máquinas sencillas, que comparten la misma cinta, forma máquinas más complejas

Máquina compleja: Repertorio de máquinas básicas Reglas para combinar máquinas

Cuando una máquina termina su ejecución, la otra empieza La segunda máquina opera sobre el contenido

de la cinta que dejó la primera al detenerse

16

Construcción de Máquinas de Turing

Def. : Sean T1 y T2 dos máquina de Turing sobre el mismo

alfabeto de entrada y el mismo alfabeto de la cinta , donde T1 = ( Q1, , , 1, p1, Δ, F1)

y T2 = ( Q2, , , 2, p2, Δ, F2),

con Q1 Q2 =

La composición de T1 y T2 es la máquina de Turing

T1T2 = ( Q, , , , q0, Δ, F), donde Q= Q1Q2

q0= p1 F= F2

(q,s)= 1(q,s) si q Q1 y 1(q,s) (p,s’,X), p F1

2(q,s) si q Q2

(p2,s’,X), si q Q1 y 1(q,s) =(p,s’,X), para algún p F1

17

Composición de Máquinas de Turing

Bloques básicos: R : mueve la cabeza una celda a la derecha L : mueve la cabeza una celda a la izquierda a : escribe el símbolo a en la celda actual RR o R2 : mueve la cabeza dos celdas a la derecha R Δ , Rs : mueve la cabeza a la derecha hasta encontrar

el primer blanco o el primer símbolo s respectivamente Otros RΔ cualquier símbolo distinto de Δ, LΔ , Ls , LΔ

Bifurcaciones

LΔ R a

b

s=Δ

sΔ

18

¿Qué hacen las siguientes máquinas de Turing?

R s=a

s=b

a

b R sΔ

s=Δ

RΔ

ΔR2ΔsL2

Δs

T1 T2

¿Cómo quedaría la máquina que reconoce {anbncnn0}?

19

Modificaciones a la máquina de Turing

1.- :Q Q{L,R}, puede ser modificado como :Q Q{L,R,S} (q,s)=(p,s’,S), la cabeza no se mueve

2.- Cada celda de la cinta se divide en subceldas cinta con múltiples pistas contenido de las celdas son n-túplas 1 cabeza lectora/escritora

3.- Cinta infinita en una sola dirección generalmente, limitada a la izquierda, infinita a la

derecha

20


4.- Máquina de Turing multicinta cada cinta tiene su propia cabeza lecto/escritora cada cabeza lecto/escritora se controla

independientemente de las demás en un movimiento la máquina

cambia de estado dependiendo del estado actual y de las celdas de todas las cintas

escribe un símbolo en la celda examinada por cada cabeza

mueve cada cabeza a la izquierda o a la derecha

función de transición:Qn Qn{L,R}n

(q,(s1,s2,...,sn))=(p,(t1,t2,...,tn),(X1,X2,...,Xn))

21


5.- Máquina de Turing con cinta multidimensional función de transición

:Q Q{L,R,U,D}

6.- Máquina de Turing no determinista función de transición

:Q Q{L,R}(q,s)={(p,s’,X),(p’,s’’,X),...,(pi,si,X)}

22

Máquina de Turing Universal

Def. : La máquina de Turing universal es una máquina de Turing que, a partir de una descripción adecuada de una máquina de Turing arbitraria T y un string de entrada w, simula el comportamiento de T sobre el string w. La MTU tiene como entrada a T y a w requiere de una codificación de

T = ( Q, , , , q0, Δ, F) sobre de un alfabeto finito

requiere que T tenga un solo estado final

23

Máquina de Turing UniversalSuposiciones

Q={q1, q2, ..., qn}q1 es estado inicial y q2 es el único estado final

={s1, s2, ..., sm}s1 es el blanco

Para codificar T sólo hay que codificar Representaciones:

Q : q1 : 1 q2 : 11 ....

: s1 : 1 s2 : 11 .... Movimiento cabeza l/e L : 1 R : 11 El cero se usa como separador

Ejemplo (q2, s1)=(q3, s4, L) : 01101011101111010

24

Máquina de Turing Universal

Una máquina de Turing universal Tu se puede implementar como una máquina de Turing de 3 cintas, cuyo alfabeto de entrada contenga ceros y unos cinta 1 : codificación de T, con la cabeza en el 0 inicial cinta 2 : contenido de la cinta de T, con la cabeza en el 1 que

pertenece a la codificación del símbolo actual cinta 3 : estado actual de T, con la cabeza en el 1 inicial

Procedimiento Tu compara el contenido de las cintas 3 y 2 con el de la cinta

1 , hasta que encuentra una transición para la configuración codificada (en cuyo caso hace las transformaciones indicadas en la cinta 1) o hasta que agota todas las posibilidades

25

Lenguajes recursivos y recursivamente enumerables

Teorema: Si L es un lenguaje regular, entonces L es un

lenguaje recursivo ¿Hay lenguajes recursivos que no son

regulares?

Teorema: Si L es un lenguaje independiente del contexto,

entonces L es un lenguaje recursivo ¿Hay lenguajes recursivos que no son

independientes del contexto? Sí, {anbncnn0}, lo es

26


Teorema: Si L es un lenguaje sensible al contexto, entonces

L es un lenguaje recursivo

Lema Sea G=(N,,S,P) una gramática sensible al

contexto. Entonces existe una máquina de Turing T, que para con toda entrada y acepta L(G)

Teorema: Si L1 y L2 son lenguajes recursivos, entonces L1

L2 también lo es ¿Cómo podemos probarlo? Ejemplo L1={aibicki,k0}, L2={aibjcji,j0}

27


Teorema: Hay un lenguaje recursivamente enumerable L

para el cual *-L no es recursivamente enumerable

Teorema: Si L1 y L2 son lenguajes recursivos, entonces L1

L2 también lo es

Teorema: Si L es un lenguaje RE para el cual *-L también es

RE, entonces L es recursivo

Teorema: Les un lenguaje RE ssi L es enumerado por una

máquina de Turing

28

Máquina de Turing modelo de computación mecánica modela un proceso los procesos mecánicos que siempre

terminan se llaman algoritmos una máquina de Turing que para sobre

cualquier string es un modelo de algoritmo Si L es recursivo, hay un algoritmo que

determina si wL o nosi L es RE pero no recursivo no hay un

algoritmo que determine si wL o no Problema de indecidibilidad

(irresolubilidad)

29


Teorema: Si L es RE y *-L también lo es, entonces L es

recursivo

Tanto los lenguajes RE, como los recursivos son cerrados bajo la intersección y la unión

Tesis de Church-Turing Nada puede ser considerado algoritmo si no

puede ser ejecutado como una máquina de Turing que para con todas las entradas, y todas esta máquinas serán legítimamente llamadas algoritmos

30

Halting Problem

Se dice que los problemas de decisión son solubles si existe un algoritmo capaz de responder sí o no a cada caso

Si tal algoritmo no existe, el problema es insoluble

El problema insoluble más conocido es el problema de la parada de la máquina de Turing:

Sea T una máquina de Turing arbitraria con alfabeto de entrada . Sea w*. ¿Parará T con w como entrada?

31

Halting ProblemNecesitamos una MT que pare con todas las

entradas (T,w) y responda sí, si T con w para y responda no si T con w no para

MTs sobre son enumerables T1, T2, ...

Sea L={wiwi no es aceptada por Ti}L no es RE

Supongamos L enumerable, entonces L es aceptado por Tk, y consideremos wk

Si wkL entonces no debe ser aceptada por Tk, luego wkL(Tk)=L

Si wkL, ya que L= L(Tk) wkL(Tk) y por lo tanto wkL

32

Otros Problemas Insolubles

Un algoritmo, o programa que automáticamente determine: si una gramática independiente del

contexto es ambiguaun string wL(G), un árbol de derivación

sintáctico en G

una demostración de la corrección de programas

realmente f(x, x,..., x)=z

realmente f para para cualquier (x, x,..., x)

33

Ambigüedad en gramáticas independientes del contexto

EE o E EE y E Ep Eq Er

p o q y r

E

E E

p o q

E

q y r

y rp o

EE o T EE y T

TpTqTr

34

Corrección de programas

Ambiente = asertivas antes, después de la ejecución de un

comando ambiente inicial + reglas propuestas por el programa = ambiente final deseado programa correcto

Similar demostración de teoremas¿Problema de la parada de la MT?

Verificación si el programa se detiene

maquinas abstractas

Documents