Tc1 Automatas Y Lenguajes Formales

TRABAJO COLABORATIVO 1

Datos Estudiantes:
MATEUS CARPIO
COD:
Mail:
Zona
SANDRA MILENA RAMIREZ
COD: 1066180324
Mail:
Zona:
HALLY GRACE MAHECHA CIFUENTES
COD: 1070589487
Mail: hally.grace@gmail.com
Zona: José Acevedo y Gomez

Tutor:
JAIME JOSE VALDES

UNIVERSIDAD NACIONAL ABIERTA Y ADISTANCIA
ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA
2012
INTRODUCCION

Uno de los hechos que se destacaen la informática es que las áreas genéricas del conocimiento humano como es la lógica y el álgebra, han tenido que especializarse, o particularizarse para ser utilizados en esta área, de aquí surge el uso de la lógica matemática, lógica de conjuntos, teoría de grafos, entre otros, para su aplicación en las ciencia de las computadoras., extendiéndose en tantas direcciones como la teoría dellenguaje, el no determinismo así como las expresiones regulares y las gramáticas libres de contexto.

Lenguajes regulares tienen gran importancia en el diseño de los lenguajes de programación ya que los componentes básicos de un LP constituyen LRs., estos pueden describirse como elementos que se generan, como cadenas a partir de cadenas sencillas, con el uso de operaciones de cadenas o el desarrollo dellenguaje mismo, que se puede generar con otros lenguajes más sencillos mediante operaciones de conjuntos.

Los Lenguajes más sencillos son los considerados lenguajes regulares, es decir, los que se pueden generar a partir de lenguajes de un elemento con la aplicación de ciertas operaciones estándar realizadas un número finito de veces.

Estos son pues los lenguajes que pueden reconocer losdispositivos llamados Autómatas finitos (AF) que son máquinas de cómputo con memoria muy restringida. En esta unidad se considera como segundo aspecto la idea de que un lenguaje no sea regular, además de proporcionar un modelo sencillo de computación que se puede generalizar en las unidades siguientes.

OBJETIVO GENERAL

Identificar y analizar la temática de los lenguajes regulares, autómatas finitos ysus aplicaciones.

OBJETIVOS ESPECIFICOS

* Estudiar los conceptos fundamentales de la teoría de autómatas y lenguajes formales, para la descripción de ellos.

* Conocer como es el desarrollo aplicación de los lenguajes regulares y los autómatas finitos.

* Distinguir los diferentes tipos de lenguajes formales existentes.

* Implementar el uso de diagramas de Moore, y minimización deautómatas finitos etc., para el desarrollo de situaciones de lenguajes y autómatas presentes.

DESARROLLO DE LAS ACTIVIDADES
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?

R//= LØ=Ø

b) λ es una ER que denota el lenguaje?

R//= Lλ=λ

En general los lenguajes que pueden representarse mediante una expresiónregular se llaman lenguajes regulares. Estos coinciden con los aceptados por los autómatas finitos.

Es importante que tengamos definido o claro que Si r y s son ER denotando los lenguajes R y S, entonces se definen tres operaciones muy básicas:

- Unión: (r + s) es una expresión regular ER que denota el lenguaje R S
- Concatenación: (rs) algunos autores lo toman como (r·s) es una expresión regularER que denota le lenguaje RS.
- Clausura: r* es una expresión regular ER que denota el lenguaje R
Para efectos de plasmar las ER, los paréntesis se pueden eliminar siempre y cuando los símbolos y caracteres no alteren la interpretación de otros caracteres o cadenas. La precedencia de las operaciones es: clausura / Concatenación / Unión.
Para los siguientes ejercicios identifique el lenguaje...