Automatas 1
Enviado por darkcraft29 • 20 de Noviembre de 2012 • 1.412 Palabras (6 Páginas) • 875 Visitas
TALLER
Sobre
AUTOMATAS Y LENGUAJES FORMALES
JESUS ALBERTO PULIDO SILVA
KATERINE FERNÁNDEZ CARVAJAL
YULIVETH COQUECO
UNIVERSIDAD NACIONAL ABIERTA Y A DISTACIA (UNAD)
FACULTAD DE CIENCIAS BASICAS E INGENIERIA
PROGRAMA INGENIERIA DE SISTEMAS
NEIVA
2012
TALLER
Sobre
AUTOMATAS Y LENGUAJES FORMALES
JESUS ALBERTO PULIDO SILVA
KATERINE FERNÁNDEZ CARVAJAL
YULIVETH COQUECO
Integrantes
Tutor:
JAIME JOSE VALDES
UNIVERSIDAD NACIONAL ABIERTA Y A DISTACIA (UNAD)
FACULTAD DE CIENCIAS BASICAS E INGENIERIA
NEIVA
2012
EJERCICIOS A DESARROLLAR:
1. Para el siguiente ejercicio, recordaremos ciertas apreciaciones, conceptos o
afirmaciones acerca de las Expresiones Regulares, comúnmente denotadas
como “ER”:
Una expresión regular es una forma de representar cierto tipo de lenguajes sobre
un determinado alfabeto. Son exactamente los aceptados por los autómatas de
estado finito.
Si tomamos como A un alfabeto, unas posibles expresiones regulares sobre ese
alfabeto podrían ser: (identifique que lenguaje reconoce esa ER)….
a) Ø es una ER que denota el Lenguaje vacío
b) λ es una ER que denota el lenguaje de cadena vacía
si A = {a,b,c}
c) (a +b)
a
b
d) (a + b ) *
ab
a
abb
abab
b
e) (a+ λ )b*
a
ab
abb
abbb
abbbb
f) a (ab)*
a
aab
aabab
aababab
aabababab
g) λ∗
λ
si A = {0,1}
h) 000
i) 10* + 1
j) 01* + 0
k) (1 – 110) *
l) (1 + 10) +
m) 1* 0*
n) 00* 11*
o) (0+1)*11(1+0)*
2. Partiendo de la definición de que un Autómata Finito Determinístico (AFD) está
dado por la quíntupla: A = (Q, ∑, f, q0, F) donde:
• Q es un conjunto de estados.
• ∑ es el alfabeto de entrada
• f: Q X ∑ → Q es la función (total) de transición.
• q0 ∈ Q es el estado inicial.
• F ⊆ Q es el conjunto de estados finales.
Y que para el ejercicio, el autómata acepta las cadenas (01) n1) :,
A = ({q0, q1, q2, q3} , {0,1} , f , q0, { q2})
Representado mediante el grafo:
EN UN SIMULADOR (YA SEA JFLAP O VAS)
• Plásmelo en el simulador
• Realice la tabla de transición correspondiente.
• Compruebe el lenguaje aceptado
• Identifique la expresión regular que permite identificar que cadenas son válidas y que acepta el autómata.
Tabla de transición:
Lenguaje aceptado:
L = {}
ER = (01)* 1
4. Para el siguiente Autómata que acepta el lenguaje:
L = { ω ϵ {a,b,c}* │ω = abic, i >= 0}
Realice las siguientes actividades:
• Determine si es un AFD ó AFND
Es un autómata finito determinístico ya que se conoce la única cadena de entrada y se conoce el estado siguiente
• Encuentre la ER
ER=ab* c
• Gráfico en un diagrama de Moore
• Realice la tabla de transición
• De cinco (05) ejemplos de cadenas válidas que acepte el autómata
• Recréelo en el simulador
5. Construya un autómata que reconozca cadenas enmarcadas dentro de la
expresión regular: (10 + 0)* Tenga en cuenta que debe incluir cadenas
vacías del tipo λ
Se recomienda primero realizarlo en papel (graficarlo a mano alzada antes de
llevarlo al simulador.
• Identifique los elementos de la tupla a que corresponda ese autómata y
descríbalos.
M=({q0, q1 }, {0,1},δ, q0, {q0})
Donde la función: δ =({q0, q1 } × {0, 1} → {q0, q1 } viene dada por:
δ(q0,) = q0
δ(q0,) = q1
δ(q1, 1) = q1
δ(q1, 0) = q0
• Realice el diagrama de Moore en el simulador y plásmelo en el trabajo.
• Construya Tabla de Transición.
• En el simulador demuestre las cadenas de entrada válidas.
• Identifique el lenguaje que reconoce.
L = {* }
...