Ufff, ese 'tutorial', es francamente malo... Me recuerda ciertos libros y artículos de revistas, en esa misma línea. Ese tipo de tutorial donde te explican como si fueras idiota, "pulsa aquí, escribe esto, haz lo otro...", no enseñan absolutamente nada.
Un autómata o máquina de estados, es un modelo matemático que se compone de un alfabeto, una serie de estados, una función de transición, un conjunto de reglas, un estado inicial y un estado final.
- El alfabeto determina los elementos que puede contener.
- El estado inicial, es el modo exacto en que está el autómata al comienzo. Por lo general queda definido por un valor a la entrada.
- El estado final, es el modo exacto en que está el autómata al final. Por lo general sólo es de interés el valor de salida. O dicho de otra forma, cada valor de interés a la salida es devuelto. Es común que sea un único valor.
- Los estados, son los valores entre los que puede evolucionar internamente el autómata.
- La función de transición, determina que valor de estado se toma internamente ante las eventualidades presentes. Esta función generalmente describe en código o se compone de condiciones que examinan el estado actual y la situación en un momento concreto, para decidir el siguiente estado. Suele resumirse en una tabla de estados, que refleja fielmente qué sucede en cada caso.
- El conjunto de reglas es lo que diferencia una función de transición respecto de otra. Las reglas se pueden reflejar en un esquema o bien en una tabla.
Como podrás ver, en el 'tutorial' aludido, no se menciona prácticamente nada de todo esto, ni mucho menos aclara qué sucede y por qué...
Existen los autómatas finitos e infinitos, pero en la práctica, sólo podemos operar y llevar a término, los finitos (los infinitos pueden requerir memoria infinita o tiempo de cálculo infinito y no disponemos ni de uno ni de lo otro...).
Los finitos tienen básicamente dos aplicaciones: autómatas reconocedores, aceptadores (comúnmente llamados scanners), o traductores. Estos últimos transforman un valor de entrada en uno de salida, los otros suelen limitarse a 'decir', ok, está bien, o no, está mal... Pero no es infrecuente utilizar un rango mayor de posibilidades que sólo 2.
- Un ejemplo de los reconocedores, es por ejemplo la fase de análisis del código fuente de un lenguaje de programación para determinar si el texto recibido pertenece o no a dicho lenguaje... en realidad, ahí hay más de 1 autómata, por ejemplo uno determina si una secuencia de caracteres es o no un número.
- Un ejemplo de los traductores, ahondando en el mismo caso, es utilizado cuando por ejemplo el texto del código se pasa desde el lenguaje en que se programó a ensamblador o a código máquina, o a código intermedio durante el proceso de compilación...
En mi opinión harías más avances si usarás de ejemplo el reconocimiento de un token numérico. Más útil y más didáctico, además es un ejemplo donde puedes usar tu mente (pensar, no meramente leer y escribir).
Ejemplo
--—------—---—------—----—-----
digito = 0|1|2|3|4|5|6|7|8|9
sepDecimal = '
digitos = digito [digitos]
numero = digitos [sepDecimal digitos]
Así el alfabeto lo componen cada digito (0 a 9) y el separador decimal '
Las reglas se condensan en las 4 líneas que describen digito, digitos, sepDecimal y numero.
El estado inicial es 0. digito tiene estado 1, cuando se transita de un digito a otro, el estado cambia a 1, es decir no cambia. Si aparece un separador decimal tras un digito transita al estado 2, si tras el separador aparece un digito transita al estado 3. Pero si aparece otro separador tras el separador , transita al estado 4. Y si aparece un carácter que no pertenece al alfabeto transita al estado 5.
Si alcanza un estado 3, si aparece otro digito transita a estado 3, es decir no cambia. Y si aparece un nuevo separador transita al estado 4.
En resumen, empieza en estado 0, la función continua analizando mientras queden caracteres y el estado sea menor o igual a 3. La aparición de un carácter no definido en el alfabeto transita al estado 5.
Los estados finales, pueden ser 0, 1,2,3,4 o 5. Pero los estados de aceptación sólo son 1 y 3. Es decir la función reconocerá el token 'numero', si se devuelve el estado 1, o 3... O directamente resumido un valor TRUE (if estado =1) or (estado=3) devolver TRUE.
Si decides abordarlo, y muestras algún progreso (escribir por escribir, si no hay interés, paso) podría mostrarte el esquema, la tabla de estados y el flujo de la función... Que te servirían de excelente ejemplo para aprender...
Un autómata o máquina de estados, es un modelo matemático que se compone de un alfabeto, una serie de estados, una función de transición, un conjunto de reglas, un estado inicial y un estado final.
- El alfabeto determina los elementos que puede contener.
- El estado inicial, es el modo exacto en que está el autómata al comienzo. Por lo general queda definido por un valor a la entrada.
- El estado final, es el modo exacto en que está el autómata al final. Por lo general sólo es de interés el valor de salida. O dicho de otra forma, cada valor de interés a la salida es devuelto. Es común que sea un único valor.
- Los estados, son los valores entre los que puede evolucionar internamente el autómata.
- La función de transición, determina que valor de estado se toma internamente ante las eventualidades presentes. Esta función generalmente describe en código o se compone de condiciones que examinan el estado actual y la situación en un momento concreto, para decidir el siguiente estado. Suele resumirse en una tabla de estados, que refleja fielmente qué sucede en cada caso.
- El conjunto de reglas es lo que diferencia una función de transición respecto de otra. Las reglas se pueden reflejar en un esquema o bien en una tabla.
Como podrás ver, en el 'tutorial' aludido, no se menciona prácticamente nada de todo esto, ni mucho menos aclara qué sucede y por qué...
Existen los autómatas finitos e infinitos, pero en la práctica, sólo podemos operar y llevar a término, los finitos (los infinitos pueden requerir memoria infinita o tiempo de cálculo infinito y no disponemos ni de uno ni de lo otro...).
Los finitos tienen básicamente dos aplicaciones: autómatas reconocedores, aceptadores (comúnmente llamados scanners), o traductores. Estos últimos transforman un valor de entrada en uno de salida, los otros suelen limitarse a 'decir', ok, está bien, o no, está mal... Pero no es infrecuente utilizar un rango mayor de posibilidades que sólo 2.
- Un ejemplo de los reconocedores, es por ejemplo la fase de análisis del código fuente de un lenguaje de programación para determinar si el texto recibido pertenece o no a dicho lenguaje... en realidad, ahí hay más de 1 autómata, por ejemplo uno determina si una secuencia de caracteres es o no un número.
- Un ejemplo de los traductores, ahondando en el mismo caso, es utilizado cuando por ejemplo el texto del código se pasa desde el lenguaje en que se programó a ensamblador o a código máquina, o a código intermedio durante el proceso de compilación...
En mi opinión harías más avances si usarás de ejemplo el reconocimiento de un token numérico. Más útil y más didáctico, además es un ejemplo donde puedes usar tu mente (pensar, no meramente leer y escribir).
Ejemplo
--—------—---—------—----—-----
digito = 0|1|2|3|4|5|6|7|8|9
sepDecimal = '
digitos = digito [digitos]
numero = digitos [sepDecimal digitos]
Así el alfabeto lo componen cada digito (0 a 9) y el separador decimal '
Las reglas se condensan en las 4 líneas que describen digito, digitos, sepDecimal y numero.
El estado inicial es 0. digito tiene estado 1, cuando se transita de un digito a otro, el estado cambia a 1, es decir no cambia. Si aparece un separador decimal tras un digito transita al estado 2, si tras el separador aparece un digito transita al estado 3. Pero si aparece otro separador tras el separador , transita al estado 4. Y si aparece un carácter que no pertenece al alfabeto transita al estado 5.
Si alcanza un estado 3, si aparece otro digito transita a estado 3, es decir no cambia. Y si aparece un nuevo separador transita al estado 4.
En resumen, empieza en estado 0, la función continua analizando mientras queden caracteres y el estado sea menor o igual a 3. La aparición de un carácter no definido en el alfabeto transita al estado 5.
Los estados finales, pueden ser 0, 1,2,3,4 o 5. Pero los estados de aceptación sólo son 1 y 3. Es decir la función reconocerá el token 'numero', si se devuelve el estado 1, o 3... O directamente resumido un valor TRUE (if estado =1) or (estado=3) devolver TRUE.
Si decides abordarlo, y muestras algún progreso (escribir por escribir, si no hay interés, paso) podría mostrarte el esquema, la tabla de estados y el flujo de la función... Que te servirían de excelente ejemplo para aprender...
