|
|
|
|
|
|
5-1 No natural language, it appears, includes a longest sentence. If this universal feature of natural language corresponds to an innate constraint on children's linguistic hypotheses, then children would be barred from conjecturing a grammar for a finite language. Such a constraint on potential conjectures amounts to a strategy. To formulate it, let us call M nontrivial on a language L just in case for all s such that  , W j ( s )is infinite. M is nontrivial on  just in case M is nontrivial on each  . M is nontrivial just in case M is nontrivial on each  . Define: |
|
|
|
|
|
|
|
|
Clearly, no nontrivial scientist can identify any finite language. In contrast, their behavior on collections of infinite languages is less evident. To explore the matter, show the following. |
|
|
|
|
|
|
|
|
(a) There is  such that (i) every  is infinite, and (ii)  . |
|
|
|
|
|
|
|
|
(b)  |
|
|
|
|
|
|
|
|
(c)  |
|
|
|
|
|
|
|
|
5-2 Show that  . |
|
|
|
|
|
|
|
|
5-3 M is called nonexcessive just in case for all  ,  . [TxtEx]nonexcessive denotes  . Prove: For all  , if  , then  if and only if  . |
|
|
|
|
|
|
|
|
5-4 (J. Canny) M is said to be weakly nontrivial just in case for all infinite  , WM(T[n]) is infinite for all  and all texts T for L. Nontriviality implies weak nontriviality. [TxtEx]weak-nontriv denotes   . Show that for some collection  of infinite languages,  . |
|
|
|
|
