028 - Gramáticas Regulares

Universidad Mariano Galvez

GRAMATICAS

Ing. Maicol García

Que es una Gramática

Conjunto de reglas y símbolos que generan todos los patrones posibles para un lenguaje. Y al final generan un lenguaje como resultado.

(aa)*

Gramaticas Regulares (GR)

La descripción de la gramatica se basa en:

Simbolos Terminales T

Conjunto finito de Simbolos del lenguaje. (los llmaremos Mínusculas) podemos mencionar el alfabeto: {a,b,c} ó {0,1,} (TRANSICIONES)

Actuan a modo de variables. Y representan un conjunto de cadenas que se derivan a partir de ese simbolo no terminal. (los llamaremos MAYUSCULAS) Podemos mencionar los estados del automata. (ESTADOS)

Simbolos NO terminales V

Es el que pertenece al conjunto de símbolos no terminales y a partir del cual se comienzan a realizar las derivaciones de la gramática. (ESTADO INICIAL)

Símbolo Inicial S

Es un conjunto finito de producciones o reglas de reescritura que representan la definición recursiva de un lenguaje. (REGLAS DE TRANSICION)

Reglas de Producción P

ESTRUCTURA DE LAS GR

Para que sea una gramatica regular debe cumplir con estas dos normas:

EL lado izquierdo de las reglas de reescritura contiene un único símbolo no terminal. (MAYUSCULA)

Gramática Regular

El lado derecho de las reglas de reescritura contiene:

• Un único símbolo terminal
• ó Un símbolo terminal seguido de un símbolo no terminal
• ó el símbolo ε (épsilon)

S -> aA A -> aS A -> a S -> ɛ

Dada una grámatica regular el lenguaje que genera es siempre un LR(Lenguaje Regular) que puede representarse igualmente mediante un AF(Automata Finito) o mediante una ER (Expresión regular)

EJEMPLO #1

Expresión Regular a*

Diagrama de Estados

Lenguaje regular {ɛ, a, aa, aaa, aaaa....}

Derivación para Validar "ɛ"

Gramática Regular

S -> ɛ

S -> aS S -> ɛ

Derivación para Validar "a"

• V = No terminales {S}
• T = Terminales {ɛ, a}
• S = estado inicial
• P = 2 reglas de producción

S -> aS -> a

Derivación para Validar "aaaa"

S -> aS -> aaS -> aaaS ->aaaaS -> aaaa

EJEMPLO #2

Expresión Regular a*a

Diagrama de Estados

Lenguaje regular {a, aa, aaa, aaaa....}

Derivación para Validar "a"

Gramática Regular

S -> aS S -> aT T -> ɛ

S -> aT -> a

• V = No terminales {S, T}
• T = Terminales {ɛ, a}
• S = estado inicial
• P = 3 reglas de producción

Derivación para Validar "aa"

S -> aS -> aaT -> aa

Derivación para Validar "aaa"

S -> aS -> aaS -> aaaT -> aaa

GRAMATICAS REGULARES (GR)

"Un tipo especial de producción es aquella cuyo lado derecho tiene el simbolo e (epsilon). En este caso se considera que esta producción deriva al vacío y no genera ningún símbolo adicional"

S -> xA A -> xA A -> ɛ (Aceptación)

A -> ɛ

A -> xA

S -> xA -> S => xxA -> => S -> xx

"El conjunto de cadenas que se puede derivar de una determinada cadena forman un lenguaje. Así, dada una gramatica G, el lenguaje que genera se representa mediante la notación L(G) "

L = {x,xx,xxx,xxxx....} ER = xx*

GRAMATICA REGULAR (DERIVAR)

"Derivar una gramática consiste en ir substituyendo los símbolos no terminales por el lado derecho de la regla de reescritura en las que dichos si."

Derivamos "xxx"

S -> xA S -> yB A -> xA A -> x B -> yB B -> y

A -> x

A -> xA

S -> xA => S => xxA => S -> xxx

Derivamos "yyy"

B -> y

B -> yB

S -> yB => S => yyB => S -> yyy

L = {xx,yy,xxx,yyy,xxxx,yyyy....} ER = xx*x|yy*y

CREAR AUTÓMATA

Diagrama de Estados

Gramática Regular

S -> xA S -> yB A -> xA A -> xT B -> yB B -> yT T -> ɛ

EJERCICIO #1

Dado el alfabeto Σ = {x,y} y la siguiente gramatica regular.

S -> xS S -> yS S -> ɛ

Genere el lenguaje formado por todas las cadenas que se pueden formar, la expresión regular y el automata que lo representa.

EJERCICIO #2

Dado el alfabeto Σ = {x,y} y el siguiente automata:

Genere el lenguaje formado por todas las cadenas que se pueden formar, la expresión regular y la gramatica regular.

EJERCICIO #3

Dado el alfabeto Σ = {x,y} y la siguiente gramatica regular con simbolo Inicial S:

S -> xS S -> yS A -> yA A -> xA A -> ɛ

Genere el lenguaje formado por todas las cadenas que se pueden formar, la expresión regular y el automata.

EJERCICIO #4

Dado el alfabeto Σ = {x,y} y la siguiente gramatica regular con simbolo Inicial S:

S -> xA A -> y A -> xB B -> ɛ

Genere el lenguaje formado por todas las cadenas que se pueden formar, la expresión regular y el automata

EJERCICIO #5

Dado el alfabeto Σ = {a,b,c} y la siguiente gramatica regular con simbolo Inicial S:

S -> aA A -> aA | bB B -> bB | cC C -> cC | ɛ

Genere el lenguaje formado por todas las cadenas que se pueden formar, la expresión regular y el automata.

¡GRACIAS!