上下文无关文法与无限状态自动机  

The Context Free Grammar and the Infinite-State Automaton

作　　者：吕映芝 

机构地区：[1]清华大学计算机科学与技术系

出　　处：《电子学报》1996年第8期23-27,共5页Acta Electronica Sinica

摘　　要：目前，在研究上下文无关语言时常用的形式系统是上下文无关文法和下推自动机，在研究正则语言时常用的形式系统是正则文法和有限状态自动机．正则文法中的符号和有限状态自动机的符号之间的对应关系比较明显，因此，两种系统之间的转换比较容易，并且在这两种系统中观察语言性质时，可以得到相对一致的解释，上下文无关文法与下推自动机之间的对应关系则不够明显，本文所介绍的无限状态自动机也是一种上下文无关语言的识别系统，但它对于上下文无关文法类似于有限状态自动机对于正则文法那样，相互符号间有较明显的对应关系，从而带来相应的好处．At present, the context free grammar and the pushdown automaton are the usually used formal systems in research for context free languages, correspondently, the regular grammar and the finite automaton are usually used in research for regular languages. The correspondency between the symbols in regular grammar and the symbols in finite automaton is relatively evident. In other words,it is easier to transform one to the other between these two systems,and people may have a more accordant comprehension when they observe the characteristics of a language in these two systems. But the correspondency between context free grammar and pushdown automaton is not so evident as that between regular grammar and finite automaton. The infinite state automaton introduced in this paper is also a kind of recognizing system for context free languages, however, there is also an evident correspondency between context free grammar and infinite state automaton similar to that between regular grammar and finite antomaton, thus bringing the benefits to the research of context free languages.

关 键 词：正则文法 有限状态自动机 无限状态自动机 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]