Saltar al contenido ForoHackers

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

Autómatas y lenguajes formales
#3404 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder