Ejercicios Automatas

“Con la ciencia por la humanidad”

Ingeniería en Sistemas Computacionales

Lenguajes y Autómatas I

Ejercicios

Gramática Independiente del Contexto

Catedrático:

Ing. Brenda Escamilla Domínguez

Equipo 2:

Erick Castellanos Cruz

Edna Montserrat Romo González

Jorge Antonio Tonone Torres

Nuevo Laredo, Tamaulipas a 4 de julio de 2015

Ejercicios

1. Muestre que toda cadena derivada por la izquierda de una gramática independiente del contexto puede derivarse también por la derecha.

Gramática:

S -> zMNz

M ->aMa

M ->z

N ->bNb

N ->z

Derivación por la derecha:

S => zMNz => zaMaNz =>zazaNz => zazabNbz => zazabzbz

Derivación por la izquierda:

S=> zMNz =>zMbNbz => zMbzbz => zaMabzbz => zazabzbz

No importa si derivamos por la izquierda o la derecha nos dará la misma cadena.

2. Se dice que una gramática es ambigua cuando permite más de un árbol de análisis sintáctico para una sola cadena. Demuestre que la gramática que se presenta a continuación es ambigua, mostrando que la cadena “ictictses” tiene derivaciones que producen distintos árboles de análisis sintáctico.

3.

S -> ictS

S -> ictSeS

S->s

4. Utilice el procedimiento descrito en el teorema 2.3 para construir una gramática independiente del contexto que genere el lenguaje aceptado por el autómata de pila cuyo diagrama de transiciones es el siguiente. Demuestre que la unión de dos lenguajes independientes del contexto también es independiente del contexto

...