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:
*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

- 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?.)

EditText of this page (last edited September 22, 2006) or FindPage with title or text search