有穷自动机和正规文法

3.1 有穷自动机 在第二章,我们介绍了生成图式——文法。文法是对语言的有穷说明。在这一章我们将看到有穷地说明无穷语言的另一种方法——识别器。我们将考虑的无疑是最简单的识别器,叫做有穷自动机。有穷自动机(fa)不能定义所有由文法定义的语言,然而我们将证明已定义     

译校者的话

《形式语言及其与自动机的关系》一书可看成数字电子计算机编译程序理论和语言理论之著作,着重讲形式语言与自动机的关系。 作者首先对什么是过程和算法作了一般定义。然后阐明了语言的两个生成系统,一个是文法,另一个是识别器,即常说的自动机。两者都是有穷表示,但说明的语言却都可以是无穷的。     

几类带空转移的n元伪加权自动机的关系

引入了n元伪加权有穷自动机——带有n个有限字符集的伪加权有穷自动机、分明型n元伪加权有穷自动机和确定型n元伪加权有穷自动机的概念。根据状态转移函数在每个字符集上是否带空转移, 将以上自动机分为4类:带r-型空转移的n元伪加权有穷自动机和带空转移的n元伪加权有穷自动机和带r-型空转移的分明型n元伪加权有穷自动机和带空转移的分明型n元伪加权有穷自动机。给出了以上自动机所识别语言的定义并探究了它们之间的关系,讨论了状态转移函数在每个字符集上是否带空转移对其接受语言的影响。     

论回溯自动机

为了描述集成化软件工程环境用户接口中选单的控制机构,需要引入回溯自动机的概念。本文给出了回溯自动机概念的严格数学定义,并讨论了它与有穷自动机、确定的下推自动机等之间的关系,证明了它所接受的语言类处于正则语言类与确定的上下文无关语言类之间。     

基于Moore机器的一般汉字有穷自动机

为了更好地研究汉字信息输入系统,提高汉字输入速度,解决汉字输入的“瓶颈”问题,通过对以西文为背景的经典自动机理论的研究,给出了能够描述汉字有穷自动机所接受语言的正规表达式,并在此基础上引入了具有输出的有穷自动机的概念,具体给出了基于Moore机器的一般汉字有穷自动机的数学模型。     

关于交替的ω─有穷自动机的接受条件

到目前为止，交替的ω－有穷自动机的接受条件仅有６种，本文给出了６种新形式的接受条件，并研究了交替的ω－有穷自动机在这些条件下识别语言的能力．最后给出了ω－自动机在各种接受条件下识别的语言类．     

一类交替的ω—有穷自动机和确定的ω—有穷自动机识别能力…

本文提出了一类交替的ω－有穷自动机，即所有状态都是万能的交替的ω－有穷自动机，并采用了构造的方法证明了ω－ＵＡＦＡ和确定的ω－有穷自动机在四种接受条件下接受的ω－语言的等价性。     

关于ω—有穷自动机的两个新的接受条件

至今被公开的ω有穷自动机的接受条件有６个即Ｃ１－Ｃ６，寻找新的接受条件和研究ω－有穷自动机关于新接受条件接受ω－语言能力是ω有穷自动机理论中的一个重要课题。本定义了ω有穷自动机的两个新的接受条件Ｚ１和Ｚ２，并且研究了：（１）ω－Ｕ－ＮＦＡ关于Ｚｉ（ｉ＝１，２）接受ω－语的能力。     

模糊有穷自动机与单体二阶Lukasiewicz逻辑

该文引入了单体二阶Lukasiewicz逻辑,进而给出了模糊有穷自动机识别语言的逻辑描述,证明了多值逻辑意义下的Bchi与Elgot基本定理.通过引入星-自由模糊语言与非周期模糊语言,刻画了可以用一阶Lukasiewicz逻辑定义的模糊语言.     

一类交替的ω－有穷自动机和确定的ω－有穷自动机识别能力的等价性

本文提出了一类交替的ω－有穷自动机，即所有状态都是万能的交替的ω－有穷自动机（记为ω－ＵＡＦＡ），并采用了构造的方法证明了ω－ＵＡＦＡ和确定的ω－有穷自动机在四种接受条件下接受的ω－语言的等价性。     

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata are discussed. The notions of intuitionistic fuzzy recognizer, complete accessible intuitionistic fuzzy recognizer, intuitionistic fuzzy finite automata, deterministic intuitionistic fuzzy finite automata, and intuitionistic fuzzy language are introduced. It is shown that the languages recognized by intuitionistic fuzzy recognizer are regular, and the intuitionistic fuzzy languages recognized by the intuitionistic fuzzy finite automaton and the intuitionistic fuzzy languages recognized by deterministic intuitionistic fuzzy finite automaton are equivalent. This work is supported by National Science Foundation of China (Grant No.10571112), “TRAPOYT” of China and National 973 Foundation Research Program(Grant No.2002CB312200).     

格值有限自动机等价判定算法

引入了完备L-Fuzzy矩阵的概念,给出了基于格半群的模糊有限自动机的形式化定义,即完备格值有限自动机,研究了它的主要性质;给出了完备格值有限自动机的行为矩阵,从行为矩阵出发,给出了自动机状态等价和自动机等价的定义。最后,得到了该类自动机等价的判定算法。     

Mizumoto格值有限自动机及其最小化

提出取值为格半群的Mizumoto格值有限自动机的概念,得到基于模糊字符串的Mizumoto格值有限自动机的扩张模型,并详细讨论了其性质。同时建立了扩张Mizumoto格值有限自动机与标准扩张Mizumoto格值有限自动机的等价性,在此基础上给出了其最小化算法。     

模糊有限自动机的最小化算法优化

现有的模糊自动机最小化算法没有涉及到对模糊自动机状态的隶属度迁移和变化的讨论,优化的模糊自动机最小化算法弥补了这类算法的不足之处。该算法将模糊有限自动机首先转化为单个初始状态的模糊自动机,然后再将转化后的模糊自动机化简为最小模糊自动机,算法在转化过程中单独讨论了模糊自动机状态隶属度的转化方式,使得算法更加严谨和简化。     

On input-revolving deterministic and nondeterministic finite automata

We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with the additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any deterministic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.     

一类格值自动机的极小化

给出了格值自动机的同余和同态,从代数角度出发详细研究了同余和同态关系的代数性质,揭示了格值自动机的代数性质和取值格半群的紧密联系,利用同余和同态关系最终研究了格值自动机的极小化问题,在正则同余下给出了可在有限步实现具有模糊初始状态和特殊模糊终状态的自动机极小化的算法。     

基于模糊度量的软件漏洞检测技术研究

本文根据有限状态自动机和模型检测的思想,结合模糊数学对行为分析的优势,提出基于模糊度量的软件漏洞检测技术,并利用漏洞属性分解和模糊状态转移函数使此技术具有自学习机制和更高效广泛的检测能力。实验测试了利用模糊度量的软件漏洞检测技术可以提高漏洞发现率和给出漏洞的危急程度。     

同步格值自动机的约简和最小化算法

引入了完备L-Fuzzy矩阵的概念,提出了取值于格半群上的输入字符和输出字符长度相同的模糊自动机的概念,即完备的同步格值自动机的概念,研究了它的主要性质;从行为矩阵出发,给出了完备的同步格值自动机状态等价和自动机等价的定义,从自动机的状态等价,研究了该自动机可约简的条件,并得到了该自动机的最小化算法。     

Fuzzy Sets and Neural Networks

Abstract

It is possible that a better model for the behavior of a nerve cell may be provided by what might be called a fuzzy neuron, which is a generalization of the McCulloch-Pitts model. The concept of a fuzzy neuron employs some of the concepts and techniques of the theory of fuzzy sets which was introduced by Zadeh [2, 3] and applied to the theory of automaton by Wee and Fu [6], Tanaka et al. [7], Santo [8] and others. In effect, the introduction of fuzziness into the model of a neuron makes it better adapted to the study of the behavior of systems which are imprecisely defined by virtue of their high degree of complexity. Many of the biological systems, economic systems, urban systems and more generally, large-scale systems fall into this category.

In the nearly three decades since its publication, the pioneering work of McCulloch and Pitts [1], has had a profound influence on the development of the theory of neural nets, in addition to stimulating much of the early work in automata theory and regular events.

Although the McCulloch-Pitts model of a neuron has contributed a great deal to the understanding of the behavior of neural-like systems, it fails to reflect the fact that the behavior of even the simplest type of nerve cell exhibits not only randomness but, more importantly, a type of imprecision which is associated with the lack of sharp transition from the occurrence of an event to its non-occurrence.

In this paper, some basic properties of fuzzy neural networks as well as their applications to the synthesis of fuzzy automata are investigated. It is shown that any n-state minimal fuzzy automaton can be realized by a network of m fuzzy neurons, where ┌log₂ n┐ ? m ? 2n. Examples are given to illustrate the procedure. As an example of application, a realization of λ-fuzzy language recognizer using a fuzzy neural network is presented. The techniques described in this paper may be of use in the study of neural networks as well as in formal languages, pattern recognition, and learning.     

Regular grammars with truth values in lattice-ordered monoid and their languages

In this study, we introduce the concept of lattice-valued regular grammars. Such grammars have become a necessary tool for the analysis of fuzzy finite automata. The relationship between lattice-valued finite automata (LA) and lattice-valued regular grammars (LRG) are discussed and we get the following results, for a given LRG, there exists an LA such that they accept the same languages, and vice versa. We also show the equivalence between deterministic lattice-valued regular grammars and deterministic lattice-valued finite automata.