GRAMATICAS REGULARES

 

Gramáticas:

Las gramáticas formales definen un lenguaje describiendo cómo se pueden generar las cadenas del
lenguaje.

Una gramática formal es una cuadrupla G = (N, T, P, S) donde:

– 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

Cada producción de P tiene la forma

α →β,  α =ȸAp y β=  ȸϖp

ȸ, ϖ, p Є (N ʋ  T)*  Y A es S o A Є N

– S es el símbolo distinguido o axioma S
Restringiendo los formatos de producciones permitidas en una gramática, se pueden especificar:
cuatro tipos de gramáticas (tipo 0, 1, 2 y 3) y sus correspondientes clases de lenguajes.
Gramáticas regulares (Tipo 3)
Generan los lenguajes regulares (aquellos reconocidos por un autómata finito). Son las gramáticas más restrictivas. El lado derecho de una producción debe contener un símbolo terminal y, como máximo, un símbolo no terminal. Estas gramáticas pueden ser:
– Lineales a derecha, si todas las producciones son de la forma

A → Ab  o  A → a

AЄ N ʋ {S}
B Є N

(en el lado derecho de las producciones el símbolo no terminal aparece a la derecha del símbolo terminal)
– Lineales a izquierda, si todas las producciones son de la forma

A → Ba  o  A → a
AЄ N ʋ {S}
Є N
(en el lado derecho de las producciones el símbolo no terminal aparece a la izquierda del símbolo terminal)
En ambos casos, se puede incluir la producción S → ɛ , si el lenguaje que se quiere generar contiene la cadena vacía.
Por ejemplo las siguientes gramáticas G1 y G2, son gramáticas regulares lineales a derecha y lineales a izquierda respectivamente, que generan el lenguaje L = {a2n / n0}
G1 = ({A, B}, {a}, P1, S1) G2 = ({C, D}, {a}, P2, S2)
donde P1 es el cjto. donde P2 es el cjto.

S1→ ɛ                          S2→ ɛ

S1→ aA                       S2→ Ca

A→a B                        C→Da

A→a                           C→a

B→aA                         D→Ca

 

VIDEO



GRAMATICAS REGULARES PDF

 

BIBLIOGRAFIA

http://www.exa.unicen.edu.ar/catedras/ccomp1/Apunte3.pdf



Licencia de Creative Commons
Lenguajes Formales by gramatica regular is licensed under a Creative Commons Attribution 3.0 Unported License.
Based on a work at israelp86.wordpress.com.