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 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 …ver más…

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.
I.4.1 Aceptadores de lenguajes

st......si ....s3s2s1 Canal de entrada

M

Señal de salida

Inicialización

Unidad I: Introducción

3 de 6

Un aceptador de lenguaje recibe de manera secuencial los sí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 sí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.
I.4.2 Generadores de lenguajes.

M

rt......ri.....r3r2r1 Señal de salida

Inicialización

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 símbolos es generada a partir de un conjunto denominado alfabeto de salida. M puede exhibir un comportamiento no determinista,