Introduccion de automatas

Unidad I: Introducción

1 de 6

Teoría de la Computación
I. 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 sistemaexistente 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.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 facetasde 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 limites 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:
La máquina abstractao autómata El lenguaje abstracto

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 recibeuna 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 nodeterminista puede tener varias opciones. Para que la diferencia sea clara veamos los siguientes ejemplos:

Unidad I: Introducción

2 de 6

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 dosopciones, 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 laejecució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, subconjuntossimples 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⊆Σ*...