Primer Parcial 1C 2012 (Teoría de Lenguajes)

De Cuba-Wiki

Ejercicio 1[editar]

Dar un Autómata Finito Determinístico de estados mínimos que acepte las cadenas sobre que interpretadas como número binario, ( es congruente a 0 módulo 3) y que no contenga la cadena 11.


Ejercicio 2[editar]

Queremos usar el alfabeto {Norte, Sur, Este, Oeste} para indicar a un robot el camino que debe recorrer. Cada cadena representa una secuencia de movimientos (todos de la misma longitud) en alguna de las cuatro direcciones. No se permiten giros de 180º. ¿Es posible usar un autómata finito para reconocer los caminos (cadenas de ) que terminan en un punto distinto a aquel en el que empezaron? Si la respuesta es sí, dar el autómata. Sino, demostrar que no es posible.

Ejemplos: El camino Sur,Norte,Norte, si bien no termina en el punto de inicio, no pertenece al lenguaje por tener un giro de 180º. El camino Sur Este Norte Oeste termina en el mismo punto que donde empezó. En cambio, Sur, Oeste Norte sí representa un camino con la propiedad buscada.

Ejercicio 3[editar]

Dar un Autómata de pila que acepte el lenguaje

Error al representar (error de sintaxis): {\displaystyle L = {\alpha \in (O|&|#)^*\ |\ |\alpha|_O \neq |\alpha|_& - |\alpha|_#}}

Ejercicio 4[editar]

Dar un traductor para la relación

Error al representar (error de sintaxis): {\displaystyle T = {(a^i b^j, c^k)\ |\ i,j } pares, promedioError al representar (error de sintaxis): {\displaystyle (i,j)}}