Inicio Noticias Guía de teoría del programador: máquinas de estados finitos

Guía de teoría del programador: máquinas de estados finitos

Página 1 de 3

En muchos sentidos, las máquinas de estados finitos son más importantes que las de Turing, porque en la vida real no hay máquinas de estados infinitos.

Una guía de teoría para programadores

Ahora disponible como libro de bolsillo y libro electrónico de Amazon.

Contenido

¿Qué es?
Parte I ¿Qué se puede calcular?Cual es el calculo? El problema de detener las máquinas de estados finitos
Extracto 1: Máquinas de estado finito *** ¡NUEVO! Números prácticos de gramática, infinito y cálculo.
Extracto 1: Números
Extracto 2: Aleph Zero El primer transfinito
Extracto 3: En busca de Aleph-One
Complejidad y aleatoriedad de Kolmogorov
Extracto 1: Algoritmo de elección de complejidad de Kolmogorov Teorema de incompletitud del cálculo de Gödel Lambda
Parte II Bits, códigos y lógicaTeoría de la información Teoría de la codificación: subdivisión de la lógica booleana para la corrección de errores de bits
Parte III Complejidad Computacional¿Qué tan difícil puede ser?
Extracto 1: ¿De dónde provienen los grandes sistemas operativos de la recursividad?
Extracto 1: ¿Qué es la recursividad?
Extracto 2: ¿Por qué la recursividad NP y los algoritmos P?
Extracto 1: NP y Co-NP
Extracto 2: NP completo


Ya nos hemos encontrado con la máquina de estados finitos como parte de la máquina de Turing (en un capítulo anterior), pero ahora tenemos que considerarla por derecho propio. Existe la sensación de que toda máquina real es una máquina de estados finitos de un tipo u otro, mientras que las máquinas de Turing, aunque teóricamente interesantes, son solo teóricas.

Sabemos que si la tesis de Church-Turing es correcta, las máquinas de Turing pueden realizar cualquier cálculo posible. Sin embargo, este no es el final de la historia, porque podemos aprender mucho sobre la naturaleza de la computación al ver lo que incluso las máquinas más simples pueden hacer. Podemos entender lo difícil que es un cálculo preguntándonos cuál es el mínimo necesario para realizar el cálculo.

Como ya se ha dicho, el tipo más simple de máquina informática se denomina «máquina de estados finitos» y, como tal, ocupa una posición importante en la jerarquía informática.

Una historia terminada

Una máquina de estados finitos consta de un número fijo de estados. Cuando un símbolo, digamos un carácter de un alfabeto, se ingresa en la máquina, cambia de estado de modo que el siguiente estado depende solo del estado actual y del símbolo de entrada.

Tenga en cuenta que esto es más sofisticado de lo que podría pensar porque insertar el mismo símbolo no siempre produce el mismo comportamiento o resultado debido al cambio de estado.

También puede hacer que la máquina emita un carácter como resultado del cambio de estado o puede considerar que cada estado tiene algún tipo de acción asociada.

Esto significa que todo el historial de la máquina se resume en su estado actual. Todas las entradas desde el inicio de la máquina determinan su estado actual y, por lo tanto, el estado actual depende de todo el historial de la máquina. Sin embargo, todo lo que importa para su comportamiento futuro es el estado en el que se encuentra y no cómo ha alcanzado este estado. Esto significa que una máquina de estados finitos puede «olvidar» aspectos de su historia que considere irrelevantes para su futuro.

Antes de descartar la máquina de estados finitos tan débil que no vale la pena considerarla como modelo computacional, conviene señalar que además de poder «olvidar» aspectos irrelevantes de su historia, puede registrar tantos como necesite. Dado que puede tener tantos estados como desee, la máquina puede registrar historias arbitrariamente largas. Suponga que una máquina compleja tiene una serie larga y quizás compleja de historias que determinan lo que hará a continuación. Sigue siendo una máquina de estados finitos porque todo lo que necesita es un estado para cada una de las posibles historias pasadas y la máquina de estados finitos puede responder como la máquina aparentemente compleja. En este caso, el estado en el que se encuentra la máquina es una indicación de su historial pasado completo y, por lo tanto, puede determinar qué sucede a continuación.

Dado que una máquina de estados finitos puede representar cualquier historia y, considerando el cambio de estado como una respuesta a la historia, una reacción, se ha argumentado que es un modelo suficiente de comportamiento humano. A menos que sepa de alguna manera cómo un humano puede tener una historia ilimitada o una memoria ilimitada, esto parece ser una conclusión ineludible: los humanos son máquinas de estados finitos.

Representación de máquinas de estados finitos

Puede representar una máquina de estados finitos en una forma que facilite la comprensión y la reflexión. Todo lo que necesita hacer es dibujar un círculo para cada estado y flechas que muestren qué estado sigue para cada símbolo de entrada. Por ejemplo, la máquina de estados finitos en el siguiente diagrama tiene tres estados. Si la máquina está en el estado 1, una A la mueve al estado 2 y una B la mueve al estado 3.

Esto realmente hace que la máquina de estados finitos sea muy simple y puedes imaginar cómo se le aplican los símbolos como saltos entre estados.

De hecho, se trata de una máquina sencilla, pero su sencillez puede resultar prácticamente útil. Hay algunas aplicaciones que se modelan mejor como una máquina de estados finitos. Por ejemplo, muchos protocolos de comunicación, como USB, pueden definirse mediante un diagrama de máquina de estados finitos que muestra lo que sucede cuando se ingresa información diversa. También puede escribir, u obtener, un compilador que tomará las especificaciones de una máquina de estados finitos y producirá código que se comporte correctamente.

Muchos problemas de programación se resuelven más fácilmente implementando una máquina de estados finitos. Configura una matriz u otra estructura de datos, que almacena los estados posibles e implementa un puntero a la posición que es el estado actual. Cada estado contiene una tabla de búsqueda que muestra cuál es el siguiente estado, dado un símbolo de entrada. Cuando se lee un símbolo, el programa simplemente lo busca en la tabla y mueve el puntero al nuevo estado. Este es un enfoque muy común para organizar juegos.

Marc Gomez
Vine a por tabaco y ya me quedé aquí. Cuando no estoy en el sótano de Tecnopasion suelo pasear por las calles de Barcelona.
RELATED ARTICLES