Modelos formales de computación

Autómatas

! Máquinas que consisten en estados y transiciones

Transiciones

! Cuando de un estado hay múltiples transiones posibles, la máquina recibe como entrada símbolos de un alfabeto.

! El símbolo recibido determina la transición a realizar.

! Cuando hay solamente una transición posible por estado, el alfabeto es unario.

! Si una entrada causa que el autómata llegue a un estado terminar, su operación termina.

! El resultado de la operación es el estado final elegido.

Autómatas deterministas

Una sola transición posible de cada estado por símbolo de alfabeto, no más.

a

b

c

b

a

c

Autómata no determinista

!Cuando hay dos o más posibles transiciones de un estado que usan el mismo símbolo del alfabeto, el autómata elige su transición al azar.

!La presencia de aleatoriedad se llama no determinismo.

Ejemplo

a

a

b

b

a

b

Máquina Turing

! Un especie de autómata

! El modelo más cómunmente utilizado en la teoría de la computación

! Necesario para entender conceptos de la complejidad computacional

Máquina Turing

Estructura

Cinta infinita

Cabeza lector

Formalmente

M = (K,Σ, δ, s)Estados

Alfabeto

Función de transición

Estado inicial

M = (K,Σ, δ, s)

Capıtulo 3

Modelos de computacion

3.1. Maquinas Turing

Un modelo formal de computacion es lo de la maquina Turing. Las maquinas Turingpueden simular cualquier algoritmo con perdida de eficiencia insignificante utilizandouna sola estructura de datos: una sucesion de sımbolos escrita en una cinta (infinita) quepermite borrar y imprimir sımbolos. Formalmente, se define una maquina Turing M =(K, !, !, s) por

(I) un conjunto finito de estados K,

(II) un conjunto finito de sımbolos !, que se llama el alfabeto de M que contiene dossımbolos espaciales !, " " !,

(III) una funcion de transicion

! : K # ! $ (K % {“alto”, “sı”, “no”}) # ! # {$,&,'}, (3.1)

(IV) un estado de alto “alto”, un estado de acepto “sı” y un estado de rechazo “no” y

(V) direcciones del puntero:$ (derecha),& (izquierda) y ' (sin mover).

La funcion ! captura el “programa” de la maquina. Si el estado actual es q " K y elsımbolo actualmente bajo el puntero es # " !, la funcion ! nos da

!(q, #) = (p, $, D), (3.2)

donde p es el estado nuevo, $ es el sımbolo que sera escrito en el lugar de # yD " {$,&,'} es la direccion a la cual movera el puntero. Si el puntero mueve fuera de la sucesionde entrada a la derecha, el sımbolo que es leıdo es siempre ! (un sımbolo blanco) hastaque la maquina lo reemplaza por imprimir algo en esa posicion de la cinta. El largo de la

31

Capıtulo 3

Modelos de computacion

3.1. Maquinas Turing

Un modelo formal de computacion es lo de la maquina Turing. Las maquinas Turingpueden simular cualquier algoritmo con perdida de eficiencia insignificante utilizandouna sola estructura de datos: una sucesion de sımbolos escrita en una cinta (infinita) quepermite borrar y imprimir sımbolos. Formalmente, se define una maquina Turing M =(K, !, !, s) por

(I) un conjunto finito de estados K,

(II) un conjunto finito de sımbolos !, que se llama el alfabeto de M que contiene dossımbolos espaciales !, " " !,

(III) una funcion de transicion

! : K # ! $ (K % {“alto”, “sı”, “no”}) # ! # {$,&,'}, (3.1)

(IV) un estado de alto “alto”, un estado de acepto “sı” y un estado de rechazo “no” y

(V) direcciones del puntero:$ (derecha),& (izquierda) y ' (sin mover).

La funcion ! captura el “programa” de la maquina. Si el estado actual es q " K y elsımbolo actualmente bajo el puntero es # " !, la funcion ! nos da

!(q, #) = (p, $, D), (3.2)

donde p es el estado nuevo, $ es el sımbolo que sera escrito en el lugar de # yD " {$,&,'} es la direccion a la cual movera el puntero. Si el puntero mueve fuera de la sucesionde entrada a la derecha, el sımbolo que es leıdo es siempre ! (un sımbolo blanco) hastaque la maquina lo reemplaza por imprimir algo en esa posicion de la cinta. El largo de la

31

”alto”, ”sı”, ”no” ∈ K

Capıtulo 3

Modelos de computacion

3.1. Maquinas Turing

Un modelo formal de computacion es lo de la maquina Turing. Las maquinas Turingpueden simular cualquier algoritmo con perdida de eficiencia insignificante utilizandouna sola estructura de datos: una sucesion de sımbolos escrita en una cinta (infinita) quepermite borrar y imprimir sımbolos. Formalmente, se define una maquina Turing M =(K, !, !, s) por

(I) un conjunto finito de estados K,

(II) un conjunto finito de sımbolos !, que se llama el alfabeto de M que contiene dossımbolos espaciales !, " " !,

(III) una funcion de transicion

! : K # ! $ (K % {“alto”, “sı”, “no”}) # ! # {$,&,'}, (3.1)

(IV) un estado de alto “alto”, un estado de acepto “sı” y un estado de rechazo “no” y

(V) direcciones del puntero:$ (derecha),& (izquierda) y ' (sin mover).

La funcion ! captura el “programa” de la maquina. Si el estado actual es q " K y elsımbolo actualmente bajo el puntero es # " !, la funcion ! nos da

!(q, #) = (p, $, D), (3.2)

donde p es el estado nuevo, $ es el sımbolo que sera escrito en el lugar de # yD " {$,&,'} es la direccion a la cual movera el puntero. Si el puntero mueve fuera de la sucesionde entrada a la derecha, el sımbolo que es leıdo es siempre ! (un sımbolo blanco) hastaque la maquina lo reemplaza por imprimir algo en esa posicion de la cinta. El largo de la

31

Estados terminales

Símbolos especiales Vacio e inicio

Punteros Der., izq. y quieto

M = (K,Σ, δ, s)

Capıtulo 3

Modelos de computacion

3.1. Maquinas Turing

Un modelo formal de computacion es lo de la maquina Turing. Las maquinas Turingpueden simular cualquier algoritmo con perdida de eficiencia insignificante utilizandouna sola estructura de datos: una sucesion de sımbolos escrita en una cinta (infinita) quepermite borrar y imprimir sımbolos. Formalmente, se define una maquina Turing M =(K, !, !, s) por

(I) un conjunto finito de estados K,

(II) un conjunto finito de sımbolos !, que se llama el alfabeto de M que contiene dossımbolos espaciales !, " " !,

(III) una funcion de transicion

! : K # ! $ (K % {“alto”, “sı”, “no”}) # ! # {$,&,'}, (3.1)

(IV) un estado de alto “alto”, un estado de acepto “sı” y un estado de rechazo “no” y

(V) direcciones del puntero:$ (derecha),& (izquierda) y ' (sin mover).

La funcion ! captura el “programa” de la maquina. Si el estado actual es q " K y elsımbolo actualmente bajo el puntero es # " !, la funcion ! nos da

!(q, #) = (p, $, D), (3.2)

donde p es el estado nuevo, $ es el sımbolo que sera escrito en el lugar de # yD " {$,&,'} es la direccion a la cual movera el puntero. Si el puntero mueve fuera de la sucesionde entrada a la derecha, el sımbolo que es leıdo es siempre ! (un sımbolo blanco) hastaque la maquina lo reemplaza por imprimir algo en esa posicion de la cinta. El largo de la

31

δ(q,σ) = (p, ρ,D),dondeq, p ∈ K,σ, ρ ∈ Σ,D ∈ {→,←,−}.

Operación de la máquina! Al inicio, en la cinta está el símbolo de inicio seguido por la

entrada que es una cadena de símbolos del alfabeto.

! La máquina está en el estado inicial y la cabeza lector está encima del símbolo de inicio.

! La máquina lee el símbolo debajo de la cabeza lector y luego ejecuta a la función de transición que causa que la cabeza reemplaza el símbolo con el símbolo determinado y luego mueve según el la dirección de puntero determinada.

! Cuando la máquina llega a un estado terminar, la cadena que está escrita en su cinta es la salida de la máquina.

Ejemplo

32 CAPITULO 3. MODELOS DE COMPUTACION

cinta en todo momento es la posicion mas a la derecha leıdo por la maquina, es decir, lamayor cantidad de posiciones utilizada por la maquina hasta actualidad.Cada programa comienza con la maquina en el estado inicial s con la cinta inicializadaa contener !x, donde x es una sucesion finita de sımbolos en (! ! {"})!, y el punteropuntando a ! en la cinta. La sucesion x es la entrada de la maquina.Se dice que la maquina se ha detenido si se ha llegado a uno de los tres estados de alto{“alto”, “sı”, “no”}. Si la maquina se detuvo en “sı”, la maquina acepta la entrada. Si lamaquina se detuvo en “no”, la maquina rechaza su entrada. La salidaM(x) de la maquinaM con la entrada x se define como

(I) M(x) = “sı” si la maquina acepta x,

(II) M(x) = “no” si la maquina rechaza x,

(III) M(x) = y si la maquina llega a “alto” y !y "" . . . es la sucesion escrita en la cintadeM en el momento de detenerse y

(IV) M(x) =# siM nunca se detiene con la entrada x.

Un ejemplo es la maquina siguiente para el computo de n + 1 dado n $ Z, n > 0, enrepresentacion binaria. Tenemos dos estados s y q (ademas del estado “alto”) y cuatrosımbolos: ! = {0, 1,", !}. La funcion de transicion " se define como

p $ K # $ ! "(p, #)s, 0 (s, 0,%)s, 1 (s, 1,%)s, " (q,",&)s, ! (s, !,%)q, 0 (“alto”, 1,!)q, 1 (q, 0,&)q, ! (“alto”, !,%)

Una configuracion (q, w, u) es tal que q $ K es el estado actual y w, u $ !! tal que w esla parte de la sucesion escrita en la cinta a la izquierda del puntero, incluyendo el sımbolodebajo del puntero actualmente, y u es la sucesion a la derecha del puntero.

La relacion “rinde en un paso” M% es la siguiente:

(q, w, u)M% (q", w", u") (3.3)

ası que si # es el ultimo sımbolo de w y "(q, #) = (p, $, D), aplica que q" = p y los w"

y u" se construye segun (p, $, D). Por ejemplo, si D =%, tenemos w" igual a w con elultimo sımbolo reemplazado por $ y el primer sımbolo de u concatenado. Si u es vacıa,se adjunta un " a w. Si u no es vacıa, u" es como u pero sin el primer sımbolo, y si u esvacıa, u" tambien la es.

10110111 ¿Qué es la salida?

¿Matemáticamente qué hizo?

Lenguajes

! Una máquina o autómata decide un lenguaje si sabe decir en un tiempo finito“sí” para todas las palabras que pertenecen a ello y sabe decir “no” para todas los que no pertenecen.

! Si sabe decir “sí”, pero no sabe decir siempre “no”, se dice que reconoce el lenguaje.

! Si para un lenguaje existe una máquina que lo decide, se dice que el lenguaje es recursivo.

L ⊆ Σ∗

Gramáticas

L = {0, 1}∗

P → 0P | 1P | �

Vacío

Otro ejemplo

L = {�, r}

E → �Er | EE | �