清华大学计算机科学与技术系
纸质出版:1996
移动端阅览
[1]吕映芝.上下文无关文法与无限状态自动机[J].电子学报,1996(08):23-27.
Lu Yingzhi. The Context Free Grammar and the Infinite-State Automaton[J]. Acta Electronica Sinica, 1996, (8).
目前,在研究上下文无关语言时常用的形式系统是上下文无关文法和下推自动机,在研究正则语言时常用的形式系统是正则文法和有限状态自动机.正则文法中的符号和有限状态自动机的符号之间的对应关系比较明显,因此,两种系统之间的转换比较容易,并且在这两种系统中观察语言性质时,可以得到相对一致的解释,上下文无关文法与下推自动机之间的对应关系则不够明显,本文所介绍的无限状态自动机也是一种上下文无关语言的识别系统,但它对于上下文无关文法类似于有限状态自动机对于正则文法那样,相互符号间有较明显的对应关系,从而带来相应的好处.
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.
0
浏览量
461
下载量
20
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010802024621