Reflection in the Chomsky Hierarchy
| Autor: | Barendregt, H., Capretta, V., Kozen, D.C. |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Zdroj: | Technical Report. Ithaca, NY : Computing and Information Science, Cornell University Technical Report |
| Popis: | The class of regular languages can be generated from the regular expressions. These regular expressions, however, do not themselves form a regular language, as can be seen using the pumping lemma. On the other hand, the class of enumerable languages can be enumerated by a universal language that is one of its elements. We say that the enumerable languages are reflexive. In this paper we investigate what other classes of the Chomsky Hierarchy are reflexive in this sense. To make this precise we require that the decoding function is itself specified by a member of the same class. Could it be that the regular languages are reflexive, by using a different collection of codes? It turns out that this is impossible: the collection of regular languages is not reflexive. Similarly the collections of the context-free, context-sensitive, and computable languages are not reflexive. Therefore the class of enumerable languages is the only reflexive one in the Chomsky Hierarchy. Journal of Automata, Languages and Combinatorics, Volume 18, Number 1, 2013, 53-60 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|