Copyright: Ayuda creada por: Beatriz Corzo Menéndez              1999


Definiciones

Definiciones Generales

Definiciones sobre Autómatas


Definiciones Generales

Conjunto de prefijos de un lenguaje L

Conjunto de sufijos de un lenguaje L

Conjunto de sufijos de longitud k

Muestra positiva

Muestra característica

Partición

Bloque

Refinamiento


Prefijos
Pr(L) = { u : ∃ v  ∈ Σ *  ∧  uv  ∈  L }

Σ * ⇒ Conjunto de cadenas de cualquier longitud que pueden formarse por concatenación de elementos del alfabeto , incluida la cadena vacía que se representa por λ .


Sufijos
TL(u) = { v : uv ∈ L }


Sufijos de longitud K
TkL(u) = { v : uv ∈ L  ∧  | v | ≤ k}


Muestra positiva
S+ = Conjunto finito tal que  S+  ⊂  L


Muestra Caracteristica
S+ muestra característica de un cierto lenguaje L, si éste es el menor lenguaje que contiene a S+.


Particion
Πs. Dado un conjunto S, una partición de S, es una colección de conjuntos

 Πs = { Si } i ∈ I , tal que, se cumple:

i )  ∪ Si = S ,  i ∈ I	y        ii )  Sr ∩ Ss = ∅,   ∀ r,s ∈ I, r ≠ s


Bloque
B(s, Πs) = Si   tal que s ∈ Si

Las aplicaciones se harán para s = estado.

Gráficamente:


Refinamiento
Πs = { Si } i ∈ I  es un refinamiento de Πs´ = { Sj´}  j ∈ J , si y sóo si,

∀ S´ ∈ Πs´ ,  S´ =  ∪Sh  con  h ∈ H  y  h ⊂ I

Es decir, cada bloque de Πs´ coincide con una partición de bloques de Πs.

Gráficamente:


Definiciones sobre Automatas
Definiciones sobre Autómatas

Expresión general

Función de transición generalizada

Autómata o Aceptor de prefijos

Autómata Cociente

Autómata Mínimo

Reconocimiento de una cadena


Expresion General
Expresión General de un Autómata Finito

Un autómata, que denotaremos por A, viene determinado por una quintupla del siguiente tipo:

 	A = ( Q, Σ, δ, I, F ), donde,

Q  representa al Conjunto de Estados (finito)

Σ  representa al Alfabeto.

δ  representa la Función de Transición

Si el autómata finito es determinístico (AFD):

 	δ  : Q × Σ ———→  Q

    	     (q , x)      →      δ (q, x)

Si el autómata finito es no determinístico (AFND):

δ : Q × Σ  ———→ P(Q)

                  	    (q , x)      →       δ (q , x) = {...,qi,...} ∈ P(Q)

I    representa al Estado Inicial

F   representa el conjunto de Estados finales o aceptores

A los autómatas finitos se les suele denominar también aceptores o reconocedores.

Representaremos como L(A) al lenguaje aceptado o reconocido por el autómata A.


Funcion de Transicion
Función de Transición Generalizada

•	Si el autómata finito es determinístico (AFD):   δ*  : Q × Σ* ———→  Q

 i) δ* (q , λ) = q

ii) δ* (q , wx) = δ (δ* (q, w),x)

La función de transición δ, es determinística, es decir no presenta ambigüedades en las transiciones de estados para una cierta entrada.

•	Si el autómata finito es no determinístico (AFND):  δ* : Q × Σ* ——→ P(Q)

i) δ* (q , λ) = q

           ii) δ* (q , wx) = ∪ δ (q', x) q'  ∈  δ* (q,w)

Es decir, dada una entrada en un cierto estado q, se puede pasar a distintos estados.

Para todo AFND se puede construir un AFD, de tal forma que el lenguaje reconocido por ambos autómatas coincida.


Automata Aceptor de Prefijos
Árbol (Autómata) Aceptor de Prefijos de una Muestra Positiva

Ejemplo

PT(S+) =(Q, Σ, δ, I, F)

Donde:

 Q    Conjunto de Estados = Pr(S+)

 Σ    Alfabeto.

 δ     Aplicación de la forma   δ : Q × Σ ——→ Q 	       	u , x    → δ (u , x) =  ux    si ux ∈  Pr(S+)

   =  ⊥     en otro caso

I     Estado inicial = λ  (la cadena vacía siempre es un prefijo)

F    Conjunto de estados finales = S+


Automata Cociente
Autómata Cociente

A/Π = ( Q/Π, Σ, δ', I', F' )

Siendo Π una partición de Q, donde:

qi, qj  ∈  Q verificarán  qi  R qj  ⇔   B(qi, Π) = B(qj, Π)

( interpretación como una relación de equivalencia )

El autómata cociente puede resultar no determinístico.

Siendo:

Q/Π    Conjunto de estados

Σ        Alfabeto

δ'        Aplicación de la forma:    δ' : Q/Π × Σ   ——→  Q/Π

Si B1 ∈  Q/Π, es decir, un bloque de la partición Π en Q,

entonces

δ'(B1, x) = B2  ⇔   ∃ q ∈ B1, tal que, δ(q, x) = q' ∈ B2

I'    Estado inicial = Clase correspondiente al bloque B1

I' = [I] = B( I, Π)   bloque en el que está I con la relación Π.

Es decir, bloque en el que está el antiguo estado inicial.

F'   Estado final = { B ∈ Q/Π:  B ∩ F ≠ ∅ }, siendo B  bloques, clases o estados en el 	nuevo autómata.

Es decir, los estados finales ahora serán aquellos bloques que contengan 	alguno/s de el/los antiguo/s estado/s final/es, pudiendo contener otros estados que antes 	no eran finales.


Automata Minimo
Autómata Mínimo

Es un caso particular de autómata cociente.

Sea M = ( Q,Σ, δ, I, F ) un autómata finito deteminístico, el autómata mínimo que 	reconozca el mismo lenguaje que M será el autómata cociente:

M' = M/Π = ( Q/Π, Σ, δ', I/Π, F/Π )

donde Π está definida como sigue:

∀ qi, qj ∈ Q : B(qi, Π ) = B(qj, Π )   ⇔   (δ*(qi, w) ∈ F  ⇔   δ*(qj, w) ∈ F) , ∀ w ∈ Σ*


Reconocimiento de una Cadena

Cuando un autómata procesa una cadena y llega a un estado final a través de sucesivas transiciones, se dice que ha reconocido la cadena de entrada, es decir, que dicha cadena  pertenece al lenguaje reconocido por el autómata.


Ejemplo Aceptor de Prefijos
Ejemplo de Construcción de un Aceptor de Prefijos

Siendo  S+ = { ab, aab, abbb}

Se trata de obtener:  PT(S+) = ( Q, Σ, δ, I, F )

    Σ = {a,b}

    Q´= Pr(S+) = {  ab: λab, ab, abλ

 	     aab: λaab, aab, aab, aabλ

     abbb: λabbb, abbb, abbb, abbb, abbbλ  }

 	Nota: Los caracteres en negrita señalan los prefijos posibles para cada cadena.

    Q = Pr(S+) = { λ, a, ab, aa, aab, abb, abbb }   ⇒  7 estados

    δ : Q × Σ ——→  Q

         (u , x)   →      δ (u, x) = ux   si  ux  ∈ Pr(S+)

     δ (λ , a) = a    pues  a  ∈ Pr(S+)

     δ (λ , b) = ⊥   pues  b  ∉ Pr(S+)

.

.

.

Es decir, si 'a' ∈ Pr(S+) entonces está definido un arco en el autómata de la forma:

    I = λ

    F = S+ = {ab, aab, abbb}

El autómata quedaría: