Metodo transformador

MÉTODO TRANSFORMADOR:
Conceptos:
� � Expresión regular: Es una notación para representar de una forma concisa la  forma de las palabras de un lenguaje regular sobre un determinado alfabeto. Derivada Dx[α]: Dada una expresión regular α y x que pertenece al alfabeto la  derivada de la expresión regular α con respecto al símbolo x, Đx[α] define el  lenguaje, conjunto de cadenas, que resultadel eliminar el prefijo x de todas las  palabras del lenguaje definido por la expresión regular. Gramática regular: Son mecanismos generadores de lenguajes regulares. Están compuestas por un alfabeto terminal ∑, un alfabeto no terminal N, un símbolo inicial S y un conjunto de producciones P.

�

G = { ∑, N, S, P} Descripción del método transformador utilizado:
El método transformador consiste en irderivando la expresión regular dada  respecto de cada uno de los símbolos terminales de ∑. Al derivar la expresión regular inicial podemos obtener otras expresiones regulares distintas a la expresión regular  inicial, la palabra vacía “ε” o el conjunto vacío “Ø”. Si hemos obtenido una expresión regular distinta a la inicial, derivamos esa  nueva expresión regular al igual que lo hemos hecho conla expresión regular inicial. Se debe repetir este procedimiento hasta que después de haber derivado todas las  expresiones regulares nuevas que nos vayan apareciendo obtengamos como resultado una expresión regular conocida, la palabra vacía “ε” o el conjunto vacío “Ø”. Una vez completado el proceso, habremos obtenido un conjunto de  expresiones regulares (α1,  α2,  α3, α4 … αn). A cada una de estasexpresiones  regulares les asignaremos un símbolo no terminal (A, B, …, Z)  y a la expresión regular inicial α le asignaremos el símbolo inicial S, según la siguiente notación:

α α1 α2
……..

S A B Z

αn

3

Para obtener el conjunto de producciones P de la gramática regular observamos los resultados obtenidos del proceso de derivación, para ello aplicamos tres criterios: 1.Si al derivar αi (i = 0,1,…,n) respecto de cualquier símbolo terminal del alfabeto, por ejemplo 0, se obtiene una nueva expresión regular, hay que tener en cuenta si la palabra vacía ε pertenece o no al lenguaje generado por la nueva expresión regular. � Si ε no pertenece al lenguaje generado por la nueva  expresión regular (Aj) añadimos la regla:

Ai
�

  0Aj | 0

Si ε pertenece al lenguaje generadopor la nueva expresión regular (Aj) añadimos la regla:

Ai

  0Aj | 0

2. Si al derivar αi (i = 0,1,…,n) respecto de cualquier símbolo terminal del alfabeto, por ejemplo 0, obtenemos la palabra vacía ε añadimos la regla:

Ai

  0

3. Si la palabra vacia ε pertenece al lenguaje generado por la expresión regular incial α, entonces añadimos la regla: S   ε
Cuando finalizamos este proceso,obtenemos el conjunto de producciones P de la gramática regular. Para comprobar si la gramática generada es correcta, solo hay que elegir palabras que pertenezcan al lenguaje que genera la expresión regular inicial α, y comprobar que se obtienen esas palabras aplicando las producciones obtenidas. Si elegimos una palabra que no pertenezca al lenguaje, no debemos ser capaz de generarla aplicando lasproducciones de la gramática.

4

EJEMPLO 1:
∑ = { 0, 1 } α Ξ 01* | 0*1
D0 [α] = 1* | 0*1  D1 [α] = ε α1 NUEVA ER

α1 Ξ 1* | 0*1
D0 [α1] = 0*1 D1 [α1] = 1* | ε α2 NUEVA ER α3 NUEVA ER α2

α2 Ξ  0*1
D0 [α2] = 0*1 D1 [α2] = ε

α3 Ξ  1* | ε
D0 [α3] = Ø D1 [α3] = 1* α4 NUEVA ER

α4 Ξ  1* 
D0 [α4] = Ø D1 [α4] = 1* α4

ASOCIACIÓN DE SÍMBOLOS
α  α1 α2 S A B α3 α4 C DPRODUCCIONES OBTENIDAS
(1)  S     0A (2)     | 1B   (3)  A    0B (5) B      0D   (7)  C       1D (4)     | 1C          (6)    | 1 (8)    | ε   (9) D    1D  (10) |1

Comprobación de la gramática obtenida
001 є L (α) S | 0A | 00B | (1)  (3)  (6) 0111 є L (α) S | 0A | 01C | (1)  (4)  (7) 010 є L (α) S | 0A |  01C | (1)  (4)  001

011D | 0111 (10)

5

EJEMPLO 2:
∑ = { 0, 1 } α Ξ (01)* | (10)*...