Introducción a los conceptos de informática
La informática nos permite programar, pero es posible realizar mucha programación sin comprender los conceptos subyacentes de la informática.
Esto no siempre es malo. Cuando programamos, trabajamos a un nivel mucho más alto de abstracción.
Cuando conducimos, solo nos preocupamos por dos o tres pedales, una palanca de cambios y un volante. Puede operar un automóvil de manera segura sin tener una idea clara de cómo funciona.
Sin embargo, si desea operar un automóvil al límite de sus capacidades, necesita saber mucho más sobre automóviles que solo los tres pedales, la palanca de cambios y el volante.
Lo mismo ocurre con la programación. Gran parte del trabajo diario se puede realizar con poca o ninguna comprensión de la informática. No es necesario comprender la teoría computacional para crear un formulario de "Contáctenos" en PHP.
Sin embargo, si planea escribir código que requiera una computación seria, necesitará comprender un poco más sobre 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 continuar con algunos temas más avanzados, pero ahora mismo quiero ver la lógica detrás de uno de los dispositivos computacionales abstractos más simples: una máquina de estados finitos .
Máquinas de estado finito
Una máquina de estados finitos es una abstracción matemática utilizada para diseñar algoritmos.
En términos más simples, una máquina de estados 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 suena complicado pero en realidad es bastante simple.
Imagínese un dispositivo que lee una hoja de papel larga. Por cada pulgada de papel hay una sola letra impresa en él, ya sea la letra 'a' o la letra 'b'.
A medida que la máquina de estado lee cada letra, cambia de estado. Aquí hay una máquina de estado muy simple:
Los círculos son " estados " en los que la máquina puede estar. Las flechas son las transiciones . Entonces, si está en el estado sy lee una 'a', pasará al estado q . Si lee una 'b', permanecerá en el estado s .
Entonces, si comenzamos en sy leemos la cinta de papel de arriba de izquierda a derecha, leeremos la 'a' y pasaremos al estado q .
Luego, leeremos 'b' y regresaremos al estado s .
Otra 'b' nos mantendrá en s , seguida de una 'a', que nos lleva de regreso al estado q . Bastante simple, pero ¿cuál es el punto?
Bueno, resulta que puedes pasar una cinta a través de la máquina de estado y decir algo sobre la secuencia de letras, examinando el estado en el que terminas.
En nuestra máquina de estado simple 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 una gran cantidad de problemas que se pueden resolver con este tipo de enfoque. Un ejemplo muy simple sería determinar si una página de HTML contiene estas etiquetas en este orden:
La máquina de estado puede moverse a un estado que muestre que ha leído la etiqueta html, hacer un bucle hasta que llega a la etiqueta de la cabeza, hacer un bucle hasta que llega a la etiqueta de cierre de la cabeza, etc.
Si llega con éxito al estado final, entonces tiene esas etiquetas particulares en el orden correcto.
Las máquinas de estado finito también se pueden usar para representar muchos otros sistemas, como la mecánica de un parquímetro, una máquina de pop, una bomba de gas automatizada y todo tipo de otras cosas.
Máquinas deterministas de estados finitos
Las máquinas de estado que hemos visto hasta ahora son todas máquinas de estado deterministas . Desde cualquier estado, solo hay una transición para cualquier entrada permitida. En otras palabras, no puede haber dos caminos que salgan de un estado cuando lee la letra 'a'. Al principio, parece una tontería incluso hacer esta distinción.
¿De qué sirve un conjunto de decisiones si la misma entrada puede resultar en pasar a más de un estado? No se puede decirle a una computadora y if x == trueluego ejecutar doSomethingBigo ejecutar doSomethingSmall, ¿verdad?
Bueno, puedes hacerlo con una máquina de estado.
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 se mueve de un estado a otro.
Se 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 donde una entrada dada de un estado particular puede conducir 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:
- Empiece con la letra 'a'
- y luego son seguidos por cero o más ocurrencias de la letra 'b'
- o cero o más apariciones de la letra 'c'
- terminan con la siguiente letra del alfabeto.
Las cadenas válidas serían:
- abbbbbbbbbc
- abbbc
- acccd
- acccccd
- ac (cero apariciones de b)
- ad (cero apariciones de c)
Entonces reconocerá la letra 'a' seguida de cero o más de la misma letra de 'b' o 'c', seguida de la siguiente letra del alfabeto.
Una forma muy simple de representar esto es con una máquina de estado que se parece a la que se muestra a continuación, 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 pasar al estado q o r.
Hay algunas formas de resolver este problema. Uno es retroceder. Simplemente tome todos los caminos posibles e ignore o retroceda en aquellos en los que se atasca.
Así es básicamente como funcionan la mayoría de las computadoras para jugar al ajedrez. Miran todas las posibilidades - y todas las posibilidades de esas posibilidades - y eligen el camino que les da la mayor cantidad 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 determinista. Sin embargo, suele ser mucho más complicado.
Afortunadamente para nosotros, el ejemplo anterior es solo un poco más complicado. De hecho, este es lo suficientemente simple como para 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 por debajo de, 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 generalmente crece exponencialmente. Una máquina no determinista de tamaño moderado puede producir una máquina determinista absolutamente enorme .
Expresiones regulares
Si ha realizado algún tipo de programación, probablemente se haya encontrado con expresiones regulares. Las expresiones regulares y las máquinas de estados finitos son funcionalmente equivalentes. Todo lo que pueda aceptar o hacer coincidir con una expresión regular, puede aceptarse o combinarse con una máquina de estado.
Por ejemplo, el patrón descrito anteriormente podría coincidir 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 particular, ambos solo pueden coincidir o aceptar patrones que se pueden manejar con memoria finita.
Entonces, ¿qué tipo de patrones no pueden coincidir? Digamos que solo desea hacer coincidir cadenas de 'a' y 'b', donde hay un número de 'a' seguidos por un número igual de 'b'. O n 'a's seguidas de n ' b's, donde n es un número.
Ejemplos serían:
- ab
- aabb
- aaaaaabbbbbb
- aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb
Al principio, esto parece un trabajo fácil para una máquina de estados finitos. El problema es que rápidamente se quedarán sin estados, o tendrá que asumir un número infinito de estados, en cuyo punto ya no es una máquina de estados finitos .
Digamos que crea una máquina de estados finitos que puede aceptar hasta 20 'a's seguidas de 20' b's. Eso funciona bien, hasta que obtenga una cadena de 21 'a's seguida de 21' b's, momento en el que deberá volver a escribir su máquina para manejar una cadena más larga.
Para cualquier 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 Lema de Bombeo, que básicamente dice: “si su patrón tiene una sección que se puede repetir (como la que se muestra arriba), entonces el patrón no es regular”.
En otras palabras, ni una expresión regular ni una máquina de estados finitos se pueden construir que reconocerá todas las cadenas que no coinciden con el patrón.
Si observa con atención, notará que este tipo de patrón en el que cada 'a' tiene una 'b' coincidente, se parece mucho al HTML. Dentro de cualquier par de etiquetas, puede tener cualquier número de otros pares de etiquetas coincidentes.
Por lo tanto, si bien puede usar una expresión regular o una máquina de estados finitos para reconocer si una página de HTML tiene ; y los elementos en el orden correcto, no puede usar una expresión regular para saber si una página HTML completa es válida o no, porque HTML no es un patrón regular.
>,
Máquinas de Turing
Entonces, ¿cómo reconoces los patrones no regulares ?
Existe un dispositivo teórico que es similar a una máquina de estados, llamado Máquina de Turing. Es similar a una máquina de estados finitos 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 ocupará más espacio del que tenemos aquí, pero hay algunos puntos importantes relevantes para nuestra discusión sobre las máquinas de estados finitos 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 se limita a un número finito de estados. Se puede suponer que la cinta de papel tiene una longitud infinita. Por supuesto, las computadoras reales no tienen una cantidad infinita de memoria. Pero, por lo general, contienen suficiente memoria para que no llegue al límite del tipo de problemas que procesan.
Las Máquinas de Turing nos brindan un dispositivo mecánico imaginario que nos permite visualizar y comprender cómo funciona el proceso computacional. Es particularmente útil para comprender los límites de la computación. Si hay interés, escribiré otro artículo sobre las máquinas de Turing en el futuro.
¿Por qué importa esto?
¿Entonces cuál es el punto? ¿Cómo te ayudará esto a crear el próximo formulario PHP?
Independientemente de sus limitaciones, las máquinas de estado son un concepto muy central para la informática. En particular, es significativo que para cualquier máquina de estados no determinista que pueda diseñar, existe una máquina de estados determinista que hace lo mismo.
Este es un punto clave, porque significa que puede diseñar su 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 estados finitos y las expresiones regulares son funcionalmente equivalentes abre algunos usos increíblemente interesantes para los motores de expresiones regulares, particularmente cuando se trata de crear reglas comerciales que se pueden cambiar sin volver a compilar 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 le gusta este artículo, puede disfrutar de mi canal de YouTube donde creo un video o caricatura ocasional sobre algún aspecto de la creación de software. También tengo una lista de correo para personas a las que les gustaría recibir un correo electrónico ocasional cuando produzco algo nuevo.
Publicado originalmente en blog.markshead.com el 11 de febrero de 2018.