Aporte al trabajo colaborativo n1 de automatas

AUTOMATAS Y LENGUAJES FORMALES

WILSON RICARDO ARIAS CARMONA
93.062.246

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA
ESCUELA CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA
CEAD FLORENCIA
MARZO2011

DESARROLLO CUESTIONARIO

1. Obtener el lenguaje reconocido por el siguiente AFD:
A = ({q0, q1, q2, q3, q4}, {a, b, c}, f, q0, {q2}) R/:

[pic]
Q= {q0, q1, q2, q3, q4}
Σ= {a, b, c}f= función de transición
v=q0 →
F=q2 #

El lenguaje reconocido es:
L= {v ∈ Q | (q0,Q) ├* (q2,F) }

2.- Con base en el siguiente Diagrama de Moore: Realice las siguientes Actividades:

[pic]a. Generalice mediante una expresión regular y explique el lenguaje que acepta el Autómata.

A+3B*=Y

b. Construya la respectiva tabla de transición

|f |1|2 |3 |
|q1 |q1 |q1 |q2|
|q2 |q3 |q3 |q3 |
|q3 |q3|q3 |q3 |

c. Defina el Autómata como un conjunto de cinco elementos

B=({q1,q2,q3,},{1,2,3},f,q1{q2})

f(q1, 1) = q1f(q1, 2) = q1 f(q1, 3) = q2
f(q2, 1) = q3 f(q2, 2) = q3 f(q2, 3) = q3
f(q3, 1) = q3 f(q3, b) = q3 f(q3, 3) = q3

4. Decir cuáles de las siguientes palabras son reconocidas por el siguiente:AFND: 110, 01, 100
AFND = ({0, 1}, {q0, q1, q2}, q0, {q1})

f(q0, 0) = Æ f(q0, 1) = {q1, q2} f(q0, λ) = Æ
f(q1, 0) = {q0} f(q1, 1) = {q0, q1} f(q1, λ) = {q0}
f(q2, 0) = {q2}f(q2, 1) = Æ f(q2, λ) = {q1}

[pic]
R/:
Este AFND reconoce las siguientes palabras:

f(q0, 1)= {q1,q2}
f(q1, 0)= {q0}
f(q1, 1)= {q0,q1}
f(q2, 0)= {q2}

5. Determinar...