# data[].attributes.headline
Características de los árboles de derivación o de análisis de amigüedad

# data[].attributes.subject
Características de los árboles de derivación o de análisis de amigüedad

# data[].attributes.body
-El Nodo raíz se identifica con el símbolo inicial S
- Los nodos hijo del nodo raíz se etiquetan con los símbolos que aparecen en la parte derecha de la producción del símbolo inicial.
- Todo nodo etiquetado con un no terminal, tiene como nodos hijos los etiquetados con los símbolos del lado derecho de la producción usada para sustituir dicho no terminal.
- Los nodos que no tienen hijos deben estar etiquetados con símbolos terminales.

Antonio Carrillo Rodríguez

# data[].attributes.body
Σ ={a,b}

S->aSa | bSb | a | b | Ɛ

-Toledo David

# data[].attributes.attachment_link.title
Lenguaje formado por palíndromos es Libre de Contexto

# data[].attributes.body
Ejemplo: Dirección Postal en México.
<dirección_postal>::=<nombre><dirección>
<nombre>::=<nombre(s)><apellido_paterno><apellido_materno>
<dirección>::=<calle><no.interior><no.exterior><colonia><municipio_o_delegación><código_postal><ciudad><país>

<nombre>::={[A-Z]|[a-z]}
<apellido_paterno>::={[A-Z]|[a-z]}
<apellido_materno>::={[A-Z]|[a-z]}
<calle>::={[0-1]|[A-Z]|[a-z]}
<no.exterior>::={L|[0-1]}
<no.interior>::=<Mz|[0-1]>
<colonia>::={[A-Z]|[a-z]}
<municipio_o_delegación>::={[A-Z]|[a-z]}
<código_postal>::={[0-1]}
<ciudad>::={[A-Z]|[a-z]}
<país>::={[A-Z]|[a-z]}

Lourdes Delfino Alejo

# data[].attributes.attachment_link.description
Notación BNF (Backus Naur-Form) La notación BNF es un metalenguaje, esto se dice porque se le usa para describir otro lenguaje, es una nomenclatura que nos permite una descripción compacta y precisa de los constructores sintácticos usando ciertos símbolos y reglas. Algunos

# data[].attributes.body
Valadez González Jovani

# data[].attributes.headline
Aplicaciones GLC y Analizadores Sintácticos

# data[].attributes.subject
Aplicaciones GLC y Analizadores Sintácticos

# data[].attributes.body
Las GLC permiten el diseño de algoritmos de análisis sintácticos, los cuales analizan una cadena de símbolos de acuerdo a las reglas de una gramática formal. Existen dos tipos de analizadores sintácticos, los LL y los LR.

Zúñiga Grajeda Said Alejandro

# data[].attributes.body
(VALADEZ GONZÁLEZ JOVANI)
Podemos decir que un GLC es ambiguo si existe alguna palabra perteneciente al lenguaje que genera, que tenga más de un árbol de derivación.

# data[].attributes.body
Pueden ser reconocidos por un autómata de pila determinístico o no determinístico.

# data[].attributes.body
Nava Romero Omar Aldahir

# data[].attributes.body
-La derivación por la izquierda se refiera a remplazar la variable mas a la izquierda por uno de las variables de producción.
- Derivación mas a la derecha siempre reemplaza la variable mas a la derecha por uno de los conjuntos de sus producciones.

# data[].attributes.body
Valadez González Jovani

# data[].attributes.headline
Gramáticas libres de contexto y ambiguas en JFlap

# data[].attributes.subject
Gramáticas libres de contexto y ambiguas en JFlap

# data[].attributes.attachment_link.title
Gramaticas Libres de Contexto y Ambiguas en JFlap

# data[].attributes.headline
LENGUAJES LIBRES DE CONTEXTO // JUAN JOSÉ RIOS ALONSO

# data[].attributes.subject
LENGUAJES LIBRES DE CONTEXTO // JUAN JOSÉ RIOS ALONSO

# data[].attributes.body
GRÁMATICAS DE TIPO 2.

Es una gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte izquierda la cual debe ser un no terminal y la parte derecha puede ser tanto terminales como no terminales.

Todas las gramáticas se pueden definir mediante un formato estándar, de tal manera que las reglas de producción adopten más comprensibles o más fáciles de implementar con un computador.

# data[].attributes.body
Las derivaciones por la izquierda y por la derecha presentadas definen la sintaxis del árbol.

# data[].attributes.headline
Los lenguajes regulares son libres de contexto porque pueden ser descritos mediante una gramática de libre contexto.

# data[].attributes.subject
Los lenguajes regulares son libres de contexto porque pueden ser descritos mediante una gramática de libre contexto.

# data[].attributes.body
Victor Manuel Sevillano Mendoza

# data[].attributes.body
Una gramática es ambigua si el lenguaje que define contiene alguna cadena que tenga más de un árbol de análisis sintáctica.
- No es posible construir analizadores eficientes para gramáticas ambiguas.
- Con ciertas restricciones a la gramática se podría afirmar que no hay ambigüedad.

Flores Ponce Alan Marcelo

# data[].attributes.attachment_link.title
Derivaciones para gramáticas libres de contexto

# data[].attributes.body
Castillo David

# data[].attributes.body
Cada regla en BNF sigue la siguiente estructura:

< antecedentes >::=< consecuentes >

El símbolo :: = significa “puede expandirse en” y “puede ser reemplazado por”.

Los símbolos terminales en ocasiones se expresan entre comillas simples o dobles.

Cada antecedente en forma BNF está rodeado por paréntesis , <>, ya sea que aparezca en el lado izquierdo o derecho de la regla.

Una barra vertical | indica elección.(OR lógico)

Un ejemplo de expresión en gramática BNF sería

<expresión> ::= <termino> “+” <expsiór> | <termino>

# data[].attributes.body
Castillo David

# data[].attributes.body
Todo lenguaje formal generado por una GLC y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Libre de Contexto (LLC).

PDF sobre los LLC:
https://ocw.unican.es/pluginfile.php/1516/course/section/1946/3-1_Introduccion.pdf

# data[].attributes.body
Los símbolos inútiles son aquellos de los que no se deriva ninguna cadena de símbolos terminales.
Los símbolos inaccesibles son aquellos que no pueden ser generados a partir del axioma.

# data[].attributes.attachment_link.readable_text
Published on

tipos de gramatica, arboles de derivacion, gramaticas limpias y bien formadas, lenguajes naturales y artificiales.

1. 1. Exposición de Compiladores e Intérpretes Profesor: Eddie Christian Malca Vicente Integrantes: *Jorge Luis Severino Vicharra *Elmer André Boulangger Alberca *Jesús Huamaní Taipe *Jhon Rodríguez Silva

2. 2. Tipos de Gramática o Una gramática es una estructura algebraica formada por cuatro elementos o G={NT, T, S, P} o NT es el conjunto de elementos NO TERMINALES o T es el conjunto de elementos TERMINALES o S es el SIMBOLO INICIAL de la gramática o P es el conjunto de REGLAS DE PRODUCCION

3. 3. Gramática tipo 0 Características o No tiene restricciones . o Incluyen a todas las demás gramáticas formales. o Las maquinas que lo aceptan son maquinas de Turing.

4. 4. Gramática tipo 1 Características o Generan los lenguajes sensibles al contexto. o Las maquinas que los aceptan son autómatas linealmente acotados.

5. 5. Gramática tipo 2 Características o Generan los lenguajes independientes del contexto. o Maquinas que lo aceptan son autómata de pila.

6. 6. Gramática tipo 3 Características o También llamadas de contexto regular. o Maquinas que lo aceptan son autómata finito, determinista o no determinista.

7. 7. Árboles de derivación Derivaciones utilizando una gramática

8. 8. Derivación * Aplicación de las producciones de una gramática para obtener una cadena de terminales. * Consiste en sustituir la variable de la cabeza por el cuerpo de la producción.

9. 9. Estructura  Un árbol es un conjunto de puntos, llamados nodos; unidos por líneas llamados arcos.

10. 10. Satisfacen ciertas propiedades  Hay un único nodo distinguido, llamado raíz.  Todo nodo "c" excepto el nodo raíz esta conectado con un arco a otro nodo "k", llamado padre de c. El padre de un nodo, se dibuja por encima de un nodo.  Todos los nodos están conectados al nodo raíz mediante un único camino.  Los nodos que no tienen hijos se denominan hojas, el resto de los nodos se denominan nodos interiores.

11. 11. Tipos de derivación Derivació n a la derecha. Derivació n a la izquierda.

12. 12. Ejemplo: 1. S  ASB 2. A  b 3. aaA  aaBB 4. S  d 5. A  aA 6. B  dcd

13. 13. Ejemplo 1. S  ASB 2. A  b 3. aaA  aaBB 4. S  d 5. A  aA 6. B  dcd Derivación a la izquierda S  ASB  aASB  abSB  abdB  abddcd Derivación a la derecha S  ASB  ASdcd  Addcd  aAddcd  abddcd 1 6 4 5 2 1 5 2 4 6

14. 14. Gramáticas limpias y bien formadas

15. 15. Gramáticas limpias y bien formadas Una gramática se llama reducida si no contiene símbolos inaccesibles ni reglas superfluas. Se llama limpia si tampoco contiene reglas innecesarias.

16. 16. Reglas innecesarias En una gramática, las reglas de la forma U: :=U son innecesarias y la hacen ambigua. A partir de ahora se supondrá que una gramática no tiene tales reglas o, si las tiene, serán eliminadas.

17. 17. Símbolos inaccesibles Para eliminar los símbolos inaccesibles, se hace una lista de todos los símbolos de la gramática y se marca el axioma S. se marcan todos los símbolos que aparezcan en la parte derecha de cualquier regla cuya parte izquierda sea un símbolo marcado. El proceso continúa hasta que no se marque ningún símbolo nuevo. Los símbolos que se queden sin marcar, son inaccesibles.

18. 18. Reglas superfluas Marcar los símbolos no terminales para los que exista una regla U::=x, donde x sea una cadena de símbolos terminales, o de no terminales marcados. Si todos los símbolos no terminales han quedado marcados, no existen símbolos superfluos en la gramática. Fin del proceso. Si la última vez que se pasó por el paso 1 se marcó algún símbolo no terminal, volver al primer paso. Si se llega a este punto, todos los símbolos no terminales no marcados son superfluos.

19. 19. Eliminación de símbolos no generativos Sea la gramática independiente del contexto G =(ΣT, ΣN, S, P).  Para cada símbolo A∈ΣN se construye la gramática G(A)=(ΣT, ΣN, A, P). Si L(G(A)) es vacío, se dice que A es un símbolo no generativo. Entonces se puede suprimir A en ΣN, así como todas las reglas que contengan A en P, obteniendo otra gramática más sencilla, que representa el mismo lenguaje.

20. 20. Eliminación de reglas de re-denominación Se llama regla de re-denominación a toda regla de la forma A::=B. Para compensar su eliminación, basta añadir el siguiente conjunto de reglas: Para cada símbolo A de ΣN tal que A→*B en G, y para cada regla de la forma B::=x, donde x no es un símbolo no terminal, añadiremos una regla de la forma A::=x.

21. 21. Lenguajes naturales y artificiales

22. 22.  Lenguaje Natural.- Se llama lenguaje natural al que utilizan los seres humanos en su comunicación ordinaria, porque ha sido formado paulatinamente mediante el uso del grupo social, a través de una dinámica histórica no intencionada.  Lenguaje Artificial.- Un lenguaje artificial es un lenguaje de programación que puede ser usado para controlar el comportamiento de una máquina, especialmente una computadora.

23. 23. Lenguajes de programación de computadoras

24. 24. Procesadores de lenguaje Dicho en forma simple, un compilador es un programa que puede leer un programa en un lenguaje (el lenguaje fuente) y traducirlo en un programa equivalente en otro lenguaje (el lenguaje destino). Si el programa destino es un programa ejecutable en lenguaje máquina, entonces el usuario puede ejecutarlo para procesar las entradas y producir salidas (resultados).

25. 25. Partes de un procesador de lenguaje

26. 26. Nota sobre sintaxis y semántica Análisis El objetivo de esta etapa es obtener una representación de la entrada que nos permita realizar la síntesis o la interpretación con comodidad. 1.- Análisis léxico En esta fase se analiza la entrada carácter a carácter y se divide en una serie de unidades elementales: los componentes léxicos. 2.- Análisis sintáctico Partiendo de lo que ha recibido del analizador léxico, la tarea del analizador sintáctico consiste en ir descubriendo las estructuras presentes en el código de acuerdo con una gramática no contextual. 3.- Análisis semántico La última fase del análisis, el análisis semántico, toma como entrada el árbol sintáctico y comprueba si, además de las restricciones sintácticas, se cumplen otras restricciones impuestas por el lenguaje y que no pueden ser comprobadas mediante una gramática no contextual.

# data[].attributes.attachment_link.title
Tipos de gramatica y arboles de derivacion

# data[].attributes.attachment_link.description
Published on tipos de gramatica, arboles de derivacion, gramaticas limpias y bien formadas, lenguajes naturales y artificiales. 1. Exposición de Compiladores e Intérpretes Profesor: Eddie Christian Malca Vicente Integrantes: *Jorge Luis Severino Vicharra *Elmer André Boulangger Alberca *Jesús Huamaní Taipe *Jhon Rodríguez Silva 2.

# data[].attributes.headline
La notación de Backus-Naur Extendida (EBNF) consiste en:

# data[].attributes.subject
La notación de Backus-Naur Extendida (EBNF) consiste en:

# data[].attributes.body
<Variable>::==<Expresión> donde:
::= se define como
<obligatoria>
[opcional]
{iteración}
| or

Ejemplo
<direccion_Postal>::=<nombre><direccion>

Martinez Martinez Fernando

# data[].attributes.body
Un árbol de derivación muestra gráficamente las posibilidades de derivación de cualquier cadena de un lenguaje a partir de un símbolo de una gramática generador de dicho lenguaje.
https://users.exa.unicen.edu.ar/catedras/ccomp1/Apunte5.pdf

# data[].attributes.body
Estos árboles nos ayudan a  mostrar gráficamente como se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje.

(Valadez González Jovani)

# data[].attributes.body
Para mostrar la derivación de cualquier cadena de un lenguaje a partir de una gramática se usan los "Árboles de derivación"

# data[].attributes.headline
Un lenguaje libre de contexto (LLC) puede solo ser reconocido por una gramática libre de contexto (GLC) donde G=.

# data[].attributes.subject
Un lenguaje libre de contexto (LLC) puede solo ser reconocido por una gramática libre de contexto (GLC) donde G=.

# data[].attributes.body
Y el LLC es aquel cuyas cadenas pueden ser reconocidas por autómatas de pila.
-Castillo Hernández Aldo Joel

# data[].attributes.body
Un árbol de derivación es la forma de mostrar gráficamente como se deriva cualquier cadena de un lenguaje, donde el árbol  de derivación esta formado por 3 tipos de nodos:
1.-  Nodo Raíz.
2.-  Nodos interiores.
3.-  Hojas

# data[].attributes.body
Esta jerarquía nos permite tener soluciones dependiendo el tipo de gramática que utilicemos, pueden ser :

Maquinas de Turing; Tipo 0

Autómatas de linea acotados; Tipo 1

Autómatas de pila; Tipo 2

Autómatas regulares y finito ; Tipo 3

# data[].attributes.attachment_link.readable_text
Published on

Jerarquía de Chomsky
Formatos Estándares de Tipo 0 y 1.

1. 1. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Gramática Lenguaje Modelo Matemático Recursivamente enumerable Máquina de Turing Tipo 0: Irrestricta (Nivel Pragmático) (MT) Dependiente del Tipo 1: Dependiente Contexto Autómata Linealmente del Contexto (Nivel Semántico) Limitado (ALL) Independiente del Tipo 2: Independiente Contexto Autómata de Pila (AP) del Contexto (Nivel Sintáctico) Regular Tipo 3: Regular Autómata Finito (AF) (Nivel Léxico) ING. JORGE BUABUD

2. 2. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Esta clasificación, realizada por Noam Chomsky a fines de la década de 1950, implica una jerarquía de los lenguajes generados por las gramáticas de cada tipo, ya que cada gramática de tipo X surge de aplicar ciertas restricciones al tipo X-1. De tal modo que el conjunto de lenguajes recursivamente enumerables contiene al conjunto de lenguajes dependientes del contexto, éste contiene a los lenguajes independientes del contexto y éstos a los regulares: L0 ⊃ L1 ⊃ L2 ⊃ L3 ING. JORGE BUABUD

3. 3. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: TIPO 0 (Irrestricta o Sin Restricciones - GI): Gramática estructurada por frases sin ninguna restricción. O sea que sus reglas de producción tienen, en la parte izquierda al menos un símbolo no terminal y en la parte derecha cualquier secuencia de terminales o no-terminales, inclusive vacía. Todo lenguaje formal generado por una GI y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Irrestricto o Recursivamente Enumerable (LI). ING. JORGE BUABUD

4. 4. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Ejemplo de Gramática Tipo 0: G = 〈 ΣN , ΣT , P, S 〉 ΣN = { S, U, V, X, Y, Z } ΣT = {a, b} P: S → UVX bV → Vb ZX → VbX YX → VaX Yb → bY Ya → aY Zb → bZ Za → aZ El lenguaje generado por esta gramática es: X→λ aV → Va ∈Σ L(G) = {ww / w∈ΣT* } UV → bUZ | aUY | λ ING. JORGE BUABUD

5. 5. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Veamos la generación de algunas palabras: S ⇒ UVX ⇒ X ⇒ λ S ⇒ UVX ⇒ aUYX ⇒ aUVaX ⇒ aaX ⇒ aa S ⇒ UVX ⇒ bUZX ⇒ bUVbX ⇒ baUYbX ⇒ baUbYX ⇒ baUbVaX ⇒ baUVbaX ⇒ babaX ⇒ baba ING. JORGE BUABUD

6. 6. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: TIPO 1 (Dependiente del / Sensible al Contexto - GDC): Gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte derecha, la cual no puede ser menor que la longitud de la parte izquierda. O sea que no tienen reglas compresoras. Excepto la regla de borrado S → λ , siempre que S no figure a la derecha de ninguna regla, con el único objetivo de generar la palabra vacía. Todo lenguaje formal generado por una GDC y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Dependiente del Contexto (LDC). ING. JORGE BUABUD

7. 7. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Ejemplo de Gramática Tipo 1: G = 〈 ΣN , ΣT , P, S 〉 ΣN = { S, T, B, D } ΣT = { a, b, c } P: S → T DB → BD El lenguaje generado por esta D→c gramática es: T → aTBD | abD L(G) = {an bn cn / n ≥ 1 } bB → bb ING. JORGE BUABUD

8. 8. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Veamos la generación de algunas palabras: S ⇒ T ⇒ abD ⇒ abc S ⇒ T ⇒ aTBD ⇒ aabDBD ⇒ aabBDD ⇒ aabbDD ⇒ aabbcD ⇒ aabbcc S ⇒ T ⇒ aTBD ⇒ aaTBDBD ⇒ aaabDBDBD ⇒ aaabBDDBD ⇒ aaabbDDBD ⇒ aaabbDBDD ⇒ aaabbBDDD ⇒ aaabbbDDD ⇒* aaabbbccc ING. JORGE BUABUD

9. 9. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: TIPO 2 (Independiente / Libre del Contexto - GIC): Gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte izquierda, que debe ser igual a 1. O sea que la parte izquierda es un no-terminal y la parte derecha puede ser cualquier secuencia de terminales o no-terminales. Todo lenguaje formal generado por una GIC y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Independiente del Contexto (LIC). ING. JORGE BUABUD

10. 10. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Ejemplo de Gramática Tipo 2: G = 〈 ΣN , ΣT , P, S 〉 ΣN = { S } ΣT = { a, b } El lenguaje generado por esta P: S → aSb | ab gramática es: L(G) = {an bn / n ≥ 1 } ING. JORGE BUABUD

11. 11. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Veamos la generación de algunas palabras: S ⇒ ab S ⇒ aSb ⇒ aabb S ⇒ aSb ⇒ aaSbb ⇒ aaabbb ING. JORGE BUABUD

12. 12. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: TIPO 3 (Lineal / Regular - GR): Gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte izquierda, que debe ser igual a 1. O sea que la parte izquierda es un no-terminal y la parte derecha puede ser una secuencia de terminales con un no-terminal como sufijo (GR por la derecha) o con un no-terminal como prefijo (GR por la izquierda) o simplemente una secuencia de terminales. Existe una equivalencia entre ambas formas. Todo lenguaje formal generado por una GR por la derecha o por la izquierda, se llama Lenguaje Regular (LR). ING. JORGE BUABUD

13. 13. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Ejemplo de Gramática Tipo 3 (regular por derecha): G = 〈 ΣN , ΣT , P, S 〉 ΣN = { S, A } ΣT = { a, b } El lenguaje generado por esta P: S → bbS | aaA gramática es: A → aaA | bb ≥ ≥ L(G) = {(bb)n (aa)k bb / n≥0, k≥1} ING. JORGE BUABUD

14. 14. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Veamos la generación de algunas palabras: S ⇒ aaA ⇒ aabb S ⇒ aaA ⇒ aaaaA ⇒ aaaabb S ⇒ bbS ⇒ bbaaA ⇒ bbaabb S ⇒ bbS ⇒ bbaaA ⇒ bbaaaaA ⇒ bbaaaabb ING. JORGE BUABUD

15. 15. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Ejemplo de Gramática Tipo 3 (regular por izquierda): G = 〈 ΣN , ΣT , P, S 〉 El lenguaje generado por esta gramática es: ΣN = { S } ΣT = { a, b } L(G) = {aaa, bbb}.{ab,ba}* P: S → Sab | Sba | aaa | bbb ING. JORGE BUABUD

16. 16. U.T.N. - F.R.T. S. y S. de los L. GRAMÁTICAS Y MODELOS MATEMÁTICOS JERARQUÍA DE CHOMSKY: Veamos la generación de algunas palabras: S ⇒ Sab ⇒ aaaab S ⇒ Sba ⇒ Sabba ⇒ bbbabba S ⇒ Sba ⇒ Sbaba ⇒ Sabbaba ⇒ aaaabbaba S ⇒ Sab ⇒ Sabab ⇒ Sbaabab ⇒ bbbbaabab ING. JORGE BUABUD

17. 17. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATOS ESTÁNDARES: Para todas las gramáticas se puede definir un formato estándar, de tal modo que las reglas de producción adopten formas más comprensibles o más fáciles de implementar con un computador. Como veremos en algunos casos el formato de las reglas puede poner en evidencia características del lenguaje generado por las mismas. Por ejemplo en las de Tipo 1 se puede apreciar la dependencia del contexto en la derivación de las palabras. → En otros casos las reglas de borrado (N→λ) pueden traer como consecuencia la posibilidad de derivaciones arbitrariamente largas. Por ejemplo la siguiente gramática de Tipo 2 que genera paréntesis bien balanceados (damos sólo las reglas): 1. S → SS 2. S → (S) 3. S → λ ING. JORGE BUABUD

18. 18. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATOS ESTÁNDARES: Con esta gramática es posible hacer derivaciones arbitrariamente largas de una palabra tan sencilla como "( )" (el subíndice de las flechas indica la regla utilizada): S ⇒1 SS ⇒1 SSS ⇒1 . . . ⇒3 SSS ⇒3 SS ⇒3 S ⇒2 (S) ⇒3 ( ) Si pudiéramos tener una gramática equivalente, pero sin reglas que produzcan la cadena vacía, ya no sería posible hacer derivaciones arbitrariamente largas. Esto puede ser una ventaja a la hora de determinar si una palabra se deriva o no de una gramática, o sea en el proceso de análisis del lenguaje generado por la gramática. ING. JORGE BUABUD

19. 19. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR DE TIPO 0: En el caso de las gramáticas de tipo 0 o irrestrictas, se puede transformar las reglas para obtener una gramática equivalente de la forma: N1N2....Ni → M1M2....Mj | λ donde "t" es un terminal y los F.E.T.0 "N" y "M" son no-terminales. N→t La transformación consiste en reemplazar todos los terminales de las reglas que no cumplen con este formato, por nuevos símbolos no- terminales y agregar reglas de la forma "nuevo no-terminal deriva a terminal correspondiente". ING. JORGE BUABUD

20. 20. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 0: Por ejemplo, la GI vista anteriormente quedaría: G = 〈 ΣN , ΣT , P, S 〉 ΣN = { S, A, B, U, V, X, Y, Z } ΣT = {a, b} P: S → UVX BV → VB ZX → VBX YX → VAX YB → BY YA → AY ZB → BZ ZA → AZ X→λ AV → VA UV → BUZ | AUY | λ A→a B→b ING. JORGE BUABUD

21. 21. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: En el caso de las gramáticas de tipo 1 o dependientes del contexto, se puede transformar las reglas para obtener una gramática equivalente de la forma: α1 N α2 → α1 β α2 N ∈ ΣN , β ∈ Σ+ , αi ∈ Σ* F.E.T.1 S→ λ Pero S no figura a la derecha de ninguna regla de producción. Podemos decir que N puede reemplazarse por β siempre que N esté en el contexto (α1 , α2). En este formato se pone de manifiesto la α dependencia del contexto de este tipo de gramática. Recordemos que la excepción "S → λ" solo sirve para generar la palabra vacía, cuando así lo requiera el lenguaje. ING. JORGE BUABUD

22. 22. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: La transformación de las reglas que no cumplen con el formato estándar, se puede formalizar mediante los siguientes pasos: 1) Obtener el "F.E.T. 0" de las reglas en cuestión. 2) Para cada regla de la forma: X1X2...XL → Z1Z2...ZK donde los (Xi , Zj) son no-terminales, se debe agregar los no- terminales nuevos Y1, Y2, ... , YL y reemplazarla por las siguientes producciones: ING. JORGE BUABUD

23. 23. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: X1X2...XL → Y1X2...XL Y1X2X3...XL → Y1Y2X3...XL .............................. Y1Y2...YL-1 XL → Y1Y2...YL-1YLZL+1...ZK Y1Y2...YL-1YLZL+1...ZK → Z1Y2...YLZL+1...ZK .............................. Z1Z2...ZL-1YLZL+1...ZK → Z1Z2...ZK Se puede verificar que estas reglas cumplen con el formato estándar de tipo 1 y que son equivalentes a la regla de partida. ING. JORGE BUABUD

24. 24. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: Apliquemos estos pasos al ejemplo de GDC visto anteriormente: 1) La única regla que no cumple con el formato estándar es: DB → BD, y ya está en el "F.E.T. 0". 2) Agregamos los nuevos no-terminales: E, F y reemplazamos la regla en cuestión por las siguientes producciones: DB → EB EB → EF EF → BF BF → BD ING. JORGE BUABUD

25. 25. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: De tal modo que la GDC equivalente resulta ser: G = 〈 ΣN , ΣT , P, S 〉 ΣN = { S, T, B, D, E, F } ΣT = { a, b, c } P: S → T DB → EB EB → EF EF → BF BF → BD D→c T → aTBD | abD bB → bb ING. JORGE BUABUD

26. 26. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: Veamos ahora un ejemplo arbitrario de una regla de tipo 1, que no cumple con el formato estándar: aXb → YcZde 1) Agregamos los nuevos no-terminales: A, B, C, D, E y reemplazamos la regla por las siguientes producciones: AXB → YCZDE A→a B→b C→c D→d E→e ING. JORGE BUABUD

27. 27. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: 2) Agregamos los nuevos no-terminales: F, G, H y reemplazamos la regla : AXB → YCZDE por las siguientes producciones: AXB → FXB FXB → FGB FGB → FGHDE FGHDE → YGHDE YGHDE → YCHDE YCHDE → YCZDE ING. JORGE BUABUD

28. 28. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: De tal modo que la regla de partida se sustituye por las siguientes producciones: AXB → FXB A→a FXB → FGB B→b FGB → FGHDE C→c FGHDE → YGHDE D→d YGHDE → YCHDE E→e YCHDE → YCZDE Como vemos todas las reglas cumplen con el formato dependiente del contexto. ING. JORGE BUABUD

29. 29. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: Analicemos ahora el problema de agregar la generación de la palabra vacía a una GDC que originalmente no la genera. Se presentan dos casos: 1) Si ninguna de las producciones de la GDC contiene el axioma en su parte derecha, se agrega la regla de borrado: S → λ como excepción de regla compresora, que tendrá como único efecto permitir la derivación de la palabra vacía. 2) Si el axioma aparece en la derecha de alguna producción, entonces se realiza el siguiente artificio: a) se introduce un nuevo símbolo inicial S1 b) se agrega a las producciones originales las reglas: S1 → S | λ ING. JORGE BUABUD

30. 30. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: En el ejemplo de GDC que hemos visto, se presenta el primer caso. De tal modo que si deseamos agregar la generación de la palabra vacía, la gramática resultante sería: G = 〈 ΣN , ΣT , P, S 〉 ΣN = { S, T, B, D } ΣT = { a, b, c } P: S → T | λ DB → BD El lenguaje generado por esta D→c gramática es: T → aTBD | abD bB → bb L(G) = {an bn cn / n ≥ 0 } ING. JORGE BUABUD

31. 31. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: Veamos por último un ejemplo del segundo caso: G = 〈 ΣN , ΣT , P, S 〉 ΣN = { S, A } ΣT = { a, b } P: S → bSbb | SAS Sb → aaA A → bb ¿ Qué lenguaje genera esta gramática ? SA → aa ING. JORGE BUABUD

32. 32. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATO ESTÁNDAR TIPO 1: La GDC equivalente que genera la palabra vacía es: G = 〈 ΣN , ΣT , P, S1 〉 ΣN = { S1, S, A } ΣT = { a, b } P: S1 → S | λ S → bSbb | SAS Sb → aaA A → bb ¿ Qué lenguaje genera esta gramática ? SA → aa ING. JORGE BUABUD

33. 33. U.T.N. - F.R.T. GRAMÁTICAS Y MODELOS S. y S. de los L. MATEMÁTICOS FORMATOS ESTÁNDARES TIPO 2 y 3: Los siguientes son los formatos estándares de tipo 2 y tipo 3, cuya obtención veremos cuando profundicemos el estudio de los lenguajes independientes del contexto y regulares respectivamente: Forma Normal de Chomsky Forma Normal de Chomsky N1 → N2N3 N1 → tN2 FNC 2 N→t FNC 3 N→t S→λ S→λ Forma Normal de Greibach N∈ΣN , t∈ΣT , W∈ΣN* y ∈Σ ∈Σ ∈ → si tiene la regla S→λ , entonces N → tW S no figura a la derecha de FNG 2 S→λ ninguna regla de producción. ING. JORGE BUABUD

# data[].attributes.attachment_link.title
Gramáticas y Modelos Matemáticos - Clase 3

# data[].attributes.attachment_link.description
Published on Jerarquía de Chomsky Formatos Estándares de Tipo 0 y 1. 1. U.T.N. - F.R.T. S. y S. de los L.

# data[].attributes.body
La notación Extended BNF es un metalenguaje usado para expresar gramáticas libres de contexto. Esta es una extensión de la notación BNF y añade algunos símbolos nuevos

# data[].attributes.body
Dentro de un lenguaje de programación, para mantener balanceados los paréntesis

Castillo Rodríguez David I.

# data[].attributes.body
Es una gramatica formal en la cual "Libre de contexto" hace referencia a que una variable no terminal puede ser sustituida sin importar el contexto en el que ocurra.

# data[].attributes.body
Para las producciones existen dos tipos de derivación:

# data[].attributes.body
Fue desarrollada para representar la gramática del Algol 60 por John Backus (Estados Unidos) y Peter Naur (Dinamarca).

# data[].attributes.body
Una gramática es ambigua cuando tiene mas de una derivación a la izquierda

# data[].attributes.body
El nombre "libres de contexto" hace referencia a que la terminación V puede ser sustituido por W sin tener en cuenta el contexto

Alejo Gonzalez Alexis Alan

# data[].attributes.body
La notación Backus-Nour o Backus-Nour Form es la notación más utilizada para poder expresar gramáticas libres de contexto.
Es considerado un metalenguaje que permite especificar la sintaxis de un lenguaje formal, es decir, proporciona una forma de describir estas gramaticas o lenguajes libres de contexto.

-Juan Roldán Gómez

# data[].attributes.headline
Aplicaciones de las gramáticas libres de contexto x2

# data[].attributes.subject
Aplicaciones de las gramáticas libres de contexto x2

# data[].attributes.body
Actualmente también son muy importantes para XML y sus DTD's (document type definition)

Sandoval Pérez Julio César

# data[].attributes.body
Dentro de la Jerarquía de Chomsky, los lenguajes libres de contexto son los ubicados en el nivel 2.
Los LLC son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico.

# data[].attributes.headline
Aplicaciones de las gramáticas libres de contexto

# data[].attributes.subject
Aplicaciones de las gramáticas libres de contexto

# data[].attributes.body
Los lenguajes de programación son su principal aplicación.

Podemos observarlo en la Definición del Tipo de Documento (DTD) para describir un XML

Castillo Rodríguez David I.

# data[].attributes.body
Las gramáticas libres de contexto son utilizadas principalmente para establecer las reglas en los lenguajes de programación

# data[].attributes.body
Los lenguajes libres de Contexto tienen gran aplicación en la teoría  y construcción de intérpretes y compiladores de lenguajes de programación.

# data[].attributes.body
Pablo Aliss

Formalmente una Gramática Libre de Contexto se define como:

G=(V,T,P,S)
donde:

V Conjunto de variables
T Conjunto de terminales
P Conjunto finito de producciones de la forma
A -> α donde A  es una variable y α ∊ (V u T)*
S es una variable designada llamada símbolo inicial

# data[].attributes.body
Una Gramática libre de Contexto es aquella estructura precisa de un Lenguaje, dicho lenguaje compone de reglas y símbolos en un alfabeto valido. Formalmente, los podemos conocer como Lenguajes Regulares, donde tiene una notación de caracteres.

# data[].attributes.body
Estas gramáticas se conocen como tipo 2 o gramáticas independientes de la jerarquía de Chomsky

# data[].attributes.body
Creada en 1956 por Noam Chomsky para clasificar las gramáticas de acuerdo a su tipo de lenguaje.
Luz María Sánchez García