TRABAJO COLABIRATIVO 1 AUTOMATAS

AUTOMATAS Y LENGUAJES FORMALES

APORTE AL TRABAJO COLABORATIVO 1

PRESENTADO POR:

YOLIMA ACUÑA TORRES

39.098.240

TUTOR

CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA “UNAD”

FACULTAD DE CIENCIAS BÁSICAS E INGENIERÍA

CERES PLATO

OCTUBRE DE 2012

1. http://www.slideshare.net/diegoaper/examen-final-autmatas-y-lenguajes-formales

Defina y de un ejemplo claro de: (No se aceptan ejemplos tomados del módulo, de textos guías, o de consultas bibliográficas de la Biblioteca Virtual UNAD). Son ejemplos creados con objetividad por ustedes los estudiantes.

Alfabeto: Corresponde al bloque constructor más sencillo de los lenguajes.

Es un conjunto finito de símbolos (es decir tienen un límite y un final)

Símbolo: No se hace referencia a un solo carácter. Los símbolos pueden ser nombres

Lenguaje: Conjunto de cadenas sobre un alfabeto, no necesariamente finito.

Expresión regular: Define de forma declaratoria las cadenas aceptables o pertenecientes a un lenguaje regular

SIMBOLO:

S= {1,3,5,7,9,}

ALFABETO:

∑= {11,13,15,17,19,111,113,115}

LENGUAJE

L1={1111,111111,11111111}

L2={1113,1115,1117}

L3=Ø

EXPRESION REGULAR:

R= (1113)*=111, 11133, 111333,1113333,11133333.

2. Partiendo de la definición de que un Autómata Finito Determinístico (AFD) está dado por la quíntupla: 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.

• q 0 ∈ Q es el estado inicial.

1. • F ⊆ Q es el conjunto de estados finales que para el ejercicio, el autómata acepta las cadenas (01) n1) :

A = ({q0, q1, q3, q4} , {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

Lenguaje Aceptado:

Tabla de transición

0 1 0,1

#q0

q1 q2 0

#q1 q3 q0 0

#q2 0 0 q3

#q3 0 0 q3

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.

Según lo visto en el ejercicio

...