正规文法与有限自动机的等价性研究

通过证明正规文法和有限自动机之间的等价性定理,给出正规文法和有限自动机之间的等价构造方法。     

正规文法与有限自动机的等价构造

在功能上,正规文法与有限自动机描述和识别语言是等价的,它们之间也存在等价构造算法,但这些构造算法有些复杂.对其算法进行了简化且给以了证明,并提出了一个从有限自动机构造等价左线性正规文法的算法,同时也进行了证明,最后给出了该算法的一个实例.     

格值下推自动机与格值上下文无关文法

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。     

Fuzzy正规集合与Fuzzy右线性文法的关系

在文献[1]的基础上,对Fuzzy正规集合和Fuzzy右线性文法之间的关系作了进一步的探讨,证明了Fuzzy正规集合的右线性可表示性,为进一步研究Fuzzy正规集合与Fuzzy有限状态自动机的关系提供了一种新方法.     

量化上下文无关语言的代数性质

通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。     

取值于赋值幺半群的加权正则文法语言

正则文法是研究自动机的重要工具。引入取值于赋值幺半群的加权正则文法、加权类正则文法的定义,讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机(WFA)的关系。证明了在赋值幺半群上,已知一个加权正则文法或加权类正则文法,分别存在一个WFA与之等价。定义了可分配的赋值幺半群,证明了在可分配的赋值幺半群上已知一个WFA,存在一个加权正则文法和加权类正则文法与之等价,即证明了可分配的赋值幺半群上加权正则文法、加权类正则文法和WFA在生成语言上等价,并举例说明了赋值幺半群的可分配性不是已知WFA存在与之等价的加权正则文法或加权类正则文法的必要条件。     

基于完备剩余格值逻辑的自动机和文法理论

初步建立基于完备剩余格值逻辑自动机与文法理论的基本框架。引入l值正则文法的概念,证明了任意l值自动机识别的语言等价于某种l值正则文法所生成的语言,反之,任意l值正则文法所生成的语言等价于某种l值自动机识别的语言。获得l值自动机及被l值自动机识别的语言的连接问题刻画。特别地,建立l值和L值泵引理,并得到l值语言的判定性刻画。最后,揭示带ε移动的l值自动机与不带ε移动的l值自动机之间的两个等价关系。     

基于量子逻辑的自动机和文法理论

初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.     

扰动值模糊有限自动机及其语言*

引入扰动值模糊有限自动机及其语言的概念,讨论扰动值模糊有限自动机的状态转移函数的扩张问题,证明3类确定型扰动值模糊有限自动机、非确定型扰动值模糊有限自动机相互等价性,研究扰动值模糊有限自动机的语言关于正则运算的封闭性.     

格值树自动机与格值上下文无关树文法的等价性

本文将模糊树自动机和模糊上下文无关树文法的概念推广到格半群上。证明了在接受语言和生成语言的意义下,树自动机和上下文无关树文法是等价的。同时给出了构造正规形式的等价文法的方法。     

广义左,右线性递归规则组改写

本文从左，右线性递归规则组的定义出发，提出了广义左，右线性递归规则组的定义，放宽了左，右线性递归规则组寻规则形式的限制，扩展了Ｕｌｌｍａｎ提出的左，右线性递归规则组改写方法的适用范围。本文证明了由广义左，右线性递归规则组向左，右线性规则组转换的相容性，并给出了具体的转换算法。     

模糊识别器与有穷自动机的等价性

针对模糊识别器与有穷自动机的关系,证明了当输入字母表相同时,任给一个模糊识别器,必然存在一个有穷自动机,使得模糊识别器的行为与有穷自动机所接受的语言相同;反之,任给一个有穷自动机,必然存在一个模糊识别器,使得有穷自动机所接受的语言与模糊识别器的行为相同,从而得出它们之间的等价性。     

加权有穷自动机的代数性质

在加权有穷自动机理论基础上,利用强同态的概念,证明两个加权有穷自动机在计算能力上是等价的,并在加权有穷自动机的状态集上建立一种等价关系,得到加权有穷自动机的商自动机,证明加权有穷自动机与其商自动机在计算能力上也是等价的。并通过引入加权有穷自动机的可交换性、分离性、(强)连通性及层的概念,讨论在(强)同态的条件下,两个加权有限状态机之间的可交换性、分离性、(强)连通性及层的关系。关键词：     

Fuzzy relation equations and reduction of fuzzy automata

We show that the state reduction problem for fuzzy automata is related to the problem of finding a solution to a particular system of fuzzy relation equations in the set of all fuzzy equivalences on its set of states. This system may consist of infinitely many equations, and finding its non-trivial solutions may be a very difficult task. For that reason we aim our attention to some instances of this system which consist of finitely many equations and are easier to solve. First, we study right invariant fuzzy equivalences, and their duals, the left invariant ones. We prove that each fuzzy automaton possesses the greatest right (resp. left) invariant fuzzy equivalence, which provides the best reduction by means of fuzzy equivalences of this type, and we give an effective procedure for computing this fuzzy equivalence, which works if the underlying structure of truth values is a locally finite residuated lattice. Moreover, we show that even better reductions can be achieved alternating reductions by means of right and left invariant fuzzy equivalences. We also study strongly right and left invariant fuzzy equivalences, which give worse reductions than right and left invariant ones, but whose computing is much easier. We give an effective procedure for computing the greatest strongly right (resp. left) invariant fuzzy equivalence, which is applicable to fuzzy automata over an arbitrary complete residuated lattice.     

拓广的右线性递归变换算法及其正确性

本文给出拓广的右线性递归变换算法并证明其正确性.拓广的右线性递归中可以包含一个或多个IDB谓词,它是右线性递归的一般化.和右线性递归计算算法一样,本文提供的算法遵循魔集的模式:首先改写规则,然后用半扑质的自底向上算法计算新规则.算法的有效性通过减少递归谓词的元数实现.     

正则表达式方程组的最小解

网络安全检测中,正则表达式匹配是深度包检测的主要手段,匹配算法则是其关键技术。目前,正则表达式匹配算法可以大体分为转换压缩、状态压缩和字母表压缩三类。文章讨论正则表达式方程组最小解及其求解算法,证明了正则表达式方程组的最小解的存在性和基于Gauss消元法的求解算法的正确性,给出了最小解的构造,分析了求解算法的时间复杂度...     

Context-free languages over infinite alphabets

In this paper we introduce context-free grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a context-free grammar over an infinite alphabet if and only if it is accepted by a pushdown automaton over an infinite alphabet. Also the generated (accepted) languages possess many of the properties of the ordinary context-free languages: decidability, closure properties, etc.. This provides a substantial evidence for considering context-free grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones. Received November 27, 1995 / March 4, 1997     

More on quantum,stochastic, and pseudo stochastic languages with few states

Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all these numbers of states are optimal. After this, we completely characterize the class of languages recognized by 1-state GFAs, which is the only nontrivial class of languages recognized by 1-state automata. Finally, we consider the variations of PFAs, QFAs, and GFAs based on the notion of inclusive/exclusive cutpoint, and present some results on their expressive power.     

Probabilistic context-free grammars estimated from infinite distributions

In this paper, we consider probabilistic context-free grammars, a class of generative devices that has been successfully exploited in several applications of syntactic pattern matching, especially in statistical natural language parsing. We investigate the problem of training probabilistic context-free grammars on the basis of distributions defined over an infinite set of trees or an infinite set of sentences by minimizing the cross-entropy. This problem has applications in cases of context-free approximation of distributions generated by more expressive statistical models. We show several interesting theoretical properties of probabilistic context-free grammars that are estimated in this way, including the previously unknown equivalence between the grammar cross-entropy with the input distribution and the so-called derivational entropy of the grammar itself. We discuss important consequences of these results involving the standard application of the maximum-likelihood estimator on finite tree and sentence samples, as well as other finite-state models such as hidden Markov models and probabilistic finite automata.