TEORÍA DE LA COMPUTACIÓN

GRAMATICAS LIBRES DE CONTEXTO

 

Las gramáticas libres de contexto amplían la capacidad para especificar lenguajes al incluir algunos lenguajes que no son reconocidos por un autómata finito.

 

Las gramáticas libres de contexto son útiles para describir expresiones aritméticas que tengan una anidación arbitraria de paréntesis balanceados y estructuras de bloque en los lenguajes de programación.

 ARBOLES DE DERIVACIÓN

 

 Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje.

 

Un árbol es un grafo dirigido acíclico en el cual cada nodo se conecta con un nodo distinguido, llamado nodo raíz, mediante un único camino.

Un nodo n1 se dice descendiente de otro nodo n2 si se puede llegar a n1 a partir de n2. El nodo raíz no es descendiente de ningún nodo, y los nodos que no tienen descendientes se denominan hojas. El resto de los nodos sedenominan nodos interiores.

El árbol de derivación tiene las siguientes propiedades:

- el nodo raíz está rotulado con el símbolo distinguido de la gramática;

- cada hoja corresponde a un símbolo terminal o un símbolo no terminal;

- cada nodo interior correde a un símbolo no terminal.

FORMAS NORMALES DE CHOMSKY

 Proposición 3.1 Toda gramática libre de contexto G=(V,T,P,S) que no genere a la palabra vacía se puede transformar en una gramática libre de contexto

G'=(V',T,P',S') en forma normal de Chomsky. En efecto, dada una gramática G, apliquemos el último procedimiento de la sección anterior para transformar a G en una gramática G'' sin variables inútiles ni producciones vacías ni producciones unitarias equivalente a G.

LENGUAJES NO REGULARES

•Existen lenguajes que no son regulares y técnicas para demostrarlo: “El lema de bombeo” Ejemplo:L ={ 0n1n: n ≥0} no es regular Idea de la demostración: •Si L es regular, existe M = (Q, Σ, δ, q0, F) un AFDt que lo reconoce. Además, M tiene un nofinito de estados. •Deben existir 0iy 0jcon i ≠j tales que δ*(q0, 0i) = δ*(q0, 0j) •Esto significa que δ*(q0, 0i1i) = δ*(q0, 0j1i), pero por un lado 0i1i∈L .