Un torno que solo sabe dos cosas
Un autómata finito es una máquina con pocos estados que lee un texto símbolo a símbolo y decide si lo acepta. Sirve para comprobar si un texto tiene el formato correcto.
El torno del metro es el ejemplo más cercano. Está cerrado o abierto. Una moneda lo abre y un empujón lo cierra. No recuerda cuántas personas pasaron, solo en qué estado está ahora.
Al final de esta lección
Nota
Puedo seguir un autómata finito paso a paso y decir qué textos acepta.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Estado | la situación en la que está la máquina ahora | abierto |
| Alfabeto | los símbolos que la máquina sabe leer | 0 y 1 |
| Transición | el paso de un estado a otro al leer un símbolo | |
| Estado inicial | el estado en el que empieza siempre | |
| Estado de aceptación | un estado que significa sí al acabar el texto | |
| Autómata finito | una máquina con un número fijo de estados |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un autómata tiene estados y transiciones
Un autómata finito empieza en su estado inicial. Lee el primer símbolo del texto y sigue la transición que corresponde. Así llega a otro estado, o se queda en el mismo.
Cuando el texto se acaba, mira dónde está. Si es un estado de aceptación, acepta el texto. Si no, lo rechaza.
Ejecuta el autómata en Python
# Un autómata que cuenta los unos: ¿pares o impares?
tabla = {
"par": {"0": "par", "1": "impar"},
"impar": {"0": "impar", "1": "par"},
}
estado = "par"
texto = "1011"
for simbolo in texto:
estado = tabla[estado][simbolo]
print(simbolo, "->", estado)
print("Acepta" if estado == "par" else "Rechaza")
# Cambia texto por "0110" y vuelve a ejecutar.
Una tabla de transiciones describe el autómata
Un dibujo con círculos y flechas es fácil de mirar. Una tabla de transiciones dice lo mismo y se puede escribir en un programa.
Cada fila es un estado. Cada columna es un símbolo. La casilla dice a qué estado se pasa. En Python, un diccionario de diccionarios hace de tabla: tabla[estado][simbolo].
Ejemplo: seguir el texto 1011
| Paso | Estado antes | Símbolo | Estado después |
|---|---|---|---|
| 1 | par | 1 | impar |
| 2 | impar | 0 | impar |
| 3 | impar | 1 | par |
| 4 | par | 1 | impar |
| Fin | impar | no hay más texto | No es de aceptación: rechaza |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
grep escribe un autómata en una línea
Las herramientas del laboratorio usan autómatas por dentro. grep -E convierte un patrón en un autómata y lo pasa por cada línea. Los Runs de abajo cuentan unos con la orden tr y con grep, sin que tengas que dibujar nada.
El patrón ^0*(10*10*)*$ acepta los textos con un número par de unos. Léelo como: ceros, y después grupos con dos unos.
Las líneas con unos pares
printf '0110\n1011\n11\n000\n' | grep -E '^0*(10*10*)*$'Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Cuenta los unos de 0110
printf 0110 | tr -d 0 | wc -cSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
La paridad de 13 en binario
python3 -c "print(bin(13).count('1') % 2)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que el autómata recuerda el texto que ya leyó. No lo recuerda. Solo guarda el estado en el que está. Por eso un autómata finito puede decir si hay un número par de unos, pero no contar hasta cualquier número.
Para ir más lejos
Diseña en papel un autómata que acepte los textos binarios que acaban en 0. Necesitas solo dos estados.
Escribe después tres textos que acepta y tres que rechaza, y pruébalos con accepts. ¿Qué cambia si el texto vacío debe ser aceptado?