| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III Introducción 3.1 Token y Lexemas 3.2 Algoritmo de los dos Buffers 3.3 Expresiones regulares

3.4 Definición y ejemplos de AFN

3.5 Definición y ejemplos de AFD

3.6 Construcción de un AFN a partir de una expresión regular

3.7 Conversión de un AFN a AFD (Construcción de subconjuntos)

3.8 Lenguaje LEX

3.9 Escritura de Programas LEX

UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

3.3 Expresiones Regulares

> También las gramáticas regulares se pueden expresar por medio de las expresiones regulares.

> La expresión regular que representa a los números reales, es la siguiente:

> (+|-| ) d* . d d* (10 (+| -| ) d d*| )

> El diagrama de los números reales se presenta en la siguiente figura:

> La formación de los identificadores id, se hace como sigue:

> L = letra, d = dígito

> Transformación de expresiones regulares a producciones

> Si tenemos la siguiente expresión regular:

> A → xy

> Se puede transformar de la siguiente manera:

> A → xB B → y

> Si tenemos la siguiente expresión regular:

> A → x|y

> Se puede transformar de la siguiente manera:

> A → x A → y

> Si tenemos la siguiente expresión regular:
> A → x*

> Se puede transformar de la siguiente manera:

> A → λ
> A → xB
> B → xB
> B → λ

> x* = {λ, x, xx, xxx, …} ßPropiedad

> Si tenemos la siguiente expresión regular:
> A → x+

> Se transforma de la siguiente manera:

> A → xB B → xB B → λ

> Si tenemos la siguiente expresión regular:

> A → x*y

> Se transforma de la siguiente manera:
> A → x*B A → By*
> B → y B → x
> C → x* C → y*
> C → λ C → λ
> C → xD C → yD
> D → xD D → xD
> D → λ D → λ

> Las producciones para A → x*y quedan de la siguiente forma:
> A → Cy
> C → xD
> D → xD
> C → λ
> D → λ

> Las producciones para A → xy* quedan de la siguiente forma:
> A → xC *Forma corta.
> C → yD A → By A → Bx
> D → yD B → xB B → yB
> D → λ B → λ B → λ
> C → λ

> Comprobación

> A xC x
> A xC xyD xy

> Si se tiene la siguiente expresión regular:
> A → l(d|l)*

> Se transforma de la siguiente manera:

> A → lB
> B → (d|l)*
> A → lB

> B → dB
> B → lB

> B → λ

> Comprobación
> A lB l
> A lB ldB ld
> A lB ldB ldlB ldl

> Tarea si se tiene la siguiente expresión regular
> A → (12|2)* (12|1|2)
> A → 1* (0|01)*
> A → x*y*

> Encontrar la expresión regular.

> Todas las cadenas de letras que contienen las 5 vocales en orden, cada vocal solo se repite una vez en toda la cadena.

> Lenguaje = {aeiou, abeiou, abceiou, abediyou ……}

> Expresión regular

> A consonante * e consonante * i consonante * o consonante * u consonante *

> A → (12|1|2)*(12|1|2)
> A → BC
> B → 12B
> B → 2B
> B → λ
> C → 12
> C → 1
> C → 2

Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello