AREA DE ENERGIA LAS INDUSTRIAS Y LOS RECURSOS NATURALES NO
RENOVABLES
LENGUAJES FORMALES
GRAMATICAS REGULARES
Docente: Ingeniero Edison Coronel.
ALUMNA: Maricela Del Carmen Maldonado Cuenca.
FECHA: 27 DE Octubre del 2010
1
GRAMATICAS REGULARES
Son una herramienta muy poderosa para describir y analizar lenguajes.
Una gramática G es un cuádruplo (V, S, R, S) donde
1. V es un alfabeto.
2. S, el conjunto de los símbolos terminales, es un subconjunto
de V.
3. R, el conjunto de reglas de transformación o de producción,
es un subconjunto de V* × V*.
4. S, el símbolo inicial, es un elemento de V - S.
Los elementos de V - S son llamados variables o símbolos no
terminales.
Por lo general las reglas se escriben a ® b en lugar de (a, b).
Aplicar la regla a ® b a una palabra uav produce la palabra ubv, por lo
que las reglas pueden ser vistas como reglas de remplazo.
Explicación de los elementos de una gramática
• Símbolos terminales: son elementos del alfabeto que no se pueden
transformar, por eso se llaman terminales. Normalmente se
denotan por letras minúsculas.
• Variables o símbolos no terminales: son elementos auxiliares que
permiten poner restricciones sintácticas a un lenguaje. Las variables
sí se pueden transformar, utilizando las reglas, en una cadena de
variables y/o terminales. Por lo general se denotan por letras
mayúsculas o por la notación <variable>.
• Reglas: permiten reemplazar variables para generar oraciones
válidas de un lenguaje. Puede haber varias reglas para una misma
variable, en este caso y para ahorrar espacio, las distintas opciones
2
se colocan en una sola regla con los distintos reemplazos separados
por |. Por ejemplo
a®b|g|d
Abrevia las tres reglas
a®b a®g a®d
• Símbolo inicial: es el símbolo a partir del cual se generan todas las
palabras válidas.
Descripción de las gramáticas
• Gramáticas Regulares (tipo 3 o G3): el conjunto de reglas es un
subconjunto finito de (V - S) ´ [S(V - S) È S È l), es decir:
– El lado izquierdo consiste sólo de una variable.
– El lado derecho consiste de
• Un símbolo terminal seguido de una variable ó
• Sólo un símbolo terminal ó
• La cadena vacía.
Ejemplo: A ® aB | a | l
• Gramáticas Libres de Contexto, GLC, (tipo 2 o G2): el conjunto de
reglas es un subconjunto finito de (V - S) ´ V*, es decir:
– El lado izquierdo consiste sólo de una variable.
– No hay restricciones para el lado derecho.
Ejemplo: S ® aSb | ab | l
Una gramática regular es una gramática formal (N, Σ, P, S) que puede ser
clasificada como regular izquierda o regular derecha. Las gramáticas
regulares sólo pueden generar a los lenguajes regulares de manera similar
a los autómatas finitos y las expresiones regulares.
3
Dos gramáticas regulares que generan el mismo lenguaje regular se
denominan equivalentes. Toda gramática regular es una gramática libre
de contexto.
Una gramática regular derecha es aquella cuyas reglas de producción P
son de la siguiente forma:
1. A → a, donde A es un símbolo no-terminal en N y a uno terminal en
Σ
2. A → aB, donde A y B pertenecen a N y a pertenece a Σ
3. A → ε, donde A pertenece a N.
Análogamente, en una gramática regular izquierda, las reglas son de la
siguiente forma:
1. A → a, donde A es un símbolo no-terminal en N y a uno terminal en
Σ
2. A → Ba, donde A y B pertenecen a N y a pertenece a Σ
3. A → ε, donde A pertenece a N.
Una definición equivalente evita la regla 1 (A → a) ya que es sustituible
por:
A → aL
L→ε
en el caso de las gramáticas regulares derechas y por:
A → La
L→ε
en el caso de las izquierdas.
Algunos autores alternativamente no permiten el uso de la regla 3
suponiendo que la cadena vacía no pertenece al lenguaje.
Un ejemplo de una gramática regular G con N = {S, A}, Σ = {a, b, c}, P se
define mediante las siguientes reglas:
S → aS
S → bA
A→ε
4
A → cA
Donde S es el símbolo inicial. Esta gramática describe el mismo lenguaje
expresado mediante la expresión regular a*bc*.
Dada una gramática regular izquierda es posible convertirla, mediante un
algoritmo en una derecha y viceversa.
BIBLIOGRAFIA:
WIKIPEDIA Gramática regular 25 junio del 2010
http://es.wikipedia.org/wiki/Gram%C3%A1tica_regular
http://www3.uji.es/~martine/DOC/E45/T3/talf3/node4.html
http://www.exa.unicen.edu.ar/catedras/ccomp1/Apunte3.pdf
http://www.ual.es/~jsagrado/WALF/Archivos/Practicas/Unidad%204.pdf
