Gramáticas

En esta página vamos a explicar cosas acerca de las gramáticas formales, como por ejemplo que son las gramáticas formales, notación en forma de Backus, la jerarquía de Chomsky, pasar una gramática desformalizada a forma normal de Chomsky, pasar de una gramática desformalizada a forma normal de Greibach, etc.

-¿ Que es una gramática?

Una gramática describe la estructurade las frases y de las palabras de un lenguaje y se aplica por igual a:
•Las lenguas naturales humanas
•Lenguajes de programación.
Una gramática es un “ente formal” para especificar de manera finita el conjunto de cadenas de símbolos que constituyen un lenguaje.

Por ejemplo, la sintaxis de la lengua castellana puede representarse mediante
reglas que definen las partes de la oración.

  • Así, toda frase tiene una serie de reglas (Ej: Una oración consta de sujeto y predicado).
  • Estas reglas definen ciertos términos en función de otros semejantes y para representarlas se utiliza una notación denominada:Regla de Producción:

{término a definir} ::= {definición}

Regla de Producción:

  • El término a definir se llama: parte izquierda. Su definición es la parte derecha (de la regla).

Ejemplo:
<oración> ::= <sujeto> <predicado>

Gramática Formales. Definición

Como se determina(define) unagramática.
Es una cuádrupla: (T, N, S, P), Ty N son alfabetos:

  • T:Alfabeto de símbolosterminales:

Todas lascadenas del lenguaje representado porla G (L(G)) están formadas con símbolos de este alfabeto.

  • N: Alfabeto de símbolos No Terminales.

Conjuntode símbolos auxiliares introducidos como elementos auxiliares para la definición de G pero que no figuran en las cadenas de L(G).

  • S:Axioma o símbolo destacado.

Es un símbolo NT a partir del que se comienzan a aplicar las reglas de P.

  • P: conjunto de reglas de producción:

u::=v
u = xAy

EJEMPLO DE GRAMÁTICA FORMAL

ejemplo de gramáticaNotación de Backus

La notación de Backus es muy utilizada para la identificación de las gramáticas, ahora explicaremos como se utiliza Backus y cuales son las utilidades de Backus

  • Notación de Backus:

Si u::=vy u::= w son dos reglas de producción de P, entonces se puede escribir u ::= v | w

  • Se denomina notación BNF:

Forma Normal de Backus o Forma Normal de Backus – Naur

Ejemplo de Backus:
sea G = ({0,1,2,3,4,5,6,7,8,9}, {N,D}, N,P)
P = { N::= ND |D ; D::= 0|1|2|3|4|5|6|7|8|9}

Gramática sin notación de Backus:
G = ({0,1}, {N,C}, N,P)
P = {N::= NC,
N::=C,
C::= 0,
C ::=1}

Gramática con notación de Backus:

G = ({0,1}, {N,C}, N,P)

P= {N::= NC | C,

C::= 0 | 1}

Lenguaje asociado a una gramática

Sea la gramática:
G1= (T, N, S, P)
Se llama lenguaje asociado a G1 o lenguaje generado por G1 o o lenguaje descrito por G1 al conjunto de todas las sentencias (palabras) generadas por G1.

Gramáticas formales con recursividad

Sea G
Una Gse llama recursiva en U, U € NT, si se cumple:
U +x U y
Si x = (U +U y)se dice que Ges recursiva a izquierdas
Si y = (U +x U)se dice que G es recursiva a derechas
Una regla de producción es recursiva si tiene la forma:
U ::= x U ylSi un lenguaje es infinito, la gramática que lo representa tiene que ser recursiva

Jerarquía de Chomsky

La jerarquía de Chomsky se divide en cuatro grupos, G0, G1, G2, G3, en las que cada una tiene sus restricciones, La G0 es la que menos restricciones tiene, y la G3 es la que más restricciones tiene, adjuntamos imagen para que se vea la estrutura de la jerarquía de Chomsky:

Estructura de Chomsky

Chomsky

Chomsky G0

Jerarquía de Chomsky, gramaticas

Chomsky G1

chomsky g1 gramática

Chomsky G2

Chomsky gramática

Chomsky G3

Chomsky gramatica

Resumen de la jerarquía de Chomsky

Chomsky

• Un Lenguaje se denomina de tipo i (i= 0, 1, 2, 3) si existe una G tipo i tal que L= L(Gi)
• Jerarquía de Chomsky: relación de inclusión:   G3 Pertenece a G2 Pertenece a G1 Pertenece a G0.

Gramáticas equivalentes

Dos Gramáticas son equivalentes si representan el mismo lenguaje.
Dada una gramática lineal por la derecha cualquiera, existe otra gramática lineal por la izquierda equivalente y viceversa.

Algoritmo para crear gramáticas equivalentes

PASO 1. Construir una gramática equivalente que no sea recursiva en el axioma.
PASO 2. Construcción de un grafo dirigido a partir de la gramática.
PASO 3. Se intercambian las etiquetas y se construye un nuevo grafo.

Árboles de derivación

•A las derivaciones de las G tipo 1, 2 y 3les corresponde un árbol de derivación equivalente, también llamado “árbol sintáctico” ó “parse tree”
•Representa las producciones aplicadas durante la generación de una sentencia, es decir, su estructura de acuerdo con la G

•Es un árbol ordenado y etiquetado que se construye:
– La raíz se denota por el axioma de G (S habitualmente)
– Una derivación directa se representa por un conjunto de ramas que salen de un nodo dado (parte izquierda de la P)
– Aplicar una regla un símbolo de la parte izq. queda sustituido por una palabra ude la parte dch. Por cada uno de los símbolos de u se dibuja una rama que sale del NT a ese símbolo:

1 comentario (+add yours?)

  1. Bienvenidos a nuestro nuevo blog « Automátas, gramáticas y lenguajes formales
    Feb 29, 2012 @ 09:25:07

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: