Automatas Lenguajes Independientes

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:

...