Mexico

Lenguajes Formales
Elvira Mayordomo
Noviembre 2003
DEPARTAMENTO DE INFORMATICA E INGENIERIA DE SISTEMAS

Tema 1: Expresiones regulares hDefinición hEjemplos hNotaciones

1-1

Bibliografía de los temas 1, 2 y 3

Ullman, J.D., Hopcroft, J.E., and Motwani, R. (2001). Introduction to Automata Theory, Languages, and Computation. AddisonWesley. Lewis, H. and Papadimitriou, C. (1981).Elements of the Theory of Computation. Prentice-Hall. Apuntes de Joaquín Ezpeleta para la asignatura de Compiladores I, CPS, Universidad de Zaragoza. Apuntes de Elvira Mayordomo para el curso de doctorado Introducción al Procesamiento de Lenguaje Natural, DIIS, Universidad de Zaragoza. Jurafsky, D. and Martin, J.H. (2000). Speech and Language Processing. Prentice Hall.
1-2

Expresiones regulares.Definiciones
alfabeto

conjunto finito de símbolos
ejemplos

{0,1}, letras y dígitos

cadena (palabra o string)

secuencia finita de elementos del alfabeto
ejemplos

0010 estadoInicial v_0
1-3

Expresiones regulares. Definiciones
longitud de una cadena

número de símbolos que la componen
ejemplos

|hola| |123456|

ε

= 4 = 6 = 0 (cadena vacía)

lenguaje

dado unalfabeto, cualquier conjunto de cadenas formadas con dicho alfabeto
ejemplo

Siendo Σ={0,1} {0,111,011,0111,01111,1}
1-4

Expresiones regulares. Definiciones Algo sobre cadenas:
hconcatenación – c1=hola, c2=Colega c1c2=holaColega –

ε es el neutro, tando a derecha como a izquierda: εc = cε = c

– c0=e, c1=c, c2=cc, c3=ccc,.... hterminología – prefijo, sufijo – subcadena

1-5Expresiones regulares. Definiciones Operadores sobre lenguajes:
hSean L,M dos lenguajes
unión de lenguajes

L∪ M = {c|c ∈ L ó c ∈ M}
concatenación de lenguajes

L M = {st|s ∈ L y t ∈ M}

1-6

Expresiones regulares. Definiciones Más operadores sobre lenguajes:
potencia de un lenguaje

L0 = {ε} Li = L Li-1

L1 = L para i>1
cerradura positiva

cerradura de Kleene

L* =

∪
∞
i=0

LiL* =

∪
∞
i=1

Li

CERO o MÁS concatenaciones

UNA o MÁS concatenaciones

1-7

Expresiones regulares. Definiciones Una expresión regular es una fórmula que caracteriza un lenguaje (conjunto de cadenas) Se usan en compilación, procesamiento de lenguaje natural, búsquedas de cadenas en UNIX y muchos editores de texto (vi, Perl, Emacs, grep, Word, netscape, nedit) Veremos lasintaxis de Perl (todas son muy similares)

1-8

Expresiones regulares. Definiciones Sea
1)

Σ un alfabeto
expresión regular es la expresión regular cuyo lenguaje es L(ε)={ε}

ε

2) Si a∈Σ, a es la expresión regular cuyo lenguaje es L(a)={a} 3)Sean r,s exp. reg. con lenguajes L(r) y L(s) (r)|(s) es la exp. reg. cuyo lenguaje es L(r) ∪ L(s) (r)(s) es la exp. reg. cuyo lenguaje es L(r)L(s)(r)* es la exp. reg. cuyo lenguaje es (L(r))* Se pueden quitar los paréntesis cuando estos no sean necesarios

1-9

Expresiones regulares. Ejemplos

Ejemplo 1: Sea
r ab a|b a* ab* (ab|c)*d

Σ={a,b}
L(r) {ab} {a,b} {ε,a,aa,aaa,aaaa,...} {a,ab,ab,abbb,...} {d,abd,cd,abcd,ababcd,...}

1-10

Expresiones regulares. Ejemplos Ejemplo 2: Sea
00 (00)

Σ={0,1}
la cadena ‘00’

(1|10)*(0|1)*

ε y todas las cadenas que empiezan con
‘1’ y no tienen dos ‘0’ consecutivos todas las cadenas con 0 ó más ‘1’ ó ‘0’ y

ε

(0|1)*00(0|1)* (0|ε)(1|10)* (0|1)*011

todas las cadenas con al menos 2 ‘0’ consecutivos todas las cadenas que no tengan dos ‘0’ consecutivos todas las cadenas que acaban en ‘011’
1-11

Expresiones regulares. Notaciones Convenios de notación útiles:
hSi rrepresenta L(r)

(r)+ representa L(r)+
Se cumple que: r* = ε|r+ r+ = rr*

una ó más veces r

(r)? representa {ε}∪ L(r)
Se cumple que r? = r|ε

0 ó 1 vez

1-12

Expresiones regulares. Notaciones
hFormas abreviadas [....] expresa elección en un conjunto de elementos del alfabeto

[aeiou] [0-9]
- expresa subrango

≅ ≅

a|e|i|o|u

0|1|2|3|4|5|6|7|8|9

[+-]?[0-9]+
Ejemplos:...