Decidibilidad

DECIDIBILIDAD
INTRODUCCIÓN
● Máquina de Turing: modelo general de computador.

● Tesis de Church-Turing: Algoritmo ≡ decidible en una
MT.
● Vamos a estudiar cuales son los límites de los
algoritmos.
DECIDIBILIDAD
● Lenguaje Turing decidible (Lenguaje recursivo):
1. L es aceptada por una MT M

2. M siempre para
3. M decide L
qa Si w pertenece a L
w
M
qr Si w no pertenece a L
DECIDIBILIDAD
● Lenguaje Turing reconocible (Lenguaje

recursivamente enumerable):
1. L es aceptada por una MT M

2. M no siempre para
3. M no decide L
qa
w Si w pertenece a L
M qr
Si w no pertenece a L
LOOP
DECIDIBILIDAD
● Mostrar que el lenguaje es decidible es lo mismo

que mostrar que el problema computacional es
decidible.
PROBLEMAS DECIDIBLES
Vamos a representar varios problemas computacionales por

medio de lenguajes.
Problema de la aceptación de palabras por AFDs:
Dado un AFD B y una cadena w, B acepta w?
ADFA = {<B,w> | B es un AFD que acepta la cadena w}
Teorema 4.1: ADFA es un Lenguaje Decidible.

ADFA = {<B,w> | B es un AFD y B acepta w}
M = DA-DFA - Forma de representar que la MT es un
decisor de un lenguaje AFD
M = “Sobre la entrada <B,w> donde B es un AFD, y w es
una cadena:
1. Simule B sobre la entrada w.
2. Si la simulación termina en un estado de aceptación,
acepte. Si esta termina en un estado de no-
aceptación”, rechace
Si
B= , w=11110001
M = DA-DFA
q1 , k Abi
Algoritmo
● Entrada: <B,w>
● Salida:
◆ Sí, si la simulación del AFD B con la cadena de
entrada w, para en un estado final.
◆ No, caso contrario
Algoritmo→programa→código máquina→simulado por MT

Teorema 4.2: ANFA es un Lenguaje Decidible.

ANFA = {<B, w> | B es un AFN y B acepta w}
N = “Sobre la entrada <B,w> donde B es un AFN, y w

es una cadena:
1. Convierta el AFN B para un AFD equivalente C.
2. Ejecute la MT M del Teorema 4.1 sobre la

entrada <C, w>.
3. Si M acepta, acepte; caso contrario, rechace.”
Teorema 4.3: AREX es un Lenguaje Decidible.

AREX = {<R,w> | R es una expresión regular que describe
w}
AREX representa el problema de verificar cuando una
expresión regular R genera la cadena w.
P = “Sobre la entrada <R,w> donde R es una expresión
regular y w es una cadena:
1. Convierta la expresión regular R para un AFN
equivalente B’ usando el procedimiento estudiado.
2. Ejecute la MT N sobre la entrada <B’,w>.
3. Si N acepta, acepte; caso contrario rechace.”
Problema de probar si un AFD reconocer alguna

cadena
Problema: Dado un AFD A, ¿A reconoce alguna

cadena?
¿Existe un algoritmo que resuelve ese problema?
EDFA = {<A> | A es un AFD y L(A) =∅}

¿EDFA es decidible?
Teorema 4.4: EDFA es Decidible.

EDFA = {<A> | A es un AFD y L(A) =∅}
T = “Sobre la entrada <A> donde A es un AFD:
1. Marque el estado inicial de A.
2. Repita hasta que ningun estado nuevo venga a ser
marcado:
1. Marque cualquier estado que tenga una transición
llegando en él, a partir de cualquier estado que ya
está marcado.
3. Si ningún estado de aceptación estuviera marcado,
acepte.”
Problema: Dado dos AFD’s, ¿ellos reconocen el

mismo lenguaje?
Existe un algoritmo que resuelve ese problema
EQDFA = {<A,B> | A y B son AFDs y L(A) = L(B)}
¿EQDFA es decidible?
Teorema 4.5: EQDFA es un lenguaje decidible.
La diferencia simétrica entre dos conjuntos X e Y,

denotada por X⊗Y, es definida como
X⊗Y = (X∩Yc)∪(Xc∩Y)
X=Y ⇔ X⊗Y = 𝜙

Sea L(C)=L(A)⊗L(B) = (L(A)∩L(B)c)∪(L(A)c∩L(B))
L(C) = ∅ si L(A) = L(B)
● Podemos obtener C a partir de A y B con las
construcciones utilizadas para probar que la clase de
lenguajes regulares es cerrada bajo complementación,
unión y intersección.

● F = “Sobre la entrada <A,B>, donde A y B son

AFDs:
1. Construya el AFD C conforme descrito.
2. Ejecute la MT T del Teorema 4.4 sobre la

entrada <C>.
3. Si T acepta, acepte. Si T rechaza, rechace.”
Ejercicio: Responda todas las partes del
siguiente DFA M y explique las razones de sus
respuestas.
a. ¿⟨M, 0100⟩ ∈ ADFA?

b. ¿⟨M, 011⟩ ∈ ADFA?
c. ¿⟨M⟩ ∈ ADFA?
d. ¿⟨M, 0100⟩ ∈ AREX?
e. ¿⟨M⟩ ∈ EDFA?
f. ¿⟨M, M⟩ ∈ EQDFA?
Ejercicio:
Considere el problema de determinar si un DFA y una
expresión regular son equivalentes. Exprese este
problema como un lenguaje y demuestre que es
decidible.
AAR= { <A, R> | A es un AFD, R es una ER y L(A)=L(R) }
Demostración:
T = ”Sobre la entrada <A,R>, donde A es un AFD y R es una ER:
1. Convierta la ER R en un AFN B usando el procedimiento
estudiado en clase.
2. Convierta el AFN B en su AFD C equivalente usando el
procedimiento estudiado en clase.
3. Ejecutar la MT F del teorema 4.5 con entrada <A, C>.
4. Si la MT F acepta, aceptar. Caso contrario, rechazar”
Ejemplo:
Sea A = {⟨M⟩ | M es un AFD que no acepta ninguna
cadena que contenga un número impar de unos}.
Demuestre que A es decidible.
● La siguiente MT decide A:
● M2= “Sobre la entrada ⟨M⟩, donde M es un AFD:
● 1. Construya un AFD O que acepte todas las cadenas
que contengan un número impar de unos.
● 2. Construya un AFD B tal que L(B) = L(M) ∩ L(O).
● 3. Pruebe si L(B) = ∅ usando el decisor T de EDFA del
Teorema 4.4.
● 4. Si T acepta, aceptar; si T rechaza, rechazar ".
Problema: Dada una gramática G y una cadena w, ¿G

genera w?
Problema fundamental en compiladores
ACFG = {<G,w> | G es una GLC que genera la cadena w}
¿ACFG es decidible?
Teorema 4.7: ACFG es un lenguaje decidible.

S→AB
A→0A | Ɛ
B→1B2 | Ɛ
● Si w ∈ L ⟹ el algoritmo encontrará la derivación de w

● Si w ∉ L ⟹ el algoritmo se ejecutará para siempre
● Ese algoritmo es un reconocedor, pero no es decisor
ACFG = {<G,w> | G es una GLC que genera la cadena w}
S → AB S => AB => AAB => AAAB =>

A → AA | a AAABB => aAABB => aaABB =>
B → BB | b
aaaBB => aaabB => aaabb
Si G está en la FNC y w es una palabra generada por la

gramática, entonces la derivación de w tiene
exactamente 2|w|-1 pasos

ACFG = {<G,w> | G es una GLC que genera la cadena
w}
S = “Sobre la entrada <G,w>, donde G es una GLC y w
es una cadena:
1. Convierta G para una GLC equivalente en la forma normal
de Chomsky.
2. Liste todas las derivaciones con 2n-1 pasos, donde n es el
tamaño de w, excepto si n = 0, entonces en ese caso liste
todas las derivaciones con 1 paso.
3. Si alguna de esas derivaciones genera w, acepte. Caso
contrario, rechace”
Teorema 4.8: ECFG es un lenguaje decidible.

ECFG = {<G> | G es una GLC y L(G) = ∅}
R = “Sobre la entrada <G>, donde G es una GLC:
1. Marque todos los símbolos terminales en G.
2. Repita hasta que ninguna variable venga a ser
marcada:
1. Marque cualquier variable A donde G tiene una
producción A→U1U2...Uk y cada símbolo U1, ... ,Uk ya
haya sido marcado.
3. Si la variable inicial no está marcada, acepte; caso
contrário, rechace.”
Problema: Dada dos gramáticas A y B, ¿ellas son

equivalente?
EQCFG = {<A,B> | A y B son GLC’s y L(A) = L(B)}
¿EQCFG es decidible?
Teorema: EQCFG no es decidible.

No es posible crear un algoritmo que recibe dos
gramáticas y determina si ellas son equivalentes.
Teorema 4.9: Todo lenguaje libre de contexto es decidible.
TODOS LOS LENGUAJES
LENGUAJES
TURING RECONOCIBLES
LENGUAJES
TURING DECIDIBLES
LENGUAJES
LIBRES DE CONTEXTO
LENGUAJES
REGULARES
Teorema 4.9: Todo lenguaje libre de contexto es decidible.

Demostración
∙ Sea A un LLC. ¿A es Turing decidible?
∙ Y diseñamos una MT MG que decide A. Construimos una copia
de G dentro de MG. Ella funciona de la siguiente manera.
MG = “Sobre la entrada w:
1. Sea G una GLC para A.
2. Ejecute la MT S, que decide AGLC , sobre la entrada <G,w>.
3. Si la máquina S acepta, aceptar. Caso contrario, rechazar.”
Si A es LLC, entonces existe una GLC G, que genera A

Decidibilidad

Cargado por

Copyright:

Formatos disponibles

Decidibilidad

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Decidibilidad

Cargado por

Copyright:

Formatos disponibles

DECIDIBILIDAD

● Máquina de Turing: modelo general de computador.

● Lenguaje Turing decidible (Lenguaje recursivo):

1. L es aceptada por una MT M

● Lenguaje Turing reconocible (Lenguaje

1. L es aceptada por una MT M

● Mostrar que el lenguaje es decidible es lo mismo

Vamos a representar varios problemas computacionales por

Teorema 4.1: ADFA es un Lenguaje Decidible.

Algoritmo→programa→código máquina→simulado por MT

Teorema 4.2: ANFA es un Lenguaje Decidible.

N = “Sobre la entrada <B,w> donde B es un AFN, y w

2. Ejecute la MT M del Teorema 4.1 sobre la

Teorema 4.3: AREX es un Lenguaje Decidible.

Problema de probar si un AFD reconocer alguna

Problema: Dado un AFD A, ¿A reconoce alguna

EDFA = {<A> | A es un AFD y L(A) =∅}

Teorema 4.4: EDFA es Decidible.

Problema: Dado dos AFD’s, ¿ellos reconocen el

EQDFA = {<A,B> | A y B son AFDs y L(A) = L(B)}

Teorema 4.5: EQDFA es un lenguaje decidible.

La diferencia simétrica entre dos conjuntos X e Y,

Teorema 4.5: EQDFA es un lenguaje decidible.

Teorema 4.5: EQDFA es un lenguaje decidible.

● F = “Sobre la entrada <A,B>, donde A y B son

2. Ejecute la MT T del Teorema 4.4 sobre la

a. ¿⟨M, 0100⟩ ∈ ADFA?

Problema: Dada una gramática G y una cadena w, ¿G

ACFG = {<G,w> | G es una GLC que genera la cadena w}

Teorema 4.7: ACFG es un lenguaje decidible.

● Si w ∈ L ⟹ el algoritmo encontrará la derivación de w

S → AB S => AB => AAB => AAAB =>

Si G está en la FNC y w es una palabra generada por la

Teorema 4.7: ACFG es un lenguaje decidible.

Teorema 4.8: ECFG es un lenguaje decidible.

Problema: Dada dos gramáticas A y B, ¿ellas son

EQCFG = {<A,B> | A y B son GLC’s y L(A) = L(B)}

Teorema: EQCFG no es decidible.

Teorema 4.9: Todo lenguaje libre de contexto es decidible.

TODOS LOS LENGUAJES

Teorema 4.9: Todo lenguaje libre de contexto es decidible.

Si A es LLC, entonces existe una GLC G, que genera A

También podría gustarte