Examenes Automatas

Act 8: Lección Evaluativa Unidad No. 2

UNIDAD DIDÁCTICA 2 LENGUAJES INDEPENDIENTES DEL CONTEXTO

Introducción

Los lenguajes independientes del contexto que tambien se conocen con el nombre de gramaticas de contexto libre son un método recursivo sencillo de especificación de reglas gramaticales con las que se pueden generar cadenas de un lenguaje.

Es factible producir de esta manera todos los lenguajes regulares, ademas de que existen ejemplos sencillos de gramaticas de contexto libre que generan lenguajes no regulares.

Las reglas gramaticales de este tipo permiten que la sintaxis tenga variedad y refinamientos mayores que los realizados con lenguajes regulares, en gran medida sirven para especificar la sintaxis de lenguajes de alto nivel y otros lenguajes formales.

Objetivo General

Conocer los modelos de computación que corresponden a los lenguajes independientes del contexto y su aplicación.

Objetivos Especificos

Generalizar los conceptos de autómatas finitos y gramaticas regulares.

Reconocer el potencial de procesamiento del lenguaje del automata con los autómatas de pila.

LENGUAJES LIBRES DE CONTEXTO

Gramática Libre de Contexto

Una gramática libre de contexto enlingüística e informática es una gramática formal en la que cada regla de producción es de la forma:

V --> w

Donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera.

Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación , de hecho, la sintaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres dada determinen como puede ser generada desde la gramática. Los analizadores LL y LR tratan restringidos subconjuntos de gramáticas libres de contexto.

La notación más frecuentemente utilizada para expresar gramáticas libres de contexto es la forma Backus-Naur .

Así como cualquier gramática formal , una gramática libre de contexto puede ser definida mediante la 4-tupla:

G = (Vt,Vn,P,S) donde

• Vtes un conjunto finito de terminales

• Vnes un conjunto finito de no terminales

• P es un conjunto finito de producciones

• S ? Vn el denominado Símbolo Inicial

• los elementos de P son de la forma:

• Una pila es un dispositivo de almacenamiento que sigue el principio de:

• Seleccione una respuesta.

a. último-en-entrar-último-en salir

b. último-en-entrar-primero-en salir

c. primero-en-entrar-primero-en salir

d. primero-en-entrar-último-en salir

• Correcto

• Puntos para este envío: 1/1.

•

• 2

• Puntos: 1/1

• Cuál es el objetivo de aplicar una gramática:

• Seleccione al menos una respuesta.

a. La gramática permite formar correctamente las frases o generar palabras de un Lenguaje.

b. Representar linealmente (no gráficamente) el comportamiento de una Autómata Finito (ya sea AFN ó AFND)

c. Generar Lenguajes aceptables por una AP o una MT

d. Es que se parte de una variable, llamada s´ımbolo inicial, y se aplican repetidamente las reglas gramaticales, hasta que ya no haya variables en la palabra.

• Correcto

• Puntos para este envío: 1/1.

•

• 3

• Puntos: 1/1

• Cuáles afirmaciones son válidas respecto al funcionamiento de un AP.

• Seleccione al menos una respuesta.

a. En los AP las transiciones de un estado a otro indican lo que se saca de la pila no lo que se mete

b. Al iniciar la operación de un AP, la pila se encuentra vacía.

c. Al igual que los AF, los AP tienen estados finales

d. En un AP Cada transición implica la modificación de la pila.

e. La pila tendrá un alfabeto propio, que nunca debe coincidir con el alfabeto de la palabra de entrada.

f. Un AP no puede ser No determinista ya que siempre debe reconocer la palabra de entrada por su condición d ememoria adicional que tiene.

g. Al final de su operación, para aceptar una palabra, la pila debe estar vacía.

h. Un AP es una máquina reconocedora de lenguaje.

...