Teoria de la computación

[pic 1][pic 2]

[pic 3]

Propósito:

Realizar ejercicios de los autómatas finitos, autómatas finitos deterministas y autómatas de pila.

Instrucciones:

1. Σ = {a, b}. L=lenguaje de las cadenas que contienen exactamente dos a es igual b*ab*ab*. AFD M tal que L (M) = L:

2. Σ = {0, 1}. L = lenguaje de las cadenas sobre Σ que tienen un  número par de símbolos (cadenas de longitud par). AFD M tal que L (M) = L:

3. Σ = {0, 1}. L = lenguaje de las cadenas sobre Σ que contienen un número par de ceros. AFD M tal que L (M) = L:

4. Σ = {a, b}. L = lenguaje de las cadenas sobre Σ que terminan en b. AFD M tal que L (M) = L:

[pic 4]

1. Σ = {a, b}. L=lenguaje de las cadenas que contienen exactamente dos a es igual b*ab*ab*. AFD M tal que L (M) = L:[pic 5][pic 6][pic 7]

[pic 8]

[pic 9][pic 10][pic 11][pic 12][pic 13]

[pic 14]

[pic 15][pic 16][pic 17][pic 18]

[pic 19][pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27]

[pic 28]

2. Σ = {0, 1}. L = lenguaje de las cadenas sobre Σ que tienen un número par de símbolos (cadenas de longitud par). AFD M tal que L (M) = L:[pic 29]

[pic 30]

[pic 31]

[pic 32]

[pic 33][pic 34][pic 35][pic 36][pic 37]

      [pic 38]

[pic 39]

[pic 40]

3. Σ = {0, 1}. L = lenguaje de las cadenas sobre Σ que contienen un número par de ceros. AFD M tal que L (M) = L:[pic 41]

[pic 42][pic 43]

[pic 44][pic 45][pic 46]

[pic 47]

[pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55]

[pic 56]

[pic 57]

[pic 58]

[pic 59]

4. Σ = {a, b}. L = lenguaje de las cadenas sobre Σ que terminan en b. AFD M tal que L

(M) = L:

[pic 60][pic 61]

[pic 62][pic 63][pic 64]

[pic 65][pic 66]

...