El estudio de los temas Automáticos y Lenguajes formales

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

TRABAJO COLABORATIVO UNIDAD NO. 1

Presentado por:

JESUS ANTONIO BARBOSA CABREJO

C.C. 80.763.813

Jesus.barbosa28@hotmail.com

JOHN FRANCISCO NEIRA

Nº de grupo: _9

Presentado a:

JAIME JOSE VALDES

AUTÓMATAS Y LENGUAJES FORMALES

CEAD VALLE DEL GUAMUEZ

LA HORMIGA – PUTUMAYO

DICIEMBRE DE 2011

INTRODUCCION

Uno de los hechos que se destaca en 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 del lenguaje, 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 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.

1. OBJETIVO GENERAL

Identificar y analizar la temática de los lenguajes regulares, autómatas finitos y sus 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 de autómatas finitos etc., para el desarrollo de situaciones de lenguajes y autómatas presentes.

EJERCICIOS A DESARROLLAR:

1. Construya un autómata que reconózcalas cadenas que contienen la subcadena aba y cuya definición formal sería la siguiente:

Q = {1,2}

Σ={a,b}

I={1}

F={2}

Δ={((1,a),1),((1,b),1),((1,aba),2),((2,a),2),((2,b),2)}

 Tabla de Transición:

f a b g a b

q1 q1,q2,q2 q1,q2 q1 1,2,2 1,2

q2 q2 q2 q2 2 2

 Realice el diagrama de Moore

 En el simulador demuestre las cadenas de entrada válidas (aba).

2. Para el siguiente AFND representado en el diagrama, identifique la tabla de transición correcta que lo representa:

 Constrúyalo en los simuladores:

 Tabla de transición:

f a b

qo q3 q1

q1 Ø q2

q2 q2 q2

q3 q3,q4 q3

q4 q4 q4

 Verifique el lenguaje aceptado por el autómata en el simulador

q0 = aq3 + bq1

q1 = 0 + bq2

q1 = bq2

q2 = aq2 + bq2

q2 = (a + b) q2

q3 = aq3 ι aq4 + bq3

q3 = (a + b) q3 l aq4 + bq3

q4 = aq4 + bq4

q4 = (a + b) q4

Lenguaje descrito por la expresión regular:

L(A) = ((aa(a+b)*) + bb)(a+b)*

3. Para el siguiente autómata, constrúyalo en el simulador, identifique claramente las Cadenas y subcadenas válidas y justifíquelas

Q= {q0, q1, q2, q3, q4}

A= {a,b}

q0

F = (q4)

δ (q0,a)=q1

δ (q0,b)=q3

δ (q1,b)=q2

δ (q1,a)=q3

δ (q2,a)=q4

δ (q2,b)=q3

δ (q3,a)=q3

δ (q3,b)=q3

δ (q4,a)=q4

δ (q4,b)=q4

LMA = (aba(a+b)*)

Las únicas que son aceptadas por al autómata son las iniciadas por aba, dado que las otras opciones quedan en un ciclo aislado en q3.

4 Para el siguiente autómata, M =(Q, A, q0, δ, F) donde:

Q = {q0, q1, q2,q3}

A = {a, b}

q0

Es el estado Inicial

δ (q0,a)=q1

δ (q0,b)=q2

δ (q1,b)=q1

δ (q1,a)=q3

δ (q2,a)=q0

δ (q2,b)=q2

δ (q3,a)=q1

δ (q3,b)=q2

LMA = (a+(b*))(ab+(b*))

5. Para el siguiente autómata finito determinista dado por:

M = ({q0, q1, q2, q3}

...