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

Ejercicio 1

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

Ejercicio 2

Queremos usar el alfabeto $\Sigma =$ {Norte, Sur, Este, Oeste} para indicar a un robot el camino que debe recorrer. Cada cadena $\alpha \in \Sigma ^{*}$ 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma^*} ) 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

Dar un Autómata de pila que acepte el lenguaje

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L = {\alpha \in (O|&|#)^*\ |\ |\alpha|_O \neq |\alpha|_& - |\alpha|_#}}

Ejercicio 4

Dar un traductor para la relación

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T = {(a^i b^j, c^k)\ |\ i,j } pares, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k = } promedioError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (i,j)}}