Skip to the content ForoHackers
Log inJoin

Automata and formal languages: start here

Automata and formal languages
#3403 · · Quote · Report

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

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