Saltar al contenido ForoHackers

Automata and formal languages: start here

Autómatas y lenguajes formales
#3403 · · Citar · Denunciar

Automata are small abstract machines that read a string and accept or reject it; formal languages are the sets of strings they accept. Together they classify how complicated a pattern is and what kind of machine can recognise it. They sit under regular expressions, lexers, parsers and protocol checkers.

Key concepts

  • Finite automata: a fixed number of states and no other memory; they recognise exactly the regular languages.
  • Regular expressions: a notation for the same languages, convertible to and from automata.
  • Pushdown automata: a finite automaton with a stack; they recognise context-free languages, such as nested brackets.
  • Chomsky hierarchy: regular, context-free, context-sensitive and recursively enumerable languages, each needing a stronger machine.
  • Closure and pumping: which operations keep a language in its class, and how to prove a language is not in it.

Vocabulary

  • Alphabet and string: the symbols allowed, and a finite sequence of them.
  • DFA and NFA: deterministic and nondeterministic finite automata; they accept the same languages.
  • Grammar: a set of rewriting rules that generates the strings of a language.
  • Parse tree: the structure a grammar assigns to one string.

What to study, in order

  1. Draw a DFA for strings with an even number of zeros, then code it as a table.
  2. Convert an NFA to a DFA by the subset construction and a regular expression to an NFA.
  3. Use the pumping lemma to prove that balanced brackets are not regular.
  4. Write a context-free grammar and a recursive-descent parser for arithmetic.
  5. Place each class on the Chomsky hierarchy and link it to the Turing machine.

Related tags

#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