CIENCIAS DE LA COMPUTACION

CIENCIAS DE LA COMPUTACION I 2008

GRAMATICAS REGULARES - EXPRESIONES 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

  ,  = A y  = 

, ,  (N

T)* y A es S ó A N

- S es el símbolo distinguido o axioma S  (N

T)

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 N

{S}

A  aB ó A  a B N

a T

(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 N

{S}

A  Ba ó A  a B N

a T

(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 / n

0}

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  aB C  Da

A  a C  a

B  aA D  Ca

CIENCIAS DE LA COMPUTACION I 2008

Algoritmo para obtener la gramática regular desde el autómata finito

Existe un algoritmo que permite obtener una gramática regular que genera un lenguaje regular dado

a partir del autómata finito que reconoce ese lenguaje. Los pasos a seguir son los siguientes:

1) Asociar al estado inicial el símbolo distinguido S.

2) Asociar a cada estado del autómata (menos el estado inicial) un símbolo no terminal. Si al

estado inicial llega algún arco asociar también un símbolo no terminal (además del símbolo

distinguido). No asociar símbolo no terminal a aquellos estados finales de los que no salen

arcos.

3) Para cada transición definida  (ei, a) = ej, agregar al conjunto de producciones, la producción A

 aB, siendo A y B los símbolos no terminales asociados a ei y ej respectivamente. Si ej es un

estado final, agregar también la producción A  a. Si ej es el estado inicial (tiene dos símbolos

asociados, el distinguido y un no terminal), utilizar el símbolo no terminal (de esta manera se

evita que el símbolo distinguido aparezca a la derecha de una producción).

4) Si el estado inicial es también final agregar la producción S  .

Ejemplo 1:

Derivación de la gramática correspondiente al lenguaje del ej. 4 del apunte de autómatas finitos

L4 = { x / x {0, 1}* y x contiene la subcadena 00 ó x contiene la subcadena 11}

L4 = L(M4Dmin), M4Dmin = < {p0, p1, p2, p3}, {0, 1}, , p0, {p3}>

 está definida por el siguiente diagrama de transición de estados

Como al estado inicial no entran arcos, se asocia únicamente el símbolo distinguido S.

La gramática correspondiente a este lenguaje es

G = ({A, B, C}, {0, 1}, P, S), siendo P el siguiente conjunto:

S  0A ya que  (po, 0) = p1 y S y A están asociado a p0 y p1 respectivamente.

S  1B ya que  (po, 1) = p2 y S y B están asociado a p0 y p2 respectivamente.

A  0C

A  0

A  1B

B  0A

B  1C

B  1

C  0C

C  0

C  1C

C  1

p0

p1

p3

0 0

1

p2

1

1 0

0, 1

S

A

B

C

CIENCIAS DE LA COMPUTACION I 2008

Ejemplo 2:

Derivación de la gramática correspondiente al lenguaje del ej. 3 del apunte de autómatas finitos.

L3 = {xc3m/ x {a, b}* y la cantidad de b’s es par y m

0}, siendo L3 = L(M3D)

M3D = < {e0, e1, e2, e3, e4}, {a, b, c}, 3D, e0, {e0, e4}>

3D está definida por el siguiente diagrama de transición de estados

Como al estado inicial entran arcos, se asocia el símbolo distinguido S y además un símbolo no

terminal A.

La gramática correspondiente a este lenguaje es

G = ({A, B, C, D, E}, {a, b, c}, P, S), siendo P el siguiente conjunto:

S   (el estado inicial es también final) A  cC

S  aA B  aB

S  a B  bA (se usa el símbolo no terminal asociado al estado inicial)

S  bB B  b

S  cC C  cD

A  aA D  cE

A  a D  c

A  bB E  cC

Ejemplo 3:

Derivación de la gramática correspondiente al lenguaje del ej. 7 del apunte de autómatas finitos.

L7 = { a2nb2k+1 / n

1 y k

0}

{ax / x {a, b}* y x contiene la subcadena ba}

siendo L7 = L(M7Dmin), M7Dmin = < {p0, p1, p2, p3, p4, p5, p6}, {a, b}, , p0, {p3, p6}>

 está definida por el siguiente diagrama de transición de estados

La gramática correspondiente a este lenguaje es

G = ({A, B, C, D, E, F}, {a, b}, P, S), siendo P el siguiente conjunto:

S  aA B  bC C  a D  a F  aF

A  aB B  b D  bC E  bE F  a

A  bE C  bD D  b E  aF F  bF

B  aA C  aF D  aF E  a F  b

e0 e3 e4

b

c

e2

c

c

b

e1

c

a

a

S A

B

C D E

p1 p3

b

p5

b

p2

a

a

p4

b

b

p0

a

p6

a

a, b

b

a

a

S A B C D

E F

CIENCIAS DE LA COMPUTACION I 2008

Expresiones regulares

Se denominan expresiones regulares sobre un alfabeto A, a las expresiones que se pueden construir

a partir de las siguientes reglas:

-  es una expresión regular que

...