PDF de programación - Teoría de autómatas para investigadores en XML

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Teoría de autómatas para investigadores en

XML

Rafael C. Carrasco Jiménez

Departamento de Lenguajes y Sistemas Informáticos

Universidad de Alicante

Febrero 2006

4 de febrero de 2008

Autómatas finitos de cadenas

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Un DFA (deterministic finite-state automaton) es una
representación (grafo) de un procedimiento computable que
requiere memoria finita.

Autómatas finitos de cadenas

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Un DFA (deterministic finite-state automaton) es una
representación (grafo) de un procedimiento computable que
requiere memoria finita.
Ejemplo: determinar la paridad de una cadena binaria.
Contraejemplo: determinar si la entrada es palíndroma.

Expresiones regulares

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Las expresiones regulares definen lenguajes usando símbolos,
paréntesis y operadores de concatenación, elección y repetición.
Comentarios de C:

[*]
[/]
[^*/]

A
B
C
Comment {B}{A}{B}*({A}*{C}{B}*)*{A}*{A}{B}

Expresiones regulares

La validación de cadenas con respecto a expresiones regulares
puede hacerse mediante DFA.

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Autómata de Glushkov de una expresión regular

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Para cada expresión regular r , se construye el marcado Er
sustituyendo los símbolos por posiciones.
Por ejemplo
r = BAB∗(A∗CB∗)A∗AB ⇒ Er = 123∗(4∗56∗)∗7∗89.
Cada posición será un estado del autómata de Glushkov.
Para construir las transiciones se usan 4 funciones: empty, first,
last, follow.

Autómata de Glushkov de una expresión regular

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

empty(E ) es cierto si la subexpresión contiene la cadena vacía:

empty(n) = FALSE

empty(F|G ) = empty(F ) ∨ empty(G )
empty(F , G ) = empty(F ) ∧ empty(G )
empty(F∗) = TRUE
empty(F +) = empty(F )
empty(F ?) = TRUE

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Autómata de Glushkov de una expresión regular

first(E ) es el conjunto de símbolos por los que puede empezar
una cadena de E :



first(n) = {n}

first(F|G ) = first(F ) ∪ first(G )
first(F ) ∪ first(G )
first(F , G ) =
first(F )
first(F∗) = first(F )
first(F +) = first(F )
first(F ?) = first(F )

if empty(F )
otherwise

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Autómata de Glushkov de una expresión regular

last(E ) es el conjunto de símbolos por los que puede terminar
una cadena de E :

last(n) = {n}



last(F|G ) = last(F ) ∪ last(G )
last(F ) ∪ last(G )
last(G )

last(F , G ) =
last(F∗) = last(F )
last(F +) = last(F )
last(F ?) = last(F )

if empty(G )
otherwise

Autómata de Glushkov de una expresión regular

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

follow(E ) es el conjunto de pares de símbolos que pueden
aparecer consecutivos en E :

follow(n) = ∅

follow(F|G ) = follow(F ) ∪ follow(G )
follow(F , G ) = follow(F ) ∪ follow(G ) ∪ last(F ) × first(G )
follow(F∗) = follow(F ) ∪ last(F ) × first(F )
follow(F +) = follow(F ) ∪ last(F ) × first(F )
follow(F ?) = follow(F )

Autómata de Glushkov de una expresión regular

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

El autómata de Glushkov es (N, Σ, δ, 0, F ), con:

Q = {0, 1, ..., N}
δ(0, a) = {n ∈ first(Er ) : Φr (n) = a}
δ(n, a) = {m ∈ Q : (n, m) ∈ follow(Er ) ∧ Φr (m) = a}

{0} ∪ last(Er )

F =

last(Er )

if empty(Er )
otherwise

siendo N el número de símbolos de r y Φ el homomorfismo que
genera r a partir de Er .

Autómata de Glushkov de una expresión regular

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Construye el autómata de Glushkov para BAB∗(A∗CB∗)A∗AB

Autómata de Glushkov de una expresión regular

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Si el autómata de Glushkov es determinista, r es 1-inambigua
y, por tanto, válida en el estándar SGML.

Aunque todo autómata finito tienen un equivalente
determinista, no todas las lenguajes regulares admi-
ten una expresión regular con autómata de Glushkov
determinista.

Medidas probabilísticas

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

En un autómata probabilístico, cada transición (y cada estado
de aceptación) tiene una probabilidad asociada.
Algunas distancias

Cuadrática:
Kullback-Leibler:

x (pAx) − pB (x))2.

x pA(x) ∗ log pA(x)
pB (x) .

La distancia cuadrática es más suave, pero menos sensible a los
valores pequeños.

Medidas probabilísticas

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

La probabilidad de coemisión C (A, B) =

permite calcular la distancia cuadrática:

x pA(x)pB (x)

d2(A, B) = C (A, A) + C (B, B) − 2C (A, B)

Medidas probabilísticas

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

C (A, A) =

cij p(i, a)p(j, a)



i∈Q

a



j∈Q



Los coeficientes cij son el número esperado de “pasos” por i y j.

cij = (i == 0)(j == 0) +

ckl p(k, a)p(l, a)

a

k:δ(k,a)=i

l:δ(l,a)=j

Demostración en: Carrasco 1997.

Árboles

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Dado un alfabeto Σ = {σ1, . . . , σ|Σ|}:

Todos los símbolos de Σ son árboles de TΣ.
Dado σ ∈ Σ y m > 0 árboles t1, . . . , tm, σ(t1 ··· tm) es un
árbol de TΣ.

Lenguajes de árboles

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

A cualquier subconjunto de árboles se le llama lenguaje. En
particular, el lenguaje sub(t) de subárboles de t es

if t = σ ∈ Σ
if t = σ(t1 . . . tm) ∈ TΣ − Σ

k=1 sub(tk )

{σ}
{t} ∪m

sub(t) =

XHTML es un lenguaje de árboles sobre el alfabeto:
{html, head, body, p, a, ul, ol, li, th, tr, td...}

Autómatas de árboles

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Un autómata finito de árboles es A = (Q, Σ, ∆, F ),

Q = {q1, . . . , q|Q|} es un conjuntoestados;
Σ = {σ1, . . . , σ|Σ|} es el alfabeto;
F ⊆ Q es un subconjunto de estados de aceptación,
∆ ⊂ ∪∞

m=0Σ × Q m+1 es un conjunto finito de transiciones.

Autómatas de árboles

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Los autómatas de árboles pueden ser

indeterministas :-|
deterministas ascendentes :-)
deterministas descendente :-(

Debemos valorar capacidad expresiva y complejidad de análisis.

Autómatas de árboles

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Evaluador de expresiones lógicas:

∆ = {(F , 0), (T , 1), (∧, 1+, 1), (∧, (0|1)∗0(0|1)∗, 0)

(∨, 0+, 0), (∨, (0|1)∗1(0|1)∗, 1)}

∨

∧

F

∨

T

F

T

∨

T

1

1

0

F

1

F

F

1

0

0

1

1

0

0

0

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Autómatas de árboles

Evaluador de XPath /a[a]/b//a (indeterminista).

∆ ={ (a,Q∗,/a), (b,Q∗,/b), (a, Q∗,//a),

(b,Q∗//aQ∗,/b//a),

(a,Q∗/aQ∗/b//aQ∗,/a[a]/b//a),... }

a

a

b

a

b
/a[a]/b//a

/a

/b//a

//a

/b

Autómatas ascendentes árboles

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Las siguientes afirmaciones sobre un lenguaje de árboles L son
equivalentes:

L es reconocible por un autómata de árboles ascendente
indeterminista.

L es reconocible por un autómata de árboles ascendente
determinista.

L es reconocible por un autómata de árboles descendente
indeterminista.

En cambio, los autómatas deterministas descendentes (como
quiera que se definan) son menos potentes.

Autómatas ascendentes de árboles

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

Cada transición (σ, i1, ..., im, q) de ∆ tiene argumento
(σ, i1, ..., im) y salida q. El autómata es determinista si no hay
más de una salida por cada argumento:



if q ∈ Q such that (σ, i1, ..., im, q) ∈ ∆

q
⊥ if no such q exists

δm(σ, i1, ..., im) =

⊥ es el estado de absorción

Autómatas ascendentes de árboles

Teoría de
autómatas

para

investigadores

en XML

RCC

Autómatas de
Glushkov

Autómatas
probabilísticos

Autómatas de
árboles

El resultado de A en t es A(t):



A(t) =

δ0(σ)
δm(σ, A(t1), . . . , A(tm))

if t = σ