Tabla de Decidibilidad en Teoría de la Computación – Part 1

Prerrequisito: indecidibilidad , problemas decidibles e indecidibles La 
identificación de lenguajes (o problemas*) como decidibles, indecidibles o parcialmente decidibles es una pregunta muy común en GATE. Con el conocimiento correcto y una amplia experiencia, esta pregunta se vuelve muy fácil de resolver. 

Una lengua es indecidible si no es decidible. Un lenguaje indecidible tal vez un lenguaje parcialmente decidible o algo más pero no decidible. Si un idioma no es ni siquiera parcialmente decidible, entonces no existe una máquina de Turing para ese idioma. 

En este tema, verá la tabla de Decidibilidad y el atajo para aprenderlos. 

La intersección de 2 lenguajes recursivamente enumerables es recursivamente enumerable, por lo que es decidible.

Problemas	RL	DCFL	CFL	CSL	Rec.L	NIR
¿’w’ pertenece al lenguaje L? (es decir, problema de membresía, donde ‘w’ es cualquier string)	D	D	D	D	D	UD
¿Es L= nulo? (es decir, problema de vacío)	D	D	D	UD	UD	UD
¿Es L=E * ? (es decir, problema de completitud. Donde, E * es un conjunto de todos los idiomas posibles sobre el alfabeto dado)	D	D	UD	UD	UD	UD
¿Es L1 = L2? (es decir, problema de igualdad. L1 y L2 son lenguajes del mismo tipo).	D	D	UD	UD	UD	UD
¿Es L1 subconjunto de L2? (es decir, problema de subconjunto)	D	UD	UD	UD	UD	UD
¿Es la intersección L1 de L2= nula?	D	UD	UD	UD	UD	UD
¿’L’ es finito o no? (es decir, problema de finitud)	D	D	D	UD	UD	UD
¿Es el complemento de ‘L’ un lenguaje del mismo tipo o no?	D	D	UD	D	D	UD
¿La intersección de dos idiomas es del mismo tipo o no?	D	UD	UD	D	D	D
¿’L’ es lenguaje regular o no? (‘L’ es cualquier idioma.)	D	D	UD	UD	UD	UD

En la tabla anterior, 
 

'RL' implies Regular language.
'CFL' implies Context free language.
'DCFL' implies deterministic context free language.
'CSL' implies Context sensitive language.
'REC.L' implies Recursive language.
'REL' implies Recursive enumerable language.
'D' implies that the problem is decidable.
'UD' implies that the problem is undecidable.

Nota: 
 

1. Lenguaje regular: Decidible para todos los problemas.
2. CFL: Es decidible por problema de vacío, problema de finitud y problema de pertenencia.
3. CSL y REC.L: Ambos son decidibles por problema de membresía, ¿Es el complemento de ‘L’ un lenguaje del mismo tipo o no?, y (¿Es la intersección de dos lenguajes del mismo tipo o no?).
4. REC: Es decidible por (¿Es intersección de dos lenguas del mismo tipo o no?)
5. DCFL Es decidible para todo lo decidible en CFL plus (¿Es el complemento de ‘L’ un lenguaje del mismo tipo o no?), (¿Es ‘L’ lenguaje regular?).