CIENCIAS DE LA COMPUTACION
alekemada9 de Mayo de 2014
3.670 Palabras (15 Páginas)228 Visitas
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 describe el lenguaje vacío;
- es una expresión regular que describe el lenguaje { }, esto es el lenguaje que contiene
únicamente la cadena vacía;
- Para cada símbolo a A, a es una expresión regular que describe el lenguaje {a}, esto es el
lenguaje que contiene únicamente la cadena a;
- Si r y s son expresiones regulares que describen los lenguajes L(r) y L(s) respectivamente:
i) r + s es una expresión regular que describe el lenguaje L(r)
L(s)
ii) r . s es una expresión regular que describe el lenguaje L(r) . L(s)
iii) r* es una expresión regular que describe el lenguaje L(r)*.
El operador de clausura es el que tiene mayor precedencia, seguido por el operador de
concatenación y por último el operador de unión.
Las expresiones regulares describen los lenguajes regulares (aquellos reconocidos por autómatas
finitos).
Por ejemplo las siguientes son expresiones regulares válidas:
- a* . b que describe el lenguaje L = {anb / n
0}
- (a + b)* que describe el lenguaje L = { x / x {a, b}* }
Leyes algebraicas para expresiones regulares
Dos expresiones regulares r y s son equivalentes (r s) si L(r) = L(s)
Sean r, s y t expresiones regulares:
1) r + + r r
2) r . . r r
3) r . . r
4) r + s s + r
5) (r + s) + t r + (s + t)
6) (r . s) . t r . (s . t)
7) r . (s + t) r . s + r . t
8) (s + t) . r s . r + t . r
9) r + r r
10) *
11) r . r* r* . r
12) r . r* + r*
13) (r* . s*)* (r + s)*
14) (r*)* r*
Construcción de autómatas finitos a partir de expresiones regulares
Los lenguajes descriptos por expresiones regulares son los lenguajes reconocidos por los autómatas
finitos. Existe un algoritmo para convertir una expresión regular en el autómata finito no
determinístico correspondiente. El algoritmo construye a partir de la expresión regular un autómata
con transiciones vacías, es decir un autómata que contiene arcos rotulados con . Luego este
CIENCIAS DE LA COMPUTACION I 2008
autómata con transiciones vacías se puede convertir en un autómata finito sin transiciones vacías
que reconoce el mismo lenguaje.
Construcción del autómata finito con transiciones
Si r es una expresión regular con n operadores y sin variables como operandos atómicos, existe un
autómata finito no determinístico M con transiciones (AFND- ) que acepta solamente aquellas
cadenas que están en L(r). M tiene un estado final, no entran arcos al estado inicial y no salen arcos
del estado final.
r puede ser una expresión sin operadores (, o un símbolo) o con operadores (+, ., *).
Si r no tiene operadores, entonces:
...