• Author / Uploaded
• Bryan Enrique Caldera Ruiz

Citation preview

Instituto Tecnológico Superior de Jerez

INSTITUTO TECNOLÓGICO SUPERIOR DE JEREZ

Jerez de García Salinas Zacatecas

FECHA: 24/04/2018

ALUMNO: Bryan Enrique Caldera Ruiz

No. Control: 15070124

Correo electrónico: [email protected]

CARRERA: Ingeniería en Sistemas Computacionales

Materia: Autómatas 1

Tarea: Forma normal de chomsky DOCENTE: M.C.C Vanessa Saldívar Quezada

Gramáticas libres de contexto Estas gramáticas son conocidas de varias formas como gramáticas tipo 2, gramáticas independientes de contexto o gramáticas libres de contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico. Como toda gramática se definen mediante una cuádrupla G = (N, T, P, S), siendo - N es un conjunto finito de símbolos no terminales - T es un conjunto finito de símbolos terminales N ∩ T = ∅ - P es un conjunto finito de producciones - S es el símbolo distinguido o axioma S ∉ (N ∪ T) En una gramática libre del contexto, cada producción de P tiene la forma A ∈ N ∪ {S} A→ω ω ∈ (N ∪ T)* - {ε} (computación, 2008)

Formas normales de Chomsky Como ya se dijo anteriormente que es una gramática libre de contexto, ahora se va a definir que es una gramática en la forma de Chomsky. Una gramática en su forma de Chomsky puede presentarse de las siguientes formas: 1. A→BC, donde A, B y C son variables, o 2. A→a, donde A es una variable y a es un símbolo terminal. Además, G no contiene símbolos inútiles. Una gramática así se dice que está en la forma normal de Chomsky.

Toda producción de dicha gramática es de la forma A→a, que es una forma permitida por la FNC, o tiene un cuerpo de longitud 2 o superior. Nuestras tareas son entonces: a) Conseguir que todos los cuerpos de longitud 2 o superior estén formados sólo por variables. b) Descomponer los cuerpos de longitud 3 o superior en una cascada de producciones, teniendo cada una de ellas un cuerpo formado sólo por dos variables. La construcción para (a) es la siguiente: para todo símbolo a que aparezca en un cuerpo de longitud 2 o superior, creamos una nueva variable, por ejemplo A. Esta variable sólo tiene una producción, A →a. Ahora empleamos A en lugar de a en cualquier lugar que aparezca esta última dentro de un cuerpo de longitud 2 o superior. En este punto, toda producción tendrá un cuerpo formado por un sólo símbolo terminal o por al menos dos variables y ningún símbolo terminal. Para el paso (b), tenemos que descomponer dichas producciones A→B1B2 · · ·Bk, para k ≥ 3, en un grupo de producciones con dos variables en cada cuerpo. Introducimos k−2 nuevas variables, C1,C2, . . . ,Ck−2. La producción original se reemplaza por las k−1 producciones: A→B1C1, C1 →B2C2, . . . ,Ck−3 →Bk−2Ck−2, Ck−2 →Bk−1Bk (John E, 2007)

Bibliografía computación, C. d. (2008). Obtenido de http://www.exa.unicen.edu.ar/catedras/ccomp1/Apunte5.pdf Hopocroft John E., M. R. (2007). Teoria de automatas, lenguajes y computación . Madrid: PEARSON EDUCACIÓN S.A. Luis, J. A. (1995). Teoria de automatas y lenguajes formales. Madrid, España: PRENTICE HALL.