Maquinas Abstractas

0 %
100 %
Information about Maquinas Abstractas

Published on September 19, 2007

Author: stefanosalvatori

Source: slideshare.net

Description

Teoria de Computacion

Teoría de la Computación Máquinas Abstractas

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

Autómatas Finitos

Lenguajes Regulares

Autómatas con Pila

Lenguajes Independientes del Contexto

Máquinas de Turing

Lenguajes Sensibles al Contexto

Computabilidad, Decidibilidad

Autómatas Finitos AF = ( Q,  ,  , q 0 , F) Q :conj. Finito de estados  :alfabeto finito de entrada  :función de transición,  :Qx   Q q 0  Q: estado inicial F  Q: conj. de estados finales Representación matriz grafo

AF = ( Q,  ,  , q 0 , F)

Q :conj. Finito de estados

 :alfabeto finito de entrada

 :función de transición,  :Qx   Q

q 0  Q: estado inicial

F  Q: conj. de estados finales

Representación

matriz

grafo

d: dígito d d d 7 d d d d 6 5 4 3 2 1 E E +, - d E + - 1 2 2 2 5 3 3 4 4 4 5 5 7 6 6 6 7 7 7 * * 

Autómatas Finitos Movimiento: si  (q, s) = q’ entonces (q, sw)  (q’, w) Sea w   *, w es aceptada o reconocida por AF, si (q 0 , w)  * (q,  ), q  F L(AF)={w  w   * y  (q 0 , w)  * (q,  ), q  F} Sea AF = ( Q,  ,  , q 0 , F) un autómata finito, p  Q es accesible desde q  Q, si existe una palabra tal que  (q, x) = p Problema AFD AFND

Movimiento:

si  (q, s) = q’ entonces (q, sw)  (q’, w)

Sea w   *, w es aceptada o reconocida por AF, si (q 0 , w)  * (q,  ), q  F

L(AF)={w  w   * y  (q 0 , w)  * (q,  ), q  F}

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

Problema

AFD AFND

Autómatas con Pila AP = ( Q,  ,  ,  , q 0 , z 0 , F) Q :conj. Finito de estados  :alfabeto finito de entrada  : alfabeto finito de la pila  :función de transición,  :Q  (  {  })  Q  * q 0  Q: estado inicial z 0   : símbolo inicial de la pila F  Q: conj. de estados finales

AP = ( Q,  ,  ,  , q 0 , z 0 , F)

Q :conj. Finito de estados

 :alfabeto finito de entrada

 : alfabeto finito de la pila

 :función de transición,

 :Q  (  {  })  Q  *

q 0  Q: estado inicial

z 0   : símbolo inicial de la pila

F  Q: conj. de estados finales

Autómatas con Pila Interpretación  (q 0 ,s,z)={(p 1 ,  1), ..., (p m ,  m )}, q 0 p i  Q s  z   j  *  (q 0 ,  ,z)={(p 1 ,  1), ..., (p m ,  m )}, q 0 p i  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 (q 0 , w, z 0 )  *(q,  ,  ) con q  F  * ó (q 0 , w, z 0 )  *(q,  ,  ) termina con pila vacía L(AP)={w  (q 0 , w, z 0 )  *(q,  ,  ) para q  F  *} ó {(q 0 , w, z 0 )  *(q,  ,  )}

Interpretación

 (q 0 ,s,z)={(p 1 ,  1), ..., (p m ,  m )},

q 0 p i  Q s  z   j  *

 (q 0 ,  ,z)={(p 1 ,  1), ..., (p m ,  m )},

q 0 p i  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

(q 0 , w, z 0 )  *(q,  ,  ) con q  F  * ó

(q 0 , w, z 0 )  *(q,  ,  ) termina con pila vacía

L(AP)={w  (q 0 , w, z 0 )  *(q,  ,  ) para q  F  *} ó {(q 0 , w, z 0 )  *(q,  ,  )}

q0 q1 0,0/00 0,z/0z 1,0/  1,0/   ,z/   ,z/  ¿Lenguaje? ¿APD?

Máquinas de Turing T = ( Q,  ,  ,  , q 0 , Δ, 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 q 0  Q: estado inicial Δ   : blanco F  Q: conj. de estados finales

T = ( Q,  ,  ,  , q 0 , Δ, 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

q 0  Q: estado inicial

Δ   : blanco

F  Q: conj. de estados finales

Máquinas de Turing Configuración: (  1 , q,  2 ) q  Q, 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,x i )=(p,y,I), entonces (x 1 ...x i-2 x i-1 ,q,x i ...x n )  (x 1 ...x i-2 ,p,x i-1 yx i+1 ...x n ) Si  (q,x i )=(p,y,D), entonces (x 1 ...x i-1 ,q,x i x i+1 ...x n )  (x 1 ...x i-1 y,p,x i+1 ...x n ) L(T)={w  w   * y (q 0 , w)  * (  1 , p,  2 ) para algún p  F y  1 ,  2  *}

Configuración: (  1 , q,  2 )

q  Q, 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,x i )=(p,y,I), entonces (x 1 ...x i-2 x i-1 ,q,x i ...x n )  (x 1 ...x i-2 ,p,x i-1 yx i+1 ...x n )

Si  (q,x i )=(p,y,D), entonces (x 1 ...x i-1 ,q,x i x i+1 ...x n )  (x 1 ...x i-1 y,p,x i+1 ...x n )

L(T)={w  w   * y (q 0 , w)  * (  1 , p,  2 ) para algún p  F y  1 ,  2  *}

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) *q4 q3 (q3,y,D) (q4,Δ,D) 0 1 x y Δ  0/x,D y/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

Máquinas de Turing Construya una MT que acepte {a n b n c n  n  0} 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

Construya una MT que acepte {a n b n c n  n  0}

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

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

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

Máquinas de Turing Def. : Una MT implementa una función string f(w)=u, si se cumple q 0 w  * q f u, donde q 0 es estado inicial y q f es estado final Def. : Una función string f es Turing computable , si existe una MT, T = ( Q,  ,  ,  , q 0 , Δ, F), para la cual q 0 w  * q f u , para algún q f  F, cuando f(w)=u La definición anterior, se puede extender fácilmente a funciones algebraicas f(n,m)=n+m  transformar a n ba m en a n+m b

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

Def. : Una función string f es Turing computable , si existe una MT, T = ( Q,  ,  ,  , q 0 , Δ, F), para la cual q 0 w  * q f u , para algún q f  F, cuando f(w)=u

La definición anterior, se puede extender fácilmente a funciones algebraicas

f(n,m)=n+m  transformar a n ba m en a n+m b

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

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

Construcción de Máquinas de Turing Def. : Sean T 1 y T 2 dos máquina de Turing sobre el mismo alfabeto de entrada  y el mismo alfabeto de la cinta  , donde T 1 = ( Q 1 ,  ,  ,  1 , p 1 , Δ, F 1 ) y T 2 = ( Q 2 ,  ,  ,  2 , p 2 , Δ, F 2 ), con Q 1  Q 2 =  La composición de T 1 y T 2 es la máquina de Turing T 1 T 2 = ( Q,  ,  ,  , q 0 , Δ, F), donde Q= Q 1  Q 2 q 0 = p 1 F= F 2  (q,s)=  1 (q,s) si q  Q 1 y  1 (q,s)  (p,s’,X),  p  F 1  2 (q,s) si q  Q 2 (p 2 ,s’,X), si q  Q 1 y  1 (q,s) =(p,s’,X), para algún p  F 1

Def. : Sean T 1 y T 2 dos máquina de Turing sobre el mismo alfabeto de entrada  y el mismo alfabeto de la cinta  ,

donde T 1 = ( Q 1 ,  ,  ,  1 , p 1 , Δ, F 1 )

y T 2 = ( Q 2 ,  ,  ,  2 , p 2 , Δ, F 2 ),

con Q 1  Q 2 = 

La composición de T 1 y T 2 es la máquina de Turing T 1 T 2 = ( Q,  ,  ,  , q 0 , Δ, F),

donde Q= Q 1  Q 2

q 0 = p 1 F= F 2

 (q,s)=

 1 (q,s) si q  Q 1 y  1 (q,s)  (p,s’,X),  p  F 1

 2 (q,s) si q  Q 2

(p 2 ,s’,X), si q  Q 1 y  1 (q,s) =(p,s’,X), para algún p  F 1

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 R 2 : mueve la cabeza dos celdas a la derecha R Δ , R s : 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 Δ , L s , L  Δ Bifurcaciones L Δ R a b s=Δ s  Δ

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 R 2 : mueve la cabeza dos celdas a la derecha

R Δ , R s : 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 Δ , L s , L  Δ

Bifurcaciones

¿Qué hacen las siguientes máquinas de Turing? R s=a s=b a b R s  Δ s= Δ R Δ ΔR 2 Δ sL 2 Δ s T 1 T 2 ¿Cómo quedaría la máquina que reconoce {a n b n c n  n  0}?

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

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

Modificaciones a la máquina de Turing 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  :Q  n  Q  n  {L,R} n  (q,(s 1 ,s 2 ,...,s n ))=(p,(t 1 ,t 2 ,...,t n ),(X 1 ,X 2 ,...,X n ))

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

 :Q  n  Q  n  {L,R} n

 (q,(s 1 ,s 2 ,...,s n ))=(p,(t 1 ,t 2 ,...,t n ),(X 1 ,X 2 ,...,X n ))

Modificaciones a la máquina de Turing 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),...,(p i ,s i ,X)}

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),...,(p i ,s i ,X)}

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,  ,  ,  , q 0 , Δ, F) sobre de un alfabeto finito requiere que T tenga un solo estado final

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,  ,  ,  , q 0 , Δ, F) sobre de un alfabeto finito

requiere que T tenga un solo estado final

Máquina de Turing Universal Suposiciones Q={q 1 , q 2 , ..., q n } q 1 es estado inicial y q 2 es el único estado final  ={s 1 , s 2 , ..., s m } s 1 es el blanco Para codificar T sólo hay que codificar  Representaciones: Q :  q 1 : 1 q 2 : 11 ....  :  s 1 : 1 s 2 : 11 .... Movimiento cabeza l/e  L : 1 R : 11 El cero se usa como separador Ejemplo  (q 2 , s 1 )=(q 3 , s 4 , L) :  01101011101111010

Suposiciones

Q={q 1 , q 2 , ..., q n }

q 1 es estado inicial y q 2 es el único estado final

 ={s 1 , s 2 , ..., s m }

s 1 es el blanco

Para codificar T sólo hay que codificar 

Representaciones:

Q :  q 1 : 1 q 2 : 11 ....

 :  s 1 : 1 s 2 : 11 ....

Movimiento cabeza l/e  L : 1 R : 11

El cero se usa como separador

Ejemplo

 (q 2 , s 1 )=(q 3 , s 4 , L) :  01101011101111010

Máquina de Turing Universal Una máquina de Turing universal T u 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 T u 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

Una máquina de Turing universal T u 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

T u 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

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í, {a n b n c n  n  0}, lo es

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í, {a n b n c n  n  0}, lo es

Lenguajes recursivos y recursivamente enumerables 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 L 1 y L 2 son lenguajes recursivos, entonces L 1  L 2 también lo es ¿Cómo podemos probarlo? Ejemplo L 1 ={a i b i c k  i,k  0}, L 2 ={a i b j c j  i,j  0}

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 L 1 y L 2 son lenguajes recursivos, entonces L 1  L 2 también lo es

¿Cómo podemos probarlo?

Ejemplo L 1 ={a i b i c k  i,k  0}, L 2 ={a i b j c j  i,j  0}

Lenguajes recursivos y recursivamente enumerables Teorema: Hay un lenguaje recursivamente enumerable L para el cual  *-L no es recursivamente enumerable Teorema: Si L 1 y L 2 son lenguajes recursivos, entonces L 1  L 2 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

Teorema:

Hay un lenguaje recursivamente enumerable L para el cual  *-L no es recursivamente enumerable

Teorema:

Si L 1 y L 2 son lenguajes recursivos, entonces L 1  L 2 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

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 w  L o no si L es RE pero no recursivo no hay un algoritmo que determine si w  L o no Problema de indecidibilidad (irresolubilidad)

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 w  L o no

si L es RE pero no recursivo no hay un algoritmo que determine si w  L o no

Problema de indecidibilidad (irresolubilidad)

Lenguajes recursivos y recursivamente enumerables 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

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

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?

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?

Halting Problem Necesitamos 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 T 1 , T 2 , ... Sea L={w i  w i no es aceptada por T i } L no es RE Supongamos L enumerable, entonces L es aceptado por T k , y consideremos w k Si w k  L entonces no debe ser aceptada por T k , luego w k  L(T k )=L Si w k  L, ya que L= L(T k )  w k  L(T k ) y por lo tanto w k  L

Necesitamos 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 T 1 , T 2 , ...

Sea L={w i  w i no es aceptada por T i }

L no es RE

Supongamos L enumerable, entonces L es aceptado por T k , y consideremos w k

Si w k  L entonces no debe ser aceptada por T k , luego w k  L(T k )=L

Si w k  L, ya que L= L(T k )  w k  L(T k ) y por lo tanto w k  L

Otros Problemas Insolubles Un algoritmo, o programa que automáticamente determine: si una gramática independiente del contexto es ambigua un string w  L(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  )

Un algoritmo, o programa que automáticamente determine:

si una gramática independiente del contexto es ambigua

un string w  L(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  )

Ambigüedad en gramáticas independientes del contexto E  E o E E  E y E E  p E  q E  r p o q y r E E E p o q E q y r y r p o E  E o T E  E y T T  p T  q T  r

E  E o E

E  E y E

E  p

E  q

E  r

E  E o T

E  E y T

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

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

Add a comment

Related presentations

Related pages

Máquina abstracta - Wikipedia, la enciclopedia libre

Definiciones más complejas crean máquinas abstractas con completos conjuntos de instrucciones, registros y modelos de memoria.
Read more

MÁQUINAS ABSTRACTAS DE ESTADOS Y SUS APLICACIONES

MÁQUINAS ABSTRACTAS DE ESTADOS Y SUS APLICACIONES ABSTRACT STATE MACHINES AND THEIR APPLICATIONS Javier Mauricio Reyes Vera Universidad del Valle, Cali ...
Read more

MAQUINA ABSTRACTA by Oscar Vasquez on Prezi

Mediante el uso de máquinas abstractas es posible calcular la cantidad de recursos necesarios para realizar una operación en particular, ...
Read more

Máquina Abstracta – Deleuze | Mecanosfera

As máquinas abstractas consistem em • matérias não formadas • e funções não formais. Cada máquina abstracta é um conjunto consolidado
Read more

Máquinas Abstractas by Eunice Ayala on Prezi

Teoría de la Computación - Máquinas Abstractas Septiembre, 2013 Máquinas Abstractas Es un modelo teórico de un sistema de hardware o software usado en ...
Read more

Características comunes a Todas las Máquinas Abstractas

Características comunes a Todas las Máquinas Abstractas . A continuación se presentarán un conjunto de definiciones, y partes ...
Read more

maquinas abstractas y simuladores jflap y Thothv2Rev1 ...

En este presente video se muestra el diseño de dos maquinas: AP (Automata con pila) Y MT (Maquina de turing) y su respectiva implementacion y ...
Read more

Máquinas Abstractas / JUAN PABLO GUAMANGA HERNÁNDEZ | The ...

Máquinas Abstractas / JUAN PABLO GUAMANGA HERNÁNDEZ The greatest WordPress.com site in all the land! Search. Main menu. Skip to primary content.
Read more

Máquinas de Pila Abstracta - Ingeniería Simple

Máquinas de Pila Abstracta Generación de Código Intermedio Código intermedio Un programa para una máquina abstracta Dos cualidades Fácil de producir ...
Read more