Teorema de kleene

INSTITUTO TECNOLOGICO DE VERACRUZ

“TEOREMA DE KLEENE”

MATERIA:
TEORIA DE LA COMPUTACION

CATEDRATICO:
M.E. GUTIERREZ GIRALDI OFELIA

ESPECIALIDAD:
ING. SISTEMAS COMPUTACIONALES

H. VERACRUZ, VER., A 08 DE NOVIEMBRE DE 2010.

Teorema de Kleene: “Un lenguaje es regular si y solo si es aceptado por algún autómata finito”

Este teorema establece que para cualquier expresión regular(E.R.) existe un autómata finito equivalente, y viceversa.

El teorema consta de 4 algoritmos:
* E.R NFA-ξ
* NFA-ξ NFA
* NFA DFA
* DFA E.R.

CONVERSION DE E.R A NFA-ξ

Para probar que un lenguaje regular debe ser aceptado por un autómata finito se debe realizar una transformación gradual que vayaconvirtiendo a la expresión regular en un autómata finito.
Para que dicha transformación se vaya dando se requiere utilizar una representación de los lenguajes regulares que sea intermedia entre las E.R. y los NFA-ξ., se pueden utilizar las graficas de transición, las cuales son en esencia un NFA-ξ. Las palabras que se encuentran en las etiquetas de un NFA-ξ son interpretadas como expresiones regularesque se encuentran representadas a sí mismas.
Las graficas de transición son quíntuplas (K, Ʃ, Δ, s, F) donde: Δ Є K x ER x K.
Teniendo la grafica de transición

11
q1
q0

(0+1)*

(0+1)*

IMG 1.1
Se expresa formalmente como:
K= {q0, q1}
Ʃ= {1, 0}
Δ= (qo,0) q0, (q0,1) q0,(q0,11) q1, (q1,0) q1, (q1,1)q1
s= q0
F= q1

Procedimiento.
Sea E.R= (0+1)*11(0+1)* una expresión regular, si G1= (qo,0) q0, (q0,1) q0, (q0,11) q1, (q1,0) q1, (q1,1)q1, entonces L(G)=L(E.R)
La grafica de transición relacionada con la E.R. (0+1)*11(0+1)* se ilustra en la imagen 1.1. Se procede a realizar la transformación de G1 a G2, después G2 a G3, y así sucesivamente hasta que se llegue a Gn,siendo que en las transiciones no haya más que caracteres solos.
Al realizar la transformación de una E.R a un NFA-ξ hay que tomar en cuenta a los operadores de dicha E.R., tal que.

Reemplazar Por
R1
R1R2

R2
r
q
p

q

p

R1

q
p
R1+R2
q
p

R2

ξ
ξ
R*
q
p

r
q
p

R

R
qp


Ʃ= R

ξ

q
p

Ʃ= ξ


q
p
p
q

Ʃ= 0

Para poder realizar la eliminación de los operadores, se reemplazan ciertas transiciones por otras, y así sucesivamente hasta que ya no sea posible realizar alguno de los reemplazamientos.
Solución
Tomando la E.R. anterior, obtener el NFA-ξ que acepta el lenguaje de dicha E.R., entonces aplicamos la sucesión detransformaciones.

11
q
p

(0+1)*
(0+1)*

1
1

r
q
p

(0+1)*
(0+1)*

ξ
ξ
1
1

s
t
r
q
p

(0+1)*
(0+1)*

ξ
ξ

1
1
t
s
r
q
p

0,1
0,1

La equivalencia entre G1, G2, G3… Gn se asegura porque cada una de las transformaciones realizada mantiene la equivalencia existente.

CONVERSION DE NFA-ξ A NFA

Para realizar la conversión de un NFA-ξ a un NFA, es necesariorealizar lo que se conoce como clausura-ξ, la cual corresponde a una clausura transitiva contextualizada en la teoría de autómatas.
Teniendo un estado q, se le llama clausura-ξ (q) al conjunto de estados a los cuales se puede acceder a partir de q, procesando un único símbolo de la entrada. Puede definirse como:[]
* Para todo estado q, q ∈ clausura-ξ (q).
* Dados dos estados p y r, si p ∈clausura-ξ (q) y r ∈ δ (p, ξ), entonces r ∈ clausura-ξ(q).
Procedimiento
Debe calcularse la clausura-ξ del estado inicial, para formar un conjunto “P” el cual corresponderá al estado inicial del nuevo autómata que se obtendrá al realizar la conversión.
Para cada elemento del alfabeto, se debe verificar los estados a los cuales se puede acceder a partir de los estados que se encuentran...