A hierarchy of languages in terms of the power of the machine needed to recognize (parse) them and the complexity of the grammar that describes them:
- Type 3: recognized by FiniteStateAutomaton, Described by RegularExpressions and right linear grammars. Note that the programming construct commonly referred to by the name RegularExpressions are not equivalent to a true RegularExpression; the construct that came out of various Unix tools (sed, etc.) and is now commonplace in PerlLanguage and other programming languages, can handle many grammars which are Type 2 and Type 1.
- Type 2: Context Free recognized by PushDownAutomaton (that is, an non-deterministic FiniteStateAutomaton with a stack), described by BackusNaurForm type grammars. There are many sub-categories of Type 2 grammars; a non-deterministic PushDownAutomaton is more powerful than (that is, can recognize more languages than) a deterministic PushDownAutomaton. On the other hand, a non-deterministic FiniteStateAutomaton is not more powerful than a deterministic FiniteStateAutomaton; nor is a non-deterministic TuringMachine more powerful than a deterministic TuringMachine.
- Type 1: Context-sensitive recognized by linear bound TuringMachine, described by grammars that include the context in the LeftHandSide of the definitions
- Type 0: Recursively enumerable, that needs a TuringMachine, described by really horrible grammars:-( /Ahem: These are described by a PhraseStructureGrammar.)
And there are languages which are are not RecursivelyEnumerable; there is no computational model (which we can build or approximate) which can recognize such a language. Also, if a set is not denumerable, can it fall under the definition of a language?
See also NoamChomsky