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 RegularExpression''''''s and right linear grammars.  ''Note that the programming construct commonly referred to by the name RegularExpression''''''s 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