Trabajo colaborativo 2

Tutor:

JAIME VALDES

Presentado

Nelson Javier López Jiménez

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA

INGENIERIA ELECTRONICA

AUTOMATAS Y LENGUAJES FORMALES

BOGOTA

Julio 28de 2014

INTRODUCCIÓN

Mediante el desarrollo del trabajo colaborativo de la unidad 2 del curso de Autómatas y Lenguajes

Formales pretendemos poner en práctica los conceptos básicos aprendidos hasta el momento acerca de los lenguajes independientes del contexto, sus conceptos generales, sus propiedades y su relación con los autómatas a pila.

También es importante complementar la solución de los ejercicios de la actividad a través del uso de herramientas computacionales de simulación, empleando los conceptos aprendidos en nuestros estudios de las diversas ramas de la Ingeniería en nuestra Universidad.

Para ello, se pretende resolver lo solicitado en la guía de la actividad mediante el trabajo individual y colaborativo de los miembros del grupo No. 15 a través de la Plataforma Virtual del curso buscando fomentar la investigación, el trabajo en equipo, el dialogo y la concertación como pilares fundamentales de la filosofía Unadista.

OBJETIVOS:

1. Conocer los modelos de computación que corresponden a los lenguajes independientes del contexto y su aplicación.

2. Generalizar los conceptos de autómatas finitos y gramáticos regulares.

3. Reconocer el potencial de procesamiento del lenguaje del autómata con los Autómatas de pila.

4. Desarrollar las competencias comunicativas con sus compañeros de grupo al realizar un trabajo colaborativo concertado bajado en la investigación individual y un dialogo grupal respetuoso y constructivo.

5. Afianzar las competencias argumentativas al exponer la resolución de un problema utilizando los conceptos del módulo.

DESARROLLO

1. Calcular el autómata mínimo correspondiente al siguiente autómata finito.

1. Enuncie el autómata en notación matemática

M= {q0, q1, q2, q3, q4} {a,b} Ơ , q0,q3DondeK= {q0, q1, q2, q3, q4} ∑= { a,b } s= q0 F= q3

2. Identifique los componentes del autómata (que tipo de tupla es)

Es un autómata determinístico. 3. Identifique la tabla de transición correspondiente

4. Identifique el lenguaje que reconoce y enuncie cinco posibles cadenas válidas que terminen en el estado “halt”

El lenguaje q reconoce será el de todas las posibles cadenas ω que empiecen por “ab” y que terminen en “b”, bajo ciertas condiciones que resultan complejas (ER) por eso se minimiza.Cadenas validas {abb} {abbb} {abab} {ababb} {abbab}

5. Encuentre la expresión regular válida.

6. Encuentre su gramática que sea válida para la función de transición (describa sus componentes y como se escriben matemáticamente). Justifíquela si la convierte a la Izquierda o a la derecha. Plásmela en el simulador y recréela. (Debe quedar documentado en el texto el paso a paso que realizan en el simulador)

Componentes y como se escriben matemáticamente

Aclarando: definimos gramáticacomo el conjunto de reglas que sirven para formar correctamente las frases de un lenguaje, se indica con la letra “G”.

En si la gramática para nuestro caso es un cuádruplo donde.

V Es un alfabeto de variables {S,A,B,C,D} ∑ Es un alfabeto de constantes {a,b} R Es el conjunto de reglas vx{ ∑ vU ∑ } S Es símbolo inicial un elemento de v

Justifíquela si la convierte a la Izquierda o a la derecha

Es convertida por la derecha porque todas sus producciones tienen la forma:

7. Realice el árbol de Derivación de esa gramática

Identifique si ese árbol o gramática es ambigua o no y plasme las razones de su afirmación

Definitivamente nuestro autómata es deterministico y no presenta ambigüedad, puesto que siempre presenta una ruta determinada.

ACTIVIDADES PARA EL EJERCICIO A MINIMIZAR O YA MINIMIZADO:

10. Explicar el proceso de Minimización (que estados sesuprimen y porque) En el caso de los AFD la simplificación es reducir estados pero de forma que se acepte el mismo lenguaje al igual que antes de la simplificación.

a. Definimos el autómata e identificamos lo que va a cambiar

b. Eliminar estados inaccesibles de m – se identifican los estados que pueden ser

e liminados por ser equivalentes.

c. Identificar estados distinguibles – recordar quesi son equivalentes no son distinguibles.

d. Construcción de tabla

11. Que transiciones se reemplazan o resultan equivalentes. El estado ₁será eliminado ya que es equivalente.

CONCLUSIONES

Con el desarrollo del trabajo colaborativo No. 2, realizada por parte de los estudiantes del grupo 45 de la asignatura de Autómatas y Lenguajes Formales, hemos comprendido de manera clara el contenido de la unidad No. 2 del presente curso y así apropiarnos de estos importantes fundamentos teóricos y prácticos aprovechando todos los recursos dispuestos por nuestro Tutor a través del aula virtual de nuestra Universidad.

A través del trabajo individual, la puesta en comúnde los productos ante el grupo y un dialogo fluido entre las partes intervinientes en la actividad, se logró la concertación de la mejor alternativa de solución de los ejercicios solicitados por el Tutor, esperando cumplir con los objetivos planteados en la actividad con eficacia y eficiencia.

Esta actividad nos permite acercarnos a la meta de crecer como estudiantes Unadistas de las diversas ramas de la Ingeniería tanto a nivel intelectual como de requisitos académicos vislumbrando nuestra futura titulación.

BIBLIOGRAFÍA

CARLOS ALBERTO AMAYA TARAZONA. (2014). AUTÓMATAS Y LENGUAJES FORMALES. Duitama (ZCBOY): UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA.DIRECCIÓN

ELECTRÓNICA: http://www.exa.unicen.edu.ar/catedras/ccomp1/Apunte3.pdf DIRECCIÓN ELECTRÓNICA http://luzem.dyndns.org/tag/jflap/ DIRECCIÓN ELECTRÓNICA: http://www.ia.urjc.es/grupo/docencia/automatas_itis/examenes/itis/

solucion_final_sep_2009.pdf MODULO: AUTÓMATAS Y LENGUAJES FORMALES. UNAD. 2011. LIU C. L. Elementos de matemáticas discretas segunda edición. Editorial: McGraw-Hill Interamericana, Méjico, 1995, páginas 447. PLATAFORMA VIRTUAL DE LA UNAD: Curso virtual de Autómatas y Lenguajes Formales.