Saltar al contenido ForoHackers

Autómatas y lenguajes formales: por dónde empezar

Autómatas y lenguajes formales
#898 · Ophuscado · · Denunciar

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

  1. Dibuja un AFD para las cadenas con un número par de ceros y luego codifícalo como una tabla.
  2. Convierte un AFN en AFD con la construcción de subconjuntos y una expresión regular en un AFN.
  3. Usa el lema de bombeo para demostrar que los paréntesis balanceados no son un lenguaje regular.
  4. Escribe una gramática independiente del contexto y un analizador de descenso recursivo para la aritmética.
  5. Sitúa cada clase en la jerarquía de Chomsky y relaciónala con la máquina de Turing.

Etiquetas relacionadas

#computability #compilers #formal-methods #language-design

Inicia sesión o únete para responder.