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


Otras Definiciones

Partición sobre un lenguaje

Partición sobre un conjunto de estados

Subaceptor de un autómata finito

Isomorfismo.Lema

Autómata finito determinístico k-ulterior

Autómata invertido

Autómata k-reversible

Lenguaje k-reversible

Aceptor destacadamente terminal

Aceptor ku-reversible

Aceptor k-contextual


Particion sobre un Lenguaje
Partición sobre un Lenguaje

ΠL sobre el conjunto de prefijos del lenguaje L, se define como:

 ∀ u,v  ∈ L   B(u, Π) = B(v, Π) ⇔  TL(u) = TL(v)


Particion sobre un Conjunto de Estados
Partición sobre un Conjunto de Estados

ΠPr(s+)  es la restricción de ΠL al conjunto de prefijos de una muestra positiva S+. Se define como:

∀ u,v  ∈  Pr(S+)   B(u, ΠPr(s+) ) = B(v, ΠPr(s+) )  ⇔ TL(u) = TL(v)


Subaceptor de Automata Finito
Subaceptor de Autómata Finito

A' es un subaceptor de A ⇔ L(A') ⊂ L(A),

es decir, el lenguaje reconocido por el también autómata finito A' → L(A'), está contenido o reconocido por un lenguaje de  A.


Isomorfismo. Lema

Todos los algoritmos de inducción que parten del árbol aceptor de prefijos se basan indirectamente en esta proposición.

Sea

L un lenguaje,

S+ una muestra positiva de L,

A0 un aceptor de prefijos de S+  = PT(S+), y

ΠPr(s+)  una restricción de ΠL a Pr(S+) entonces

A0 /ΠPr(s+) es isomorfo a un subaceptor de L, es decir, el lenguaje aceptado por ese autómata está contenido en L, es decir:

L ( A0 /ΠPr(s+)  ) ⊂  L


AFD k-ulterior
Autómata Finito Determinístico k-ulterior

Un autómata finito M se dice que es determinístico K-ulterior, si para dos estados q1, q2 que sean bien iniciales bien que exista un q3 y una x ∈ Σ  con δ(q3,x) = q1 y δ(q3,x) = q2, entonces no existe una cadena u ∈ Σ* de longitud k saliente de ellos. Es decir, que no se den ninguna de las situaciones que se muestran en el siguiente gráfico:


Automata Invertido
Autómata Invertido

Ar = ( Q, Σ, δr, I', F' ), siendo A = ( Q, Σ, δ, I, F ) un autómata finito deteminístico, donde:

δr : Q ——→  P( Q )  ,	será no determinístico,

δr(q,x) = {q' ∈ Q / δ(q',x) = q}

I'   Conjunto de estados iniciales = F

(siempre existe un autómata equivalente con un solo estado inicial)

F'  Conjunto de estados finales = { I }

Por ejemplo:


Automata K reversible
Autómata K-reversible

Si A es determinístico y Ar es determinístico en exploración k-ulterior.


Lenguaje k reversible
Lenguaje K-Reversible

Si existe un autómata k-reversible que lo reconozca.


Aceptor Tao-Terminal
Si existe un símbolo τ ∈ Σ   tal que:

δ(q,x) ∈ F , si y sólo si,   x = τ

Es decir que todos los arcos incidentes en estados terminales están etiquetados con τ.


Aceptor de Estado Objetivo
Si el autómata posee un único estado final y además de él no parte ninguna transición ni bucle.


Aceptor Destacadamente Terminal

Si es τ-terminal y aceptor de estado objetivo. Es decir, que sólo tiene un estado final (sin bucles) y todas las flechas hacia él están etiquetadas con el mismo símbolo τ.

Existe una biyección hτ que asocia a un aceptor A un aceptor destacadamente terminal hτ(A), tal que si L es el lenguaje reconocido por A entonces L (hτ(A)) = L . { τ }. Se supone que τ no pertenece a L.


Aceptor KU-reversible

Si el aceptor es destacadamente terminal y 1/hτ(A) es k-reversible.


Lenguaje K-contextual
Siendo L un lenguaje regular, L será K-contextual si para cualquiera cadenas u1 v w1 , u2 v w2  L, con | v | = k, se verifica que:

TL(u1 ,v) = TL(u2 ,v).


Aceptor K-contextual

Si el lenguaje aceptado por el aceptor ( L(A) ) es un lenguaje K-contextual.