Por Mark Shead
Una introducción a los conceptos de la informática
La informática nos permite programar, pero es posible hacer mucha programación sin entender los conceptos subyacentes de la informática.
Esto no siempre es algo malo. Cuando programamos, trabajamos a un nivel de abstracción mucho mayor.
Cuando conducimos un coche, sólo nos preocupamos de dos o tres pedales, una palanca de cambios y un volante. Se puede manejar un coche con seguridad sin tener una idea clara de su funcionamiento.
Sin embargo, si se quiere manejar un coche al límite de sus posibilidades, hay que saber mucho más sobre automóviles que los tres pedales, la palanca de cambios y el volante.
Lo mismo ocurre con la programación. Una gran cantidad de trabajo cotidiano puede llevarse a cabo con poca o ninguna comprensión de la informática. No es necesario entender la teoría de la computación para construir un formulario de «Contacto» en PHP.
Sin embargo, si usted planea escribir código que requiere computación seria, tendrá que entender un poco más acerca de cómo funciona la computación bajo el capó.
El propósito de este artículo es proporcionar algunos antecedentes fundamentales para la computación. Si hay interés, puedo seguir con algunos temas más avanzados, pero ahora quiero ver la lógica detrás de uno de los dispositivos computacionales abstractos más simples – una máquina de estado finito.
Máquinas de estado finito
Una máquina de estado finito es una abstracción matemática utilizada para diseñar algoritmos.
En términos más simples, una máquina de estado leerá una serie de entradas. Cuando lee una entrada, cambiará a un estado diferente. Cada estado especifica a qué estado cambiar, para una entrada determinada. Esto parece complicado, pero en realidad es bastante simple.
Imagina un dispositivo que lee un largo trozo de papel. Por cada pulgada de papel hay una sola letra impresa: la letra ‘a’ o la letra ‘b’.
A medida que la máquina de estados lee cada letra, cambia de estado. Aquí tenemos una máquina de estados muy sencilla:
Los círculos son «estados» en los que puede estar la máquina. Las flechas son las transiciones. Así, si está en el estado s y lee una ‘a’, pasará al estado q. Si lee una ‘b’, se quedará en el estado s.
Así que si empezamos en s y leemos la cinta de papel de arriba de izquierda a derecha, leeremos la ‘a’ y pasaremos al estado q.
Entonces, leeremos la ‘b’ y nos moveremos de nuevo al estado s.
Otra ‘b’ nos mantendrá en s, seguida de una ‘a’ – que nos mueve de nuevo al estado q. Bastante simple, pero ¿qué sentido tiene?
Bueno, resulta que puedes pasar una cinta por la máquina de estados y decir algo sobre la secuencia de letras, examinando el estado en el que terminas.
En nuestra sencilla máquina de estados anterior, si terminamos en el estado s, la cinta debe terminar con una letra ‘b’. Si terminamos en el estado q, la cinta termina con la letra ‘a’.
Esto puede parecer inútil, pero hay muchísimos problemas que se pueden resolver con este tipo de enfoque. Un ejemplo muy sencillo sería determinar si una página de HTML contiene estas etiquetas en este orden:
<html> <head> </head> <body> </body> </html>La máquina de estados puede pasar a un estado que muestre que ha leído la etiqueta html, hacer un bucle hasta llegar a la etiqueta head, hacer un bucle hasta llegar a la etiqueta head close, y así sucesivamente.
Si llega con éxito al estado final, entonces tienes esas etiquetas concretas en el orden correcto.
Las máquinas de estados finitos también se pueden utilizar para representar muchos otros sistemas – como la mecánica de un parquímetro, una máquina de refrescos, un surtidor de gasolina automático, y todo tipo de cosas.
Máquinas de estados finitos deterministas
Las máquinas de estados que hemos visto hasta ahora son todas máquinas de estados deterministas. Desde cualquier estado, sólo hay una transición para cualquier entrada permitida. En otras palabras, no puede haber dos caminos que salgan de un estado cuando se lee la letra ‘a’. Al principio, parece una tontería hacer esta distinción.
¿De qué sirve un conjunto de decisiones si la misma entrada puede dar lugar a pasar a más de un estado? No puedes decirle a un ordenador, if x == true entonces ejecuta doSomethingBig o ejecuta doSomethingSmall, puedes?
Bueno, más o menos puedes con una máquina de estados.
La salida de una máquina de estados es su estado final. Pasa por todo su procesamiento, y luego se lee el estado final, y luego se toma una acción. Una máquina de estados no hace nada mientras pasa de un estado a otro.
Procesa, y cuando llega al final, se lee el estado y algo externo desencadena la acción deseada (por ejemplo, dispensar una lata de refresco). Este es un concepto importante cuando se trata de máquinas de estados finitos no deterministas.
Máquinas de estados finitos no deterministas
Las máquinas de estados finitos no deterministas son máquinas de estados finitos en las que una entrada dada de un estado particular puede llevar a más de un estado diferente.
Por ejemplo, digamos que queremos construir una máquina de estados finitos que pueda reconocer cadenas de letras que:
- Comiencen con la letra ‘a’
- y luego sean seguidas por cero o más ocurrencias de la letra ‘b’
- o, cero o más ocurrencias de la letra ‘c’
- se terminen con la siguiente letra del alfabeto.
- abbbbbbbbbc
- abbbc
- acccd
- acccd
- ac (cero ocurrencias de b)
- ad (cero ocurrencias de c)
- ab
- aabb
- aaaaaabbbbbb
- aaaaaaaaaaaabbbbbbbbbbbbbb
Las cadenas válidas serían:
Así que reconocerá la letra ‘a’ seguida de cero o más de la misma letra de ‘b’ o ‘c’ seguido de la siguiente letra del alfabeto.
Una forma muy sencilla de representar esto es con una máquina de estados que se parece a la siguiente, donde un estado final de t significa que la cadena fue aceptada y coincide con el patrón.
¿Ves el problema? Desde el punto de partida s, no sabemos qué camino tomar. Si leemos la letra ‘a’, no sabemos si ir al estado q o al r.
Hay algunas formas de resolver este problema. Una es mediante el backtracking. Simplemente se toman todos los caminos posibles, y se ignoran o se retroceden los que se atascan.
Así es como funcionan básicamente la mayoría de los ordenadores que juegan al ajedrez. Miran todas las posibilidades -y todas las posibilidades de esas posibilidades- y eligen el camino que les da el mayor número de ventajas sobre su oponente.
La otra opción es convertir la máquina no determinista en una máquina determinista.
Uno de los atributos interesantes de una máquina no determinista es que existe un algoritmo para convertir cualquier máquina no determinista en una determinista. Sin embargo, suele ser mucho más complicado.
Por suerte para nosotros, el ejemplo anterior es sólo un poco más complicado. De hecho, éste es lo suficientemente sencillo como para que podamos transformarlo en una máquina determinista en nuestra cabeza, sin la ayuda de un algoritmo formal.
La máquina de abajo es una versión determinista de la máquina no determinista de arriba. En la máquina de abajo, un estado final de t o v es alcanzado por cualquier cadena que sea aceptada por la máquina.
El modelo no determinista tiene cuatro estados y seis transiciones. El modelo determinista tiene seis estados, diez transiciones y dos posibles estados finales.
Eso no es mucho más, pero la complejidad suele crecer exponencialmente. Una máquina no determinista de tamaño moderado puede producir una máquina determinista absolutamente enorme.
Expresiones regulares
Si has hecho algún tipo de programación, probablemente te hayas encontrado con expresiones regulares. Las expresiones regulares y las máquinas de estado finito son funcionalmente equivalentes. Cualquier cosa que puedas aceptar o emparejar con una expresión regular, puede ser aceptada o emparejada con una máquina de estados.
Por ejemplo, el patrón descrito anteriormente podría ser emparejado con la expresión regular: a(b*c|c*d)
Las expresiones regulares y las máquinas de estados finitos también tienen las mismas limitaciones. En concreto, ambas sólo pueden coincidir o aceptar patrones que puedan ser manejados con memoria finita.
Entonces, ¿qué tipo de patrones no pueden coincidir? Digamos que usted quiere sólo coincidir con cadenas de ‘a’ y ‘b’, donde hay un número de ‘a’ seguido de un número igual de ‘b’. O n ‘a’s seguidas de n ‘b’s, donde n es algún número.
Los ejemplos serían:
Al principio, esto parece un trabajo fácil para una máquina de estados finitos. El problema es que rápidamente te quedarás sin estados, o tendrás que asumir un número infinito de estados -en cuyo punto ya no es una máquina de estados finitos.
Digamos que creas una máquina de estados finitos que puede aceptar hasta 20 «a» seguidas de 20 «b». Eso funciona bien, hasta que se obtiene una cadena de 21 ‘a’s seguidas de 21 ‘b’s – en ese momento tendrá que reescribir su máquina para manejar una cadena más larga.
Por cada cadena que pueda reconocer, hay una un poco más larga que su máquina no puede reconocer porque se queda sin memoria.
Esto se conoce como el Lemma del Bombeo, que básicamente dice: «si tu patrón tiene una sección que se puede repetir (como la de arriba), entonces el patrón no es regular».
En otras palabras, no se puede construir ni una expresión regular ni una máquina de estado finito que reconozca todas las cadenas que sí coinciden con el patrón.
Si te fijas bien, te darás cuenta de que este tipo de patrón en el que cada ‘a’ tiene una ‘b’ que coincide, se parece mucho al HTML. Dentro de cualquier par de etiquetas, puedes tener cualquier número de otros pares de etiquetas coincidentes.
Así, mientras que usted puede ser capaz de utilizar una expresión regular o una máquina de estado finito para reconocer si una página de HTML tiene el <html>, <head>; y <body> elementos en el orden correcto, no se puede utilizar una expresión regular para saber si una página HTML entera es válida o no – porque HTML no es un patrón regular.
Máquinas de Turing
Entonces, ¿cómo se reconocen los patrones no regulares?
Hay un dispositivo teórico que es similar a una máquina de estado, llamado Máquina de Turing. Se parece a una máquina de estado finito en que tiene una tira de papel que lee. Pero, una Máquina de Turing puede borrar y escribir en la cinta de papel.
Explicar una Máquina de Turing nos llevaría más espacio del que tenemos aquí, pero hay algunos puntos importantes relevantes para nuestra discusión sobre las máquinas de estado finito y las expresiones regulares.
Las máquinas de Turing son computacionalmente completas – lo que significa que cualquier cosa que se pueda calcular, se puede calcular en una máquina de Turing.
Dado que una máquina de Turing puede escribir y leer de la cinta de papel, no está limitada a un número finito de estados. Se puede suponer que la cinta de papel tiene una longitud infinita. Por supuesto, los ordenadores reales no tienen una cantidad infinita de memoria. Pero, por lo general, contienen suficiente memoria para no llegar al límite para el tipo de problemas que procesan.
Las máquinas de Turing nos dan un dispositivo mecánico imaginario que nos permite visualizar y entender cómo funciona el proceso computacional. Es especialmente útil para entender los límites de la computación. Si hay interés haré otro artículo sobre las Máquinas de Turing en el futuro.
¿Por qué importa esto?
Entonces, ¿qué sentido tiene? Cómo va a ayudarte esto a crear ese próximo formulario PHP?
Independientemente de sus limitaciones, las máquinas de estado son un concepto muy central para la computación. En particular, es significativo que para cualquier máquina de estado no determinista que puedas diseñar, existe una máquina de estado determinista que hace lo mismo.
Este es un punto clave, porque significa que puedes diseñar tu algoritmo de la manera que sea más fácil de pensar. Una vez que tenga un algoritmo de trabajo, puede convertirlo en cualquier forma que sea más eficiente.
La comprensión de que las máquinas de estado finito y las expresiones regulares son funcionalmente equivalentes abre algunos usos increíblemente interesantes para los motores de expresiones regulares – en particular cuando se trata de crear reglas de negocio que se pueden cambiar sin recompilar un sistema.
Una base en Ciencias de la Computación te permite tomar un problema que no sabes cómo resolver y razonar: «No sé cómo resolver X, pero sí sé cómo resolver Y. Y sé cómo convertir una solución para Y en una solución para X. Por lo tanto, ahora sé cómo resolver X.»
Si te gusta este artículo, puede que disfrutes de mi canal de YouTube donde creo un video o una caricatura ocasional sobre algún aspecto de la creación de software. También tengo una lista de correo para las personas que quieran recibir un correo electrónico de vez en cuando cuando produzco algo nuevo.
Publicado originalmente en blog.markshead.com el 11 de febrero de 2018.