TEOR A DE LA COMPUTACI N Y LENGUAJES FORMALES



TEORÍA DE LA COMPUTACIÓN Y LENGUAJES FORMALES. 

OBJETIVO 

Realizar un repaso de los conceptos básicos y los conocimientos aprendidos con anterioridad, para reafirmarlos, resolver dudas eidentificar aquellos aún no comprendidos. 

CUESTIONAMIENTOS 

¿Qué es un homomorfismo? 

Concepto: 
 “Un homomorfismo, (o a veces simplemente morfismo) desde un objeto matemático a otro de la mismacategoría, es una función que preserva la estructura entre dos estructuras matemáticas relevantes”. [1] 

Comentario: 
De acuerdo a lo anterior, entendimos que un homomorfismo es una función que igualar,modelar o imitar una forma o estructura.  

¿Cuál es el lenguaje recursivamente enumerable? 

Concepto: 
 “Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquinade Turing que acepta y se detiene con cualquier cadena del lenguaje. Pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje, en contraposición a loslenguajes recursivos en cuyo caso se requiere que la máquina de Turing pare en todos los casos”. [2] 

Comentario: 
Por lo tanto, los lenguajes recursivamente enumerables, son aquellos lenguajes que sonaceptados y calculados  por una máquina de Turing. También serán generados por esta. Son enumerables, ya que enlista o enumera una cadena de lenguaje. Esta cadena será aceptada si es que pertenece a unlenguaje recursivo, de lo contrario la rechazará y se detendrá.  

¿Cuál es el lenguaje dependiente o sensible del contexto? 

Concepto: 
 “Un LSC es un lenguaje formal que puede ser definido porgramáticas sensibles al contexto. Es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky, siendo esta gramática la menos frecuente, tanto en la teoría como en la práctica”. [3] Comentario: 
Son todos aquellos lenguajes descritos por gramáticas formales, reconocidos por una máquina de Turing determinista, cuya cinta de memoria esta determinada por un cierto número entero de veces...