Estoy pensando en hacer una presentación para estudiantes de escuela intermedia, a la edad de diez a catorce años, acerca de los autómatas finitos y regulares de idiomas.
Promedio de los estudiantes Estadounidenses no tienen ningún problema con los usos de los conceptos de estados y transiciones, tales como el modelado de las actividades del mundo real y el diseño de dispositivos electrónicos.
Regular los idiomas (y expresiones regulares) son un poco más avanzados. Estos estudiantes son ciertamente capaces de manipular y utilizar, pero un cierto nivel de alfabetización informática es necesaria para ver su utilidad, por ejemplo en la búsqueda a través de texto.
Vamos a suponer que los estudiantes pueden lidiar con todo eso. El significado teórico de la equivalencia en el poder de los dos modelos aún parece un poco fuera de su alcance. Así que estoy buscando una manera de conectar los dos que serán accesibles.
La dificultad es que para los ejemplos canónicos, los dos modelos de participación de independientes preocupaciones.
Ejemplos de autómatas finitos incluyen el control de una máquina con un conjunto finito de entradas, como una máquina expendedora con monedas y botones. Excelente la participación del estudiante actividades en MathmaniaCS (UIUC) y CS Unplugged (buscar en todos ellos, pero estos son sólo acerca de FSMs).
Ejemplos de expresiones regulares incluyen describiendo las palabras de un idioma, como la búsqueda de patrones en un texto. Para un autómata finito, el objetivo es averiguar qué secuencias finitas de las acciones de llegar a un estado determinado, por ejemplo, qué combinaciones de cambio de obtener la cantidad correcta. Para una expresión regular, el objetivo es para que coincida con un patrón, normalmente infinito en posibilidades. La correspondiente expresión regular para la pregunta interesante en un autómatas finitos configuración es realmente muy interesante.
Por ejemplo, una máquina de estados finitos actividad que es divertido es una caza del tesoro, pasando de isla en isla (los estados) con un código secreto (la transición). Sin embargo, el lenguaje del código para obtener el tesoro es aburrido: una sola palabra en el idioma.
Para un interesante lenguaje de la pregunta en autómatas finitos, uno quisiera preguntar para no trivial de la expresión regular que es la descripción de un no-trivial solución a algunos de ruta de acceso en el autómata finito.
Mi pregunta es (por fin): ¿qué es un buen ejemplo de un no-trivial de la expresión regular que, para algunos autómata finito (esperemos que con las conexiones al mundo real), que se mete de un estado a otro?
