Skip to the content ForoHackers
Log inJoin

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

Automata and formal languages
#3404 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply