A logical study of formal language identification. The main goal of the dissertation is to develop a new question-answer model of formal language identification which is offered as an alternative to the Chomsky-Gold paradigm of language identification. The new model is an instance of Jaako Hintikka's 'interrogative model of information seeking'. In this model a learner is assumed to learn the axioms of an unknown formal language by putting questions to an information source called 'Oracle'. The basic problem is this: what are the weakest possible questions needed to identify an unknown language, or all languages of a given language class. / A simple first-order language L$\sb{\rm G0}$ is designed, such that this language can be used to speak about any formal language. For the sake of clarity, the languages we want to talk about are called 'target languages'. L$\sb{\rm G0}$ can be used to describe the properties of any first-order language, too. As an interesting special case, L$\sb{\rm G0}$ can be chosen as a target language (of itself). / An algorithm is designed which translates any context-free grammar on a given vocabulary into a set of first-order axioms. / A proof-theoretical analysis of grammaticalness is presented, and it is proved that for any context-free grammar there exists a set of axioms in L$\sb{\rm G0}$ (in a suitable normal form), such that the language of the grammar is exactly the set of strings which can be proved to belong to set specified by the axioms, assuming that the axioms result as an output of the translation algorithm. A study of the quantificational complexity of the axiomatizations of context-free languages is presented, followed by a sematical (model-theoretical) analysis of grammaticalness. / This logical analysis of formal language theory serves the proof of the main theorem which claims that any context-free language can be identified in an interrogative model of formal language identification. / Source: Dissertation Abstracts International, Volume: 49-07, Section: A, page: 1789. / Major Professor: Jaakko Hintikka. / Thesis (Ph.D.)--The Florida State University, 1988.
| Identifer | oai:union.ndltd.org:fsu.edu/oai:fsu.digital.flvc.org:fsu_77797 |
| Contributors | Pylkko, Pauli Olavi., Florida State University |
| Source Sets | Florida State University |
| Language | English |
| Detected Language | English |
| Type | Text |
| Format | 170 p. |
| Rights | On campus use only. |
| Relation | Dissertation Abstracts International |
Page generated in 0.0021 seconds