Automatas

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 - trabajo colaborativo 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 pueden considerar 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 de un 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ómatas finitos 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), encuentre la expresión mínima simplificada correspondiente.

ER1 (0(1)*) + 1 █(0(1)*+1@)

█(01*+1@)

01*+1

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

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

1+11*1

11*1111*

1λ+11*

11*

λ+11*

1*

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

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

0+(1)(1)*0

0+1+λ1*0

0+λ+11*0

1*0+0

1*0

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

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

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

1*0+1*0(0+1)(0+1)*

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

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

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

1*0+1*0(0+1)*

1*0(0+1)*

ER5 ((0+1)1) ((0+1)1)

(0+1)1

2. PARA LA EXPRESION REGULAR 4: 1*0+1*0(λ+0+1)*(λ+0+1)

RESUELVA:

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)

L={1^n 0,1^m 0,(λ,0,1)^ñ (λ,0,1)}│n,m,ñ≥0}

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)

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

q0+q1●q2●q3

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 puede acceder a él desde ningún otro estado), según regla de minimización de autómatas.

q0=1q0+0q1

q1=1q1+0q2

...