Clasificacion de gramaticas

Solo disponible en BuenasTareas
  • Páginas : 3 (726 palabras )
  • Descarga(s) : 0
  • Publicado : 11 de mayo de 2011
Leer documento completo
Vista previa del texto
CLASIFICACION DE LAS GRAMATICAS

GRAMÁTICAS TIPO 0
También llamadas gramáticas no restringidas con estructura de frase. Se caracterizan por:
* En la parte izquierda tiene que haber al menos unsímbolo no terminal.
* Respecto a sus partes derechas de producciones no hay ningún tipo de restricción.
* Las reglas de derivación son de la forma:
b®a
* Siendo a ÃŽ(VN È VT)+   y ÃŽb(VN È VT), es decir la única restricción es que no puede haber reglas de la forma
l®b
            donde l  es la cadena vacía.
* Ejemplos de estas gramáticas son todos los ejercicios que hemosvisto hasta ahora.
EJEMPLO
* Sea la gramática definida por: G= ({S}, {0,1},S,P)
donde
P={(S® 000S111), (0S1 ®01)} .
Determinar el lenguaje que genera.
SOLUCIÓN
L(G)={0(3n+1)1(3n+1)/ n>=0}GRAMÁTICAS TIPO 1
También llamadas gramáticas sensibles al contexto. Es decir que es importante tomar en cuenta la ubicación de los símbolos no terminales en la regla de derivación (que preceden ysuceden a cada símbolo Terminal, deben mantener su ubicación en el lado derecho de la regla de producción tal como aparece en la parte izquierda de la regla de producción).
En este tipo de gramática susreglas de producción son de la forma:
aAb ® bga
Siendo A ÃŽ VN
a, b Î (VN È VT) * y
gÎ (VN È VT)*
Estas gramáticas se llaman sensibles al contexto, pues se puede reemplazar A por g siempreque estén en el contexto a….b.
EJEMPLOS
* La gramática G=({S,A,B}, {a,b}, S, P) cuyas producciones P se muestran a continuación:
S ® aB
B ® bAb
bA®bcD
cD ®cAA
A ®aaA
A ®b
PROPIEDADES DE LASGRAMÁTICAS TIPO 1
* Propiedad de no decrecimiento.- Las cadenas que se obtienen en cualquier derivación de una gramática de tipo 1 son de longitud no decreciente, es decir:
a®b Þ êbê³ êaô             Y se puede enunciar como la longitud de la parte derecha de la producción es mayor o igual a la parte izquierda. Es decir no tiene reglas compresoras.
Se puede demostrar de la siguiente...
tracking img