Languages

A language is a set of strings over some finite alphabet. To be well-defined, a set requires a membership criterion. Two kinds of membership criteria often used for languages are grammars and automata. Other kinds of criteria are possible, such as regular expressions and recursive functions.

Language types can be arranged according to the complexity required of the membership criterion. The following is the classic Chomsky hierarchy.

Language Grammar Machine Example
Regular language Regular grammar
  • Right-linear grammar
  • Left-linear grammar
Deterministic or nondeterministic finite-state acceptor a*
Context-free language Context-free grammar Nondeterministic pushdown automaton an timesbn times
Context-sensitive language Context-sensitive grammar Linear-bounded automaton an timesbn timescn times
Recursively enumerable language Unrestricted grammar Turing machine Any computable function

If there exists a grammar of a given type for a language L, then L is no more complex than the corresponding language type. It is possible that a simpler (less powerful) grammar exists for the same language.