Formas normales de chomsky

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES Práctica 6 - Forma Normal de Chomsky
1. Introducción 2. Forma Normal de Chomsky 3. Actividades propuestas

1. Introducción.
Como ya conocemos, existengramáticas de muy diferentes formas que generan un mismo lenguaje. El hecho de no restringir la forma de las reglas de tipo 2 tiene interés en los casos en que se desea diseñar una gramática para unlenguaje dado. Sin embargo, cuando se desea desarrollar demostraciones de ciertas propiedades de los lenguajes incontextuales o se desea desarrollar algoritmos eficientes que operen sobre gramáticasincontextuales, interesa imponer ciertas restriciones en las formas de las reglas de la gramática. Para ello se introducen las definiciones y los algoritmos de obtención de las formas normales para lasgramáticas incontextuales. En concreto, vamos a estudiar la conocida como Forma Normal de Chomsky (FNC). El objetivo principal de esta práctica es el estudio e implementación de los algoritmos quepermiten obtener una gramática incontextual en FNC a partir de una gramática incontextual sin λ-reglas ni reglas simples

2. Forma Normal de Chomsky.
Definición de la Forma Normal de Chomsky Diremos queuna gramática incontextual G=(N,T,P,S) que no genera la cadena vacía, está en FNC cuando todas sus reglas son de la forma: A → BC con A,B,C ∈ N A → a, con A,B ∈ N y a ∈T

Teorema. Todo lenguajeincontextual L que no incluye la cadena vacía, es generado por una gramática en FNC.

Algoritmo para la obtención de gramáticas en FNC Entrada: G=(N,T,P,S) (sin producciones unitarias ni vacías)Salida: G=(N'',T,P'',S) Método:

PASO 1
N'=N; P'=∅; Para toda regla (A → α ) de P hacer Si |α|=1 entonces añadir la regla a P' (*ya esta en FNC*) Sino sea α=X1X2...Xm con m > 1 Para i=1 hasta m hacer SiXi=a ∈Σ Entonces se añade a N' un nuevo no terminal Ca y se añade a P' una nueva regla (Ca → a) finsi finpara Se añade a P' una regla (A → X'1X'2...X'm) con: X'i=Xi si Xi ∈ N X'i=Ca si Xi = a ∈Σ...