Logic, formal languages, and formal language identification. Some logical properties of the languages in the Chomsky hierarchy, and an interrogative model of formal language identification.

摘要

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;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;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.