Plan de estudio clave asignatura nombre de la asignatura



Descargar 194,12 Kb.
Página1/2
Fecha de conversión24.09.2017
Tamaño194,12 Kb.
  1   2


CARRERA

PLAN DE ESTUDIO

CLAVE ASIGNATURA

NOMBRE DE LA ASIGNATURA

Ingeniería en Computación

2003-1

5044

Teoría de la Computación




Práctica No.

LABORATORIO DE

Teoría de la Computación

DURACIÓN

(HORAS)

2


Nombre de la Práctica

Autómatas

2





Elaboró:

Christian Navarro Cota



Revisó:

Odin Isaac Meling López




1.- INTRODUCCIÓN:
Desde su nacimiento, la teoría de autómatas ha encontrado aplicación en muy diversos campos. Esto se debe a que resulta muy natural considerar, que tanto los autómatas como las máquinas secuenciales, son sistemas capaces de transmitir (procesar) información. Lo anterior en definitiva, es comparable con cualquier sistema existente de la naturaleza, que recibe señales de su entorno, reacciona ante ellas y emite así nuevas señales al ambiente que le rodea.
Algunos de los campos donde ha encontrado aplicación la teoría de autómatas son:

  • Teoría de la comunicación.

  • Teoría del control.

  • Lógica de circuitos secuenciales.

  • Reconocimiento de patrones.

  • Fisiología del sistema nervioso.

  • Traducción automática de lenguajes.



2.- OBJETIVO (COMPETENCIA):
El alumno se adentrara a lo que es un lenguaje en teoría de la computación así como conocerá los diferentes tipos de autómatas y como es que estos funcionan.

3.- MARCO TEÓRICO:

I.1. Maquinas de Información
En el pasado, la curiosidad de la mayoría de los hombres intelectuales estaba enfocada hacia la

transformación y la utilización de la energía. Pero con el advenimiento de las computadoras digitales su atención cambio hacia la utilización de la información.


Las máquinas de la información computadoras, teléfonos, etc. han jugado un rol importante en casi todas las facetas de la vida humana. La versatilidad de las computadoras modernas ha suscitado la siguiente pregunta acerca del poder de las máquinas de información actuales:
¿Cuáles, si existen son los límites en las tareas que estas máquinas pueden llevar a cabo?

Para entender las limitaciones de las máquinas de información, analizaremos 2 abstracciones principales de estos dispositivos:





I.2. La máquina abstracta o autómata
Un autómata desde el punto de vista técnico se define como un mecanismo que realiza procesos funciones u operaciones (ej. operaciones tecnológicas, procesos de mando de las industrias, etc.) sin participación directa del hombre.
Un autómata desde el punto de vista computacional puede verse cómo una caja negra que recibe una entrada y produce una salida. El autómata se dice que es finito ya que realiza un número finito de instrucciones y determina la salida, en ese momento el autómata termina su ejecución.
Existen 2 tipos de autómatas finitos: deterministas y no deterministas. La diferencia radica en que el determinista, dada la entrada, en cada paso sólo tiene una opción para continuar, mientras que el no determinista puede tener varias opciones. Para que la diferencia sea clara veamos los siguientes ejemplos:
Ejemplo 1 Determinista: Mireya le dice a Eduardo que va a tirar un volado, si cae sol, entonces ella gana y si cae águila ella pierde.
Ejemplo 2 No Determinista: Ahora Mireya le propone a Eduardo que si cae sol ella gana y si cae águila entonces hay dos opciones, que ella acepte que ha perdido o tira un nuevo volado con las mismas reglas.
Los autómatas son utilizados para modelar una gran variedad de sistemas prácticos que van desde los circuitos digitales, hasta el sistema nervioso humano, sistemas lógicos y funciones recursivas. Basándonos en los equipos actuales, un autómata programable se puede definir como un equipo electrónico el cual realiza la ejecución de un programa en forma cíclica.
I.3. Los lenguajes abstractos.
Un lenguaje abstracto es una colección de sentencias que satisfacen determinadas propiedades o reglas de construcción. Las sentencias son un conjunto finito de símbolos elegidos de un conjunto denominado el

alfabeto del lenguaje (Σ).

Los lenguajes abstractos se utilizan para modelar lenguajes de programación, subconjuntos simples

del lenguaje natural, y la secuencia de operaciones de las máquinas físicas. Un autómata puede ser usado para representar un lenguaje, si se considera la entrada como una cadena de caracteres de Σ .


I.3.1 Especificación de un lenguaje
• Un lenguaje L es un conjunto finito o infinito de cadenas tomadas de algún alfabeto (Σ).

• Si Σ es el conjunto de símbolos posibles, L⊆Σ*

• Un alfabeto Σ es un conjunto finito de símbolos.

• Una cadena es una secuencia de símbolos s=s1s2...sn donde si∈Σ.



• Una cadena nula es aquella que tiene longitud igual a 0.
I.4. Relación entre los lenguajes abstractos y los autómatas
La relación entre los lenguajes abstractos y las máquinas se establece a través del estudio de 3 tipos de autómatas: Aceptadores, generadores y traductores.’

Un aceptador de lenguaje recibe de manera secuencial los mbolos de una cadena de entrada, respondiendo a cada símbolo con una señal binaria (que se muestra en la figura como un foco que cuando esta encendido representa a un 1 y apagado a un 0).

Los símbolos de entrada son elegidos a partir de un conjunto finito de mbolos conocido como el alfabeto de entrada de M. Se supone que M se inicializa en un estado predeterminado. La máquina M divide el conjunto de todas las posibles secuencias de símbolos en 2 clases:


ƒ Clase 1: Aquellas sentencias a las cuales M responde con una señal binaria de 0 (o apagado).

ƒ Clase 2: Aquellas cadenas o sentencias a las que M responde con un 1.


Cuándo se inicializa un generador de lenguaje, este empieza a generar una secuencia de símbolos de salida:

r1r2r3...ri.rt

Esta secuencia de mbolos es generada a partir de un conjunto denominado alfabeto de salida. M puede exhibir un comportamiento no determinista, es decir, generar diferentes secuencias cada vez que se inicializa. El lenguaje generado por M está formado por el conjunto de todas las secuencias diferentes que la máquina M pueda producir.

  1   2


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal