Trabajo Automata

TRABAJO COLABORATIVO 1
CURSO: AUTOMATAS Y LENGUAJES FORMALES

EDUARDO YAIR ARRIETA DOMINGUEZ
Eduardojad11@hotmail.com
CODIGO: 1124021336

GRUPO: 301405

TUTOR:
 JESUS EMIRO VEGA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA –UNAD-
FACULTAD DE INGENIERIA DE SISTEMAS
CEAD COROZAL
ABRIL 2012
INTRODUCCION

El presente trabajo está realizado con el fin de analizar y comprender losdiferentes temas propuestos en la primera unidad del modulo de Autómatas y
Lenguajes Formales afianzando conocimientos sobre Lenguajes, Expresiones
regulares, al igual que Autómatas finitos.
Como parte fundamental de este trabajo encontraremos ejercicios realizados
con los programas Visual Autómata Simulator (VAS) y/o el JFLAP.

OBJETIVOS

OBJETIVO GENERAL
Reconocer y aplicar los conceptosestudiados en la unidad 1, como lenguajes regulares, autómatas finitos y su aplicación.

OBJETIVOS ESPECIFICOS
* Verificar lenguajes y cadenas aceptados por los AFD y AFND
* Utilizar el software simulador para plasmar los diferentes ejercicios de autómatas finitos.

EJERCICIOS A DESARROLLAR:
1. Defina y de un ejemplo claro de: (No se aceptan ejemplos tomados del módulo, de textosguías, o de consultas bibliográficas de la Biblioteca Virtual UNAD). Son ejemplos creados con objetividad por Uds los estudiantes.
SIMBOLO: Es una representación gráfica sencilla de una idea, que es comúnmente aceptado y entendido por quienes lo reconocen.
ALFABETO: Es un conjunto de símbolos o caracteres que representan letras con las que se pueden crear palabras.
LENGUAJE: Es un conjunto depalabras que se crean mediante un alfabeto previamente creado o identificado.
EXPRESION REGULAR: Es un conjunto de cadenas de símbolos o caracteres que sirven para representar lenguajes regulares.

2. Partiendo de la definición de que un Autómata Finito Determinístico (AFD) está dado por la quíntupla: A = (Q, Σ, f, q, F) donde: 0
• 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) 1): n
, A = ({q, q, q, q} , {0,1} , f , q, { q}) 012302
Representado mediante el grafo:

EN UN SIMULADOR (YA SEA JFLAP O VAS)
• Plásmelo en el simulador

• Realice la tabla de transicióncorrespondiente.
A | 0 | 1 |
q0 | q1 | q2 |
q1 | q3 | q0 |
q2* | q3 | q3 |
q3 | q3 | q3 |

• Compruebe el lenguaje aceptado
L= (01) *1

3. Acorde al autómata del ejercicio N 2, explique o justifique de donde proviene el nombre “finito”. (Sea objetivo y creativo). No copie contextos puntuales de los libros o de la web.
En el autómata del ejercicio N 2 se evidencia que los autómatas finitostienen
un número finito de estados.

4. Acorde al siguiente diagrama de Moore:

Cuáles de las siguientes expresiones representa:
Justifique su respuesta, incluso para las expresiones que no representa.
A. Expresión regular (q|q)1* Es incorrecta esta opción dado que q no
corresponde a un estado de aceptación.
B. Expresión regular (ac|b)* Es correcta porque se está representando unaoperación de una expresión regular (el cierre u operación estrella)
C. Expresión regular (bb|ab)* Es incorrecta porque no está teniendo en cuenta
el elemento "c"
D. Expresión regular (ac|b|b)*

5. Construya un autómata que reconozca las cadenas las cadenas que contienen la subcadena aba y cuya definición formal sería la siguiente:
Se recomienda primero realizarlo en papel (graficarlo a manoalzada antes de llevarlo al simulador.
Q = {1,2}
Σ={a,b}
I={1}
F={2}
Δ ={((1,a),1),((1,b),1),((1,aba),2),((2,a),2),((2,b),2)}
• Realice el diagrama de Moore en el simulador.

• Construya Tabla de Transición.
A | a | b | a,b,a |
1 | 1 | 1 | 2 |
2 | 2 | 2 | - |

• En el simulador demuestre las cadenas de entrada válidas (aba).

6. Para el siguiente AFND representado en el...