Lenguages Formales

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 un alfabeto, 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 = {ε}

L1 = L

Li = L Li-1

para i>1

cerradura de Kleene

L* =∪
∞

i=0

Li

CERO o MÁS concatenaciones

cerradura positiva

L* =

∪
∞

i=1

Li

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 la sintaxis de Perl (todas son muy similares)

1-8

Expresiones regulares. Definiciones
Sea

Σ un alfabeto
expresión regular

1)

ε

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

Σ={a,b}

r

L(r)

ab

{ab}

a|b

{a,b}

a*

{ε,a,aa,aaa,aaaa,...}

ab*

{a,ab,ab,abbb,...}

(ab|c)*d

{d,abd,cd,abcd,ababcd,...}

1-10Expresiones regulares. Ejemplos
Ejemplo 2: Sea
00

Σ={0,1}

(00)

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

la cadena ‘00’

ε 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 lascadenas que acaban en ‘011’
1-11

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

(r)+ representa L(r)+

una ó más veces r

Se cumple que:
r* = ε|r+
r+ = rr*

(r)? representa {ε}∪ L(r)

0 ó 1 vez

Se cumple que
r? = r|ε
1-12

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