Automata

EJERCICIOS TALF – 4.6



1.- Construir el AP reconocedor del lenguaje de los palíndromos de longitud par, excluyendo la palabra vacía.

2.- Construir el AP reconocedordel lenguaje de los palíndromos de longitud par, incluyendo la palabra vacía.

3.- Sobre el alfabeto de los paréntesis ( = {( , )}, definir el lenguaje de las expresionesválidas y construir el autómata con pila que reconoce dicho lenguaje.

4.- Dada la gramática G que tiene el conjunto de reglas P = {S ( a S b (( (}, definir un autómata con pilaequivalente.

5.- Dada la gramática G1 que tiene el conjunto de reglas P = {S1 ( S1 (S1) (((}, encontrar un autómata con pila equivalente.

6.- Dada la gramática G2 quetiene el conjunto de reglas P = {S2 ( S2 S2 (( (S2) (((}, encontrar un autómata con pila equivalente.
Transformar G2 en una gramática equivalente no ambigua. Eliminar lasproducciones (. Ponerla en forma normal de Chomsky.

7.- Demostrar que las gramáticas G1 (ejercicio 5) y G2 (ejercicio 6) son equivalentes.

8.- Demostrar que el AP equivalente aG1 (ejercicio 5) es equivalente al AP equivalente a G2 (ejercicio 6).

9.- Construir el analizador sintáctico para el lenguaje L = { x = an bn , n ( 0 }, a partir de unagramática con dos reglas.

10.- Construir el analizador sintáctico para el lenguaje L = { x = an bn , n ( 1 }, a partir de una gramática en forma normal de Chomsky.

11.-Construir el analizador sintáctico para el lenguaje de las expresiones de solo paréntesis bien apareados, partiendo de una gramática no ambigua y recursión por la derecha.

12.-Construir el analizador sintáctico para el lenguaje de las expresiones de solo paréntesis bien apareados, partiendo de una gramática no ambigua y recursión por la izquierda.