Trabajo Colaborativo 1 Automatas Y Lenguajes Formales

TRABAJO COLABORTIVO 1

AUTÓMATAS Y LENGUAJES FORMALES

TUTOR:

Jaime José Valdés

PRESENTADO POR:

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA

Abril 2013

INTRODUCCIÓN

Por medio de este trabajo se aplican los conocimientos adquiridos en la primera unidad del curso, donde se aplican las definiciones y graficas de Autómatas, tanto en AFD como AFND, sustentando de esta menara los conceptos estudiados y apoyándonos en el pequeño grupo de trabajo.

El alfabeto consiste en un conjunto vacio de símbolos, con estos símbolos es posible formar secuencias o cadenas de caracteres, estas cadenas son llamadas también palabras.

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 del lenguaje 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 los dispositivos 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.

OBJETIVOS

OBJETIVO GENERAL

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

OBJETIVOS ESPECIFICOS

• Aplicar los estudios 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.

• Identificar los tipos de lenguajes formales existentes.

EJERCICIOS A DESARROLLAR:

1. Para los siguientes ejercicios identifique el lenguaje que reconoce y plasme cinco posibles cadenas válidas que representan esa ER:

Si A = {a,b,c}

c) (a +b)

R/= (a,b)

d) (a + b ) *

R/= (a,b aa,aba,abba,aabbaa…)

e) (a+ λ) b*

R/= (a, a ƛ, ab,a ƛbbbbb…)

f) a (ab)*

R/= (a, ab, a abbbbb…)

g) λ∗

R/= (λ, λ λ, λ λ λ, λ λ λ λ…)

Si A = {0,1}

h) 000

R/= (000)

i) 10* + 1

R/= (1, 10 1, 1010 1, 101010 1…)

j) 01* + 0

R/= (0, 01 0,0101 0,010101 0,01010101 0…)

k) (1 – 110) *

R/= ( 110, 1, 11, 111…)

l) (1 + 10) +

R/= (1,10 , 1,10, 1,10)

m) 1* 0*

R/= (1 0,1100,111000…)

n) 00* 11*

R/= (0011,00001111,000000111111…)

...