Saltar al contenido ForoHackers

Automata and formal languages: start here

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

Inicia sesión o únete para responder.