5/26/2018 Ejemplo Estrella de Kleene

1/13

Ejemplo Adicional del Teorema deKleene

5/26/2018 Ejemplo Estrella de Kleene

2/13

TEOREMA DE KLEENE

Estrella de Kleene:

E.R.

NFA-

NFA

DFA

5/26/2018 Ejemplo Estrella de Kleene

3/13

TEOREMA DE KLEENE

Ejemplo: Tenemos la E.R. -> (0+1)*1

0+ 1 0*

01

5/26/2018 Ejemplo Estrella de Kleene

4/13

TEOREMA DE KLEENE

Completemos el autmata:

1 2

3

4

5

6

7 8 9 10

0

1

1

5/26/2018 Ejemplo Estrella de Kleene

5/13

TEOREMA DE KLEENE (NFA- a NFA)

1. Se interpretan los estados y sus direcciones teniendo en cuenta haciadonde nos lleva en base a epsilon y agregando que cada estado selleva a si mismo.

1 2

3

4

5

6

7 8 910

0

1

1

2. Mover cada estado que resulto de la cerradura psilon con losvalores del alfabeto.

C(1) = {1,2,3,4,8,9}

Mov{C(1) ,0}={5}

Mov{C(1),1 }={6,10}

5/26/2018 Ejemplo Estrella de Kleene

6/13

C(2) = {2,3,4}

Mov{C(2) ,0}={5}

Mov{C(2), 1 }={6}

C(3) = {3}

Mov{C(3) ,0}={5}

Mov{C(3), 1 }={ }

C(4) = {4}

Mov{C(4) ,0}={ }

Mov{C(4), 1 }={6}

C(5) = {5,7,2,3,4,8,9}

Mov{C(5) ,0}={5 }

Mov{C(5), 1}={6,10}

C(6) = {6,7,8,9,2,3,4}

Mov{C(6) ,0}={5}

Mov{C(6), 1}={6,10}

C(7) = {2,3,4,8,9}

Mov{C(7) ,0}={5}

Mov{C(7), 1}={6,10}

5/26/2018 Ejemplo Estrella de Kleene

7/13

C(8) = {8,9}

Mov{C(8) ,0}={ }

Mov{C(8), 1 }={10}

C(9) = {9}

Mov{C(9) ,0}={ }

Mov{C(9), 1 }={10}

C(10) = {10}

Mov{C(10) ,0}={ }

Mov{C(10), 1 }={ }

5/26/2018 Ejemplo Estrella de Kleene

8/13

TEOREMA DE KLEENE (NFA- a NFA)

3. Se genera la siguiente tabla para despus minimizarla mediante laidentificacin de los estados a los que no hay forma de llegar a ellos

mediante otros estados.

Alfabeto

Posicin 0 1 C1

2

3

4

56

7

8

9

10

5

5

5

-

55

5

-

-

-

6,10

6

-

6

6,106,10

6,10

10

10

-

1,2,3,4,8,9

2,3,4

3

4

5,7,2,3,4,8,96,7,8,9,2,3,4

2,3,4,8,9

8,9

9

10

5/26/2018 Ejemplo Estrella de Kleene

9/13

TEOREMA DE KLEENE (NFA- a NFA)

4. Si se quiere dibujar el autmata solo se debe tomar en cuenta quelos estados finales sern aquellos que en su cerradura epsiloncontengan al antiguo estado final.

5 6 10

0

1

0

1

1

1

5/26/2018 Ejemplo Estrella de Kleene

10/13

TEOREMA DE KLEENE (NFA a DFA)

Alfabeto

Posicin 0 1 C1

23

4

5

6

78

9

10

5

55

-

5

5

5-

-

-

6,10

6-

6

6,10

6,10

6,1010

10

-

1,2,3,4,8,9

2,3,43

4

5,7,2,3,4,8,9

6,7,8,9,2,3,4

2,3,4,8,98,9

9

10

5/26/2018 Ejemplo Estrella de Kleene

11/13

TEOREMA DE KLEENE (NFA a DFA)

Construccin de Subconjuntos (Se toman los valores de la tabla), en elcaso que este vaco se toman en cuenta los movimientos del Edo. Que loseal, en este caso para el edo. 10 fue sealado por el edo. 7

5 { 5,7,2,3,4,8,9}

6 {5,7,8,9,2,3,4}

10 {2,3,4,8,9} Alfabeto

Estados1 0

5 6,10 56 6,10 5

10 - -

5/26/2018 Ejemplo Estrella de Kleene

12/13

TEOREMA DE KLEENE (NFA a DFA)

Construccin de Subconjuntos

A = { 5,6}

B = {10}

C = {5}D = {6,10}

1

5,6 6,10

10

1

15

00

0

1

0

5/26/2018 Ejemplo Estrella de Kleene

13/13

TEOREMA DE KLEENE (DFA a E.R.)

5,6 6,10

10

1

15

00

0

10

1 Verificar cada camino delDFA

(0+1)* 1