Automatas Y Lenguaje Formales

TUTOR:
JAIRO RIANO

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA “UNAD”
FACULTAD DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA
ABRIL 2010

INTRODUCCIÓN

Para la realización de este producto se elaboro una estrategia correspondiente en elaborar aportes individuales sobre los ejercicios propuestos que fueron puestos en el foro, donde el coordinador del trabajo elaboro el modelo inicialrecopilando y organizando los aportes individuales presentados por los demás compañeros, el modelo fue puesto en consideración del grupo para que se le hicieran los ajustes necesarios (incluida esta introducción), en la medida que llegan los aportes se incluye el nombre del estudiante en la lista de participantes, de manera tal que al final del proceso se incluyen los nombres de quienes hicieron aportes.AUTOMATAS Y LENGUAJES FORMALES

Ejercicios Propuestos:

1.- Dado el siguiente autómata con pila, indicar:

(a) Qué lenguaje reconoce
(b) Cuáles de las siguientes palabras son aceptadas por el autómata:

aabbc, abbc, bbcc, aabbbcc (mostrando la sucesión de descripciones instantáneas)

AP = ({a, b, c}, {A, B, S}, {q, r, s, t}, q, S, f, Ø)
f(q, a, S) = {(r, S)} f(s, b, S) = {(s, BS)}f(q, a, A) = {(r, A)} f(s, b, A) = {(s, λ)}
f(q, b, S) = {(s, BS)} f(s, b, B) = {(s, BB)}
f(q, b, A) = {(s, λ)} f(s, c, B) = {(t, λ)}
f(r, a, S) = {(q, AS)} f(t, c, B) = {(t, λ)}
f(r, a, A) = {(q, AA)} f(t, λ, S) = {(t, λ)}

R/ Para verificar si cada cadena fue aceptada se realizo el siguiente procedimiento teniendo en cuenta: AP = ({a, b, c}, {A, B, S}, {q, r, s, t}, q, S, f, Ø)

a) Ellenguaje que reconoce es: [pic]
b) aabbc SE ACEPTA

|B |
|B |
|A |
|S |
|S |

f(q,a,S)
f(r,a,S)
f(q,b,A)
f(s,b,S)
f(s,c,B)

[pic]

abbc SE RECHAZA.

f(q,a,S)

f(r,b,S) Esta iteración no aparece en las combinaciones

bbcc SE ACEPTA

|B |
|B |
|S|

f(q,b,S)
f(s,b,B)
f(s,c,B)
f(t,c,B)

[pic]

aabbbcc SE ACEPTA

|B |
|A |
|B |
|S |

f(q,a,S)
f(r,a,S)
f(q,b,A)
f(s,b,S)
f(s,b,B)
f(s,c,B)
f(t,c,B)

[pic]

2.- Definir formalmente el lenguaje reconocido por el siguiente autómata con pila:

A = ({a,b,c}, {S,A,B}, {q,r,s,p}, q, S, f, ∅)
f(q, a, S) = {(r, S)} f(s, b, S) = {(s, BS)}
f(q, b,S) = {(s, BS)} f(s, b, A) = {(s, λ)}
f(q, a, A) = {(r, A)} f(s, b, B) = {(s, BB)}
f(q, b, A) = {(s, λ)} f(s, c, B) = {(p, λ)}
f(r, a, S) = {(q, AS)} f(p, c, B) = {(p, λ)}
f(r, a, A) = {(q, AA)} f(p, λ, S) = {(p, λ)}

Diagrama de Moore:

R/ Según las pruebas realizadas con varias cadenas como:

• aabbc CADENA ACEPTADA
• aaaabbbbcc CADENA ACEPTADA
• aabbb CADENARECHAZADA
• bbccc CADENA RECHAZADA
• aabbcc CADENA RECHAZADA
El lenguaje que reconoce este autómata con pila es: [pic]

3.- Dado el siguiente automata con pila indicar:

(a) Que lenguaje reconoce por vaciado de pila.
(b) Cuales de las siguientes palabras son aceptadas por el AP: abba, abaaba.

AP = ({a,b}, {Z}, {q0, q1, q2, q3}, q0, Z, f, Æ)

f(q0, a, Z) = {(q1, aZ)}f(q2, b, b) = {(q2, λ)}
f(q0, b, Z) = {(q1, bZ)} f(q2, a, a) = {(q2, λ)}
f(q1, a, a) = {(q1, aa), (q2, λ)} f(q2, λ, Z) = {(q2, λ)}
f(q1, a, b) = {(q1, ab)}
f(q1, b, a) = {(q1, ba)}
f(q1, b, b) = {(q1, bb), (q2, λ)}

Diagrama de Moore:

a. Reconoce el lenguaje: L= (a (ba)n a / n > 0)
b. Las palabras que son aceptadas por el autómata son:

abba
|ESTADO |PILA|CADENA |
|q0 |Z |abba |
|q1 |aZ |bba |
|q1 |baZ |ba |
|q2 |aZ |a |
|q2 |Z |λ |
|q2 |Λ |λ |

abaaba

|ESTADO |PILA |CADENA |
|q0...