Momento 1 Grupo 301405 26 1



MOMENTO 1





Por:
AURELIO NÚÑEZ GENES
C.C. 1.039.083.901

LUZ ESTELA CANO CALVO
C.C. 25.038.357

JUAN CAMILO TABORDA
C.C: 8103507

ALEJANDRO ARBELAEZ CASTAÑEDA
C.C. 14.566.479


Curso:
AUTÓMATAS Y LEGUAJES FORMALES




Tutora:
ÁNGELA MARÍA GONZÁLEZ


Grupo:
301405_26


UNIVARSIDAD NACIONAL ABIERTA Y A DISTACIA


2015

INTRODUCCIÓN

Mediante del desarrollo de esta actividad - trabajocolaborativo en el curso de Autómatas y lenguajes formales, nos permite en nuestra formación profesional la asimilación de los conceptos y mecanismos fundamentales para la definición de lenguajes.
La investigación científica acerca del tema desarrollado nos permite, indagar, adquirir conceptos y conocimientos de los procesos y sus estados en la determinación de lenguajes.
Los lenguajes se puedenconsiderar como elementos que se generan, como son las cadenas a partir de cadenas sencillas, con el uso de operaciones de cadenas o el desarrollo del lenguaje mismo, se puede generar con otros lenguajes más sencillos mediante operaciones de conjuntos.
Teniendo en cuenta que los lenguajes más sencillos son considerados lenguajes regulares y estos a su vez se pueden generar a partir de lenguajes deun elemento con la aplicación de ciertas operaciones estándar realizadas un número finito o determinado de veces, conociéndose así lenguajes que pueden reconocer dispositivos denominados como autómatas finitos (máquinas de cómputo con memoria muy restringida.
Los intentos de formalizar los lenguajes naturales, lleva a la construcción de gramáticas, como una forma de describir estos lenguajes,utilizando para ello reglas de producción para construir las frases del lenguaje. Se puede entonces caracterizar un lenguaje mediante las reglas de una gramática adecuada.
Como elemento determinante se tiene en cuenta los conceptos matemáticos básicos de conjuntos, funciones, relaciones y principios fundamentales de la lógica.








OBJETIVO GENERAL.


Reconocer los lenguajes regulares, autómatasfinitos y su aplicación.


OBJETIVOS ESPECIFICOS.


Estudiar la aplicación de los lenguajes regulares y los autómatas finitos.

Adquirir las habilidades necesarias para desarrollar autómatas y máquinas que reconozcan lenguajes o computen funciones.

Distinguir las expresiones regulares existentes y su simplificación.




ACTIVIDAD
1. Dada las siguientes expresiones regulares (ER), encuentrela expresión mínima simplificada correspondiente.
ER1
(0(1)*) + 1



ER2
λ+1+(λ+ 1)(λ+ 1)*(λ+ 1)








ER3
0 + (λ+ 1)( λ+ 1)*0







ER4
1*0 + 1*0(λ +0+1)*(λ +0+1)
1








ER5
((0+1)1)




2. PARA LA EXPRESION REGULAR 4:
RESUELVA:

1. Describa la forma matemática del autómata
La forma matemática del autómata es:

M = {q0,q1,q2,q3},{ λ,0,1},σ,q0,{q3} donde K = { q0,q1,q2,q3} ∑= { λ,0,1},S= q0 F= q3

La forma matemática del lenguaje del autómata: (Se desarrolla como valor agregado al trabajo Colaborativo)


2. Plasme la tabla de transición. Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el concepto de determinismo)


f
0
1
λ
→q0
q1
q0

q1
q2
q1

#q2
q2
q2
q2
q3
q3
q3
q3
Eliminamos q3 ya que es un estando inaccesible (no se puedeacceder a él desde ningún otro estado), según regla de minimización de autómatas.



















Con base en la información obtenida en la tabla de transición, se puede afirmar que se trata de un autómata tipo AFD (autómata finito determinístico), ya que el q0 pasa a q1 por una sola transición la cual es 0 y q1 pasa q2 también con una sola transición que es 0 y como q3 es una transicióninaccesible ya que ningún estado puede llegar a ella, se elimina según las regla de minimización.

3. Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales.

M es un quíntuplo (K, Σ, δ, s, F), donde:

K = {q0, q1, q2, q3},...