Formas normales de Chomsky.

Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas:
 o
α
donde ,  y  son símbolos no terminales (o variables) y α es un símbolo terminal.
Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.



Sea $G=(\Sigma_N,\Sigma_T,P,\$)$ una gramática con $P\subset\Sigma_N\times(\Sigma_N\cup\Sigma_T)^*$ y $X\in\Sigma_N$ un símbolo no-terminal (o una variable). Podemos clasificar tales símbolos $X$ en tres clases:

variables accesibles:
si existe una derivación desde el símbolo inicial que contiene $X$, es decir, existe $\$\longrightarrow ^*\alpha X\beta$ donde $\alpha,\beta\in\mbox{$\Sigma^*$}$.

variables generativas:
si existe una derivación desde el la variable que produce una sentencia $w$, es decir, existe $X\longrightarrow ^*w$ donde $w\in\Sigma_T^*$.

variables útiles:
si existe una derivación desde el símbolo inicial usando $X$ que produce una sentencia $w$, es decir, existe $\$\longrightarrow ^*\alpha X\beta\longrightarrow ^*w$ donde $\alpha,\beta\in\mbox{$\Sigma^*$}$ y $w\in\Sigma_T^*$.


Una gramática está en forma normal de Chomsky (FNC)
  • si $G$ (es decir, su $\Sigma_N$) solamente contiene variables útiles y
  • si todas las producciones de $G$ (es decir, en su $P$) son
    • o bien de la forma $X\longrightarrow YZ$ con $X,Y,Z\in\Sigma_N$
    • o bien de la forma $X\longrightarrow \sigma$ con $X\in\Sigma_N$ y $\sigma\in\Sigma_T$
  • si $\$$ (es decir, el símbolo inicial de $G$) no aparece al lado derecho de ninguna producción, también está permitido que $\$\longrightarrow \epsilon\in P$.



Comentarios

Publicar un comentario

Entradas populares de este blog

Arbol de Derivacion

Imagen
Un  árbol de derivación  (o  árbol sintáctico ) es una representación gráfica de como se deriva una forma sentencial a partir del símbolo no-terminal inicial. 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 n  1  se dice descendiente de otro nodo n  2  si se puede llegar a n  1  a partir de n  1 . 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 se denominan nodos interiores. Un  árbol de derivación  tiene las siguientes propiedades: El  nodo raíz  está rotulado con el símbolo distinguido (inicial) de la Gramatica. Cada  hoja  corresponde a un símbolo terminal o un símbolo no-terminal. Cada  nodo interior  corresponde a un símbolo no-terminal. Un...
Leer más