Teoria 7

INSTITUTO POLITÉCNICO NACIONAL

ESCUELA SUPERIOR
DE CÓMPUTO


“Practica 7: Forma Normal de Greibach”

Teoría Computacional

Profesora:
Sánchez García Luz María

Presenta:
Luna Reyes BrandonManuel

Grupo: 2CM3
Boleta: 2014630279




Introducción

Una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG) si todas y cada una de sus reglas de producción tienen unconsecuente que empieza por un carácter del alfabeto, también llamado símbolo terminal. Formalmente, cualquiera de las reglas tendrá la estructura:
Donde "A" es el antecedente de la regla, que en el casode las GIC debe ser necesariamente un solo símbolo auxiliar. Por su parte, "a" es el mencionado comienzo del consecuente y, por tanto, un símbolo terminal. Finalmente, "w" representa una concatenacióngenérica de elementos gramaticales, esto es, una sucesión exclusivamente de auxiliares, inclusive, pudiera ser la palabra vacía.
Existe un teorema que prueba que cualquier GIC, cuyo lenguaje nocontiene a la palabra vacía, si no lo está ya, se puede transformar en otra equivalente que sí esté en FNG. Para su demostración, normalmente, se procede por construcción, es decir, se plantea directamenteun algoritmo capaz de obtener la FNG a partir de una GIC dada.













Planteamiento Del Problema
Realización de un programa que calcule la forma normal de Greibach de una gramática libre decontexto
El programa aceptará una gramática libre de contexto (GLC) en Forma Normal de Chomsky (FNC) y la convertirá en Forma Normal de Greibach (FNG).




















Desarrollo
//Brandon ManuelLunas Reyes - 2CM3 - 22/04/2015
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int main()
{int z;
do{
char S[100],B[100],C[100],D[100],E[100];
int s=0,b=0,e=0;
printf ("Ingrese el los primeros terminos: ");
fgets(S,100,stdin);
if (S[0]!='C')...

Leer documento completo

Regístrate para leer el documento completo.