|
|
|
|
|
|
4-7 (Angluin [6]) Most practical classes of languages are uniformly decidable. A sequence of nonempty languages L0, L1, . . . is an indexed family just in case there exists a computable function f such that for each  and for each  , |
|
|
|
|
|
|
|
|
In other words, there is a uniform decision procedure for languages in the class. The purpose of this and the next two exercises is to explore the identifiability of indexed families of computable languages. In this exercise we establish Angluin's characterization (described in Theorem 3.26) for an indexed family of computable languages. To this end, we define a finite tell-tale set. |
|
|
|
|
|
|
|
|
Let  be an indexed family of computable languages. A is a finite tell-tale of Li just in case A is a finite subset of Li and there is no j such that  . |
|
|
|
|
|
|
|
|
Show that an indexed family of computable languages  belongs to TxtEx just in case there is a procedure, effective in i, that enumerates all elements in a finite tell-tale of Li. |
|
|
|
|
|
|
|
|
There has been considerable work on identification of several natural indexed families of computable languages, e.g., subclasses of elementary formal systems, of logic programming languages, and of formal languages in the Chomsky hierarchy. For results on elementary formal systems, we refer the reader to the papers of Arikawa, Miyano, Ayumi Shinohara, Takeshi Shinohara, and Yamamoto [9, 8, 175]. Sample results about identification of logic programming languages can be found in Arimura and Shinohara [10] and Krishna Rao [112]. Yokomori [205] contains results about identification of languages accepted by a class of deterministic automata. See Sakakibara [165] for a survey of related results about grammatical inference. |
|
|
|
|
|
|
|
|
4-8 (Angluin [5]) A collection of languages  has finite thickness just in case for each  , is finite. |
|
|
|
|
|
|
|
|
Show that if an indexed family of computable languages  has finite thickness, then  . |
|
|
|
|
|
|
|
|
4-9 (Wright [204], see also Motoki, Shinohara, and Wright [133]) A collection of languages  has infinite elasticity just in case there exists an infinite sequence of pairwise distinct numbers,  , and an infinite sequence of pairwise |
|
|
|
|
