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

q2=λq2+0q2+1q2+λ

q2=(λ+0+1)q2+λ=

q2=(λ+0+1)*λ=

q2=(λ+0+1)*

q1=1q1+0q2=

q1=1*(0q2)=

█(0(λ+0+1)*@q1=1*)

q0=1q0+0q1=

q0=1*(0q1)=

█(0(1*(0(λ+0+1)*))@q0=1*)

█(0(1*(0(λ+0+1)*))=1*01*0(λ+0+1)*1*0+1*0(λ+0+1)*(λ+0+1)=1*01*0(λ+0+1)*(λ+0+1)@1*)

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ón inaccesible ya que ningún estado puede llegar a ella, se elimina según las regla de minimización.

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}, identifica el conjunto de estados del autómata

Σ = {1, 0, λ}, es el alfabeto de entrada

“s” es el estado inicial, en nuestro caso {q0}

“F” es un conjunto de estados finales, en nuestro caso {q2}

 : K x ∑ → K es la función de transición, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado.

Identifique el lenguaje que genera.

L= {ω  {1, 0, λ} | 1*0 (0+1)* }

Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia. (No se trata solo de captura las imágenes, estas deben ser explicadas en pié de página o de lo contrario no tienen validez)

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

Diagrama

...