Developments of LearningAlgorithms for Deterministic Context-Free Languages in Some Classes and Their Applications

机器学习是实现人工智能的重要研究领域之一，而计算学习理论是用数学方法分析机器学习可能性的一种范式。在形式语言理论中，确定性上下文无关语言类在实际应用中很重要。本文研究了确定性下推自动机（dpda）的一些子类，这些子类接受确定性上下文无关语言和相应的形式语法子类。本研究的目的是为dpda的子类开发学习算法，并将这些算法应用于实际问题。我们的研究结果如下：1。开发学习算法的基础：我们提出了一种简单而直接的算法，用于检查某对非实时确定性下推换能器（简称dpdt）的等效性，其中dpdt通过将输出函数附加到dpda来获得。此外，我们还给出了一种多项式时间算法来检验实时严格确定性限制单计数器传感器的等价性，这是一种只有一个堆栈符号的实时dpdt。我们知道等价性检查算法在自动机和形式语法的学习系统中起着重要的作用。这些结果可用于通过查询dpdt的某些子类进行学习。学习算法的发展：我们提出了一种基于一类语言和一类字符串的有限子集所定义的扩展类在正数据极限下的统一识别算法。进一步证明了dpda的一个子类Szilard严格确定性限制单计数器自动机和有限状态传感器的一个子类在正数据的极限上是多项式时间可识别的。

The machine learning is one of the most important research fields for the realization of the artificial intelligence, and the computational learning theory is a paradigm which analyzes mathematically about the possibility for the machine learning. In formal language theory, the class of deterministic context-free languages is important in practical use. In this research, we are concerned with some subclasses of deterministic pushdown automata (dpda's for short) which accept deterministic context-free languages and the corresponding subclasses of formal grammars. The aim of this research is to develop learning algorithms for subclasses of dpda's and to apply these algorithms to practical problems.We had the following research results.1. Basics to develop learning algorithms: We have proposed a simple and direct algorithm for checking the equivalence of a certain pair of non-real-time deterministic pushdown transducers (dpdt's for short), where dpdt's are obtained by attaching the output function to dpda's. In addition, we have given a polynomial-time algorithm for checking the equivalence of real-time strict deterministic restricted one-counter transducers, which are real-time dpdt's that have just one stack symbol. We know that the equivalence checking algorithm plays an important role in learning systems which are formulated as automata and formal grammars. These results can be used for learning via queries for some subclasses of dpdt's.2. Developments of learning algorithms: We have presented a unified identification algorithm in the limit from positive data for the extended class defined by a class of languages to be based on and a class of finite subsets of strings. Furthermore, we have proved that a subclass of dpda's called Szilard strict deterministic restricted one-counter automata and a certain subclass of finite state transducers are polynomial time identifiable in the limit from positive data.