Apunte Te rico 2

UNIDAD TEMÁTICA II - AUTÓMATAS FINITOS Y LENGUAJES REGULARES
♦ MÁQUINAS O AUTÓMATAS DE ESTADOS FINITOS
 

Es el autómata más simple. La teoría subyacente detrás de estas máquinas es bien conocida y
entendida. Se las ha estudiado en diseño de computadoras, neurofisiología, comunicaciones, lingüística, y
teoría de computación. La máquina de estados finitos surgió naturalmente del modelado deaquellos
dispositivos físicos simples que procesan señales que denotan información.
La mayoría de los dispositivos complejos, sean computadoras, máquinas o sistemas de comunicación,
son realizados mediante la interconexión de varios componentes simples. Pero, solamente un número finito
de componentes físicos pueden ser encerrados en un volumen dado. Los "símbolos" empleados para
indicar eventos entrecomponentes son a menudo representados por los valores de cantidades físicas tales
como posiciones mecánicas, voltajes, corrientes, temperaturas, presiones, flujo de fluidos o composiciones
químicas. Dado que ninguna señal puede ser medida con gran exactitud dentro de tolerancias
arbitrariamente pequeñas, los diseñadores de dispositivos físicos se limitan a un número reducido de valores
fácilmentedistinguibles, tanto en el caso de las señales propiamente dichas como en el de las condiciones
internas (estados) de los dispositivos. Resumiendo, podemos decir que la realidad física impone una
ineludible "finitud" en los sistemas físicos.
Una dada señal o estado requiere de un intervalo pequeño (pero no nulo) para su medida. Luego, sólo un
número finito de operaciones puede ser efectuadoconfiablemente en una cantidad de tiempo finita.
Nuevamente, la realidad física impone "discretitud" en los sistemas, no sólo en los símbolos que ellos
pueden procesar, o en los estados que ellos pueden asumir, sino también en los tiempos en los cuales
ellos pueden cambiar de estado.
Nuestra tendencia natural a descomponer la solución de un problema en una secuencia de etapas se
manifiesta en nuestromodelo de máquina simple mediante acciones secuenciales.
Por cierto, al diseñar una máquina que opera efectuando una etapa por vez se emplea la forma más
simple conocida de hacer que su comportamiento sea determinístico, es decir, no sujeto a incertidumbre.
Ej.: Qué valor tiene un número telefónico que no nos permite alcanzar el mismo lugar cada vez que es
discado? Qué valor tiene una instrucciónperteneciente a un lenguaje de programación que nos entrega
un valor distinto cada vez que es empleada?
Luego, el modelo de autómata de estados finitos tiene las siguientes CARACTERÍSTICAS:

En virtud de estas características, el modelo de autómatas de estado finito puede ser (y ha sido) aplicado
a los siguientes casos:
1.- Sistemas mecánicos: (Por ej., máquinas sumadoras) en los cuales las señalesentre los componentes
son representadas por las posiciones de las partes móviles.
2.- Sistemas electrónicos digitales: (Por ej., circuitos lógicos de computadoras) en los cuales las señales son
representadas por voltajes "altos" o "bajos", o por la "presencia" o "ausencia" de corriente.
3.- Sistemas hidráulicos y neumáticos: (Por ej., redes de cañerías y válvulas que son actuadas por deltas depresión) en los cuales las señales se representan por la presencia o ausencia de presión en una cañería.
4.- Sistemas químicos: (Por ej., transmisión del código genético durante la reproducción celular) en los
cuales las señales son representadas por la composición química de ciertos materiales.
Las máquinas de estado finito también son útiles para el modelado de sistemas físicos que presentancombinaciones de estos efectos. Por ej., redes de conmutación de circuitos (donde hay presente una acción
electromecánica) o el sistema nervioso humano (acción electroquímica).
A pesar de sus fuertes raíces en el modelado de fenómenos físicos, la máquina de estado finito no se
limita al modelado de sistemas físicos. Se aplica a procedimientos de procesamiento de información, tales
como la codificación...