Gram ticas Regulares

Gramáticas Regulares
E N I N F O R M ÁT I C A U N A G R A M ÁT I C A R E G U L A R E S
U N A G R A M Á T I C A F O R M A L G = ( N , Σ , P, S ) Q U E
PUEDE
SER
CLASIFICADA
COMO
REGULAR
IZQUIERDA
OREGULAR
DERECHA.
LAS
G R A M ÁT I C A S
REGULARES
SÓLO
PUEDEN
GENERAR A LOS LENGUAJES REGULARES DE
MANERA
SIMILAR
A
LAS
EXPRESIONES
R E G U L A R E S.

ISC YURIVIA TORRES MERAZ

Nota:

Dosgramáticas regulares que
generan
el
mismo
lenguaje
regular
se
denominan
equivalentes.

Gramática regular derecha
Una gramática regular derecha es aquella
cuyas reglas de producción P son de la
siguienteforma:
A → a, donde A es un símbolo no-terminal
en N y a uno terminal en Σ
A → aB, donde A y B pertenecen a N y a
pertenece a Σ
A → ε, donde A pertenece a N.

Gramática regular izquierda
Unagramática regular izquierda, las
reglas son de la siguiente forma:
A → a, donde A es un símbolo no-terminal
en N y a uno terminal en Σ
A → Ba, donde A y B pertenecen a N y a
pertenece a Σ
A → ε, donde Apertenece a N.

Reglas
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 por la derecha
A → La

L → ε en el caso delas izquierdas.
Algunos

autores
alternativamente
no
permiten el uso de la regla 3 suponiendo que
la cadena vacía no pertenece al lenguaje.

Ejemplo
Un ejemplo de una gramática regular G

con N ={S, A}, Σ = {a, b, c}, P se define
mediante las siguientes reglas:
G=({S,A},{a,b,c},P,S)
S → aS
S → bA
A→ε
Probar cadena: aabcc
A → cA
Probar cadena: abc

Ejercicio 1
G=({a, b},{S,A},S,P)

P:
S bA
A  aaA | b | ε
Probar cadena: abaa
Probar cadena: baab

Ejercicio 2
G=({S,A,B}, {0,1}, P, S)

P:
SA
A  1B1
A  0B0
BA
B1
B0
Bε

Probar cadena: 1001
Probar cadena: 101

Ejercicio 3
Aplicael algoritmo a la gramática

siguiente: G=({S, A, B}, {a, b, c}, P, S)
siendo P el conjunto de producciones
S →aA |aB
A→bA |b
B→cB |c
Validar: accab
Validar: abb
Validar: accba

Ejercicio 4...