tesis

PEDECIBA Inform´tica
a
Instituto de Computaci´n - Facultad de Ingenier´
o
ıa
Universidad de la Rep´blica
u
Montevideo, Uruguay

Tesis de Maestr´ en Inform´tica
ıa
a

Reglas Contextuales y Modelos de Estado
Finito
Guillermo Moncecchi
Diciembre de 2004

Orientadora de Tesis: Dr. Ing. Dina Wonsever
Supervisora: Dr. Ing. Dina Wonsever

Resumen
Este trabajo presenta unasoluci´n para la aplicaci´n simult´nea de un subo
o
a
conjunto de reglas contextuales (un formalismo de reescritura para el an´lisis
a
y etiquetado de segmentos de texto), basada en t´cnicas de estado finito. Esta
e
soluci´n implica la definici´n de un nuevo tipo de aut´matas finitos, los transo
o
o
ductores sobre estructuras atributo-valor y el ´lgebra de expresiones regulares
a
asociada aellos. La aplicaci´n de las reglas sobre un texto de entrada se modela
o
como una cascada de reemplazos basados en segmentos del texto y el contexto
en que aparecen.
Palabras clave: t´cnicas de estado finito, transductores, expresiones regue
lares, reglas contextuales, aut´matas sobre estructuras atributo-valor.
o

i

Agradecimientos
Este trabajo llev´ tiempo. Tiempo de formaci´n, tiempode preparaci´n,
o
o
o
tiempo de elaboraci´n. Durante ese tiempo, fueron, para mi suerte, varios y
o
diversos quienes estuvieron ah´ ayudando, sugiriendo, apoyando.
ı,
La inspiraci´n para el trabajo fue un curso que dictaron hace algunos a˜os
o
n
Dina Wonsever y Gustavo Crispino sobre tratamiento autom´tico de textos,
a
donde descubr´ los transductores de estado finito. Mientras tanto,el curso
ı
de Teor´ de Lenguajes, me permiti´ acercarme a los aut´matas de todos los
ıa
o
o
tipos. Quiero agradecer a Juanjo Prada, a Diego Garat, a Marcos Campal, a
Tom´s Laurenzo, y a Ernesto Copello por tomarse tan en serio su trabajo y
a
permitirme con ello aprender un mucho.
El grupo de Lenguaje Natural del Instituto de Computaci´n me permio
ti´ tener un marco donde incluir mitrabajo, y donde darle aplicaci´n. En este
o
o
tiempo, la gu´ de Dina fue fundamental para evolucionar hacia el resultado
ıa
final. Las sugerencias de todo el equipo para mejorar lo hecho, tambi´n. La
e
amabilidad de Ken Beesley para aclararme tantas dudas sobre relaciones regulares, transductores o lo que fuera, me allanaron varias veces el camino. A
todos mi m´s sincero agradecimiento.
aEste trabajo est´ dedicado a Ver´nica, la primera, y a mi familia, por
a
o
razones obvias.

ii

´
Indice general
1. Introducci´n
o

1

2. Reglas Contextuales: el problema de su aplicaci´n
o
2.1. El formalismo de reglas contextuales . . . . . . . . . . . . . . .
2.2. Un int´rprete de reglas . . . . . . . . . . . . . . . . . . . . . . .
e
2.3. Un subconjunto de las reglascontextuales y el problema . . . .

4
4
5
7

3. Marco Te´rico
o
3.1. T´cnicas de Estado Finito . . . . . . . . . . . . .
e
3.1.1. Aut´matas Finitos y Lenguajes Regulares
o
3.1.2. Transductores y Relaciones Regulares . . .
3.1.3. Aut´matas aumentados con predicados . .
o
3.1.4. Estado del arte . . . . . . . . . . . . . . .
3.2. Estructuras Atributo-Valor . . . . . . . . . . . . .3.2.1. Definici´n . . . . . . . . . . . . . . . . . .
o
3.2.2. Subsumci´n y Unificaci´n . . . . . . . . .
o
o

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

4. Un modelo para la aplicaci´n de reglas contextuales
o
4.1. Aut´matas sobre estructuras atributo-valor . . . . . . .
o
4.1.1. Definici´n . . . . . . . . . . . . . . . . . . . . .
o
4.1.2. fs-aut´matascomo pfsr . . . . . . . . . . . . . .
o
4.1.3. fs-transductores y fs-pfst . . . . . . . . . . . . .
´
4.1.4. Algebra modificada de expresiones regulares . .
4.2. Una aproximaci´n inicial a la soluci´n . . . . . . . . .
o
o
4.3. Aplicaci´n simult´nea de reglas . . . . . . . . . . . . .
o
a
4.4. Determinizaci´n . . . . . . . . . . . . . . . . . . . . . .
o
4.5. Reglas sobre estructuras...