Los autómatas son pequeñas máquinas abstractas que leen una cadena y la aceptan o la rechazan; los lenguajes formales son los conjuntos de cadenas que aceptan. Juntos clasifican lo complicado que es un patrón y qué tipo de máquina puede reconocerlo. Están debajo de las expresiones regulares, los analizadores léxicos y sintácticos y los verificadores de protocolos.
Conceptos clave
- Autómatas finitos: un número fijo de estados y ninguna otra memoria; reconocen exactamente los lenguajes regulares.
- Expresiones regulares: una notación para esos mismos lenguajes, convertible de y a autómatas.
- Autómatas de pila: un autómata finito con una pila; reconocen los lenguajes independientes del contexto, como los paréntesis anidados.
- Jerarquía de Chomsky: lenguajes regulares, independientes del contexto, sensibles al contexto y recursivamente enumerables, cada uno con una máquina más potente.
- Clausura y bombeo: qué operaciones mantienen un lenguaje en su clase y cómo demostrar que no pertenece a ella.
Vocabulario
- Alfabeto y cadena: los símbolos permitidos y una sucesión finita de ellos.
- AFD y AFN: autómatas finitos deterministas y no deterministas; aceptan los mismos lenguajes.
- Gramática: un conjunto de reglas de reescritura que genera las cadenas de un lenguaje.
- Árbol de análisis: la estructura que una gramática asigna a una cadena.
Qué estudiar, en orden
- Dibuja un AFD para las cadenas con un número par de ceros y luego codifícalo como una tabla.
- Convierte un AFN en AFD con la construcción de subconjuntos y una expresión regular en un AFN.
- Usa el lema de bombeo para demostrar que los paréntesis balanceados no son un lenguaje regular.
- Escribe una gramática independiente del contexto y un analizador de descenso recursivo para la aritmética.
- Sitúa cada clase en la jerarquía de Chomsky y relaciónala con la máquina de Turing.