首页 | 本学科首页   官方微博 | 高级检索  
     


Some concepts for languages more powerful than context-free
Authors:Dipl.-Math. E. Bergmann  Dipl.-Math. R. Franck
Affiliation:1. Technische Universit?t Berlin, Fachbereich 20, D-1000, Berlin 10, Germany
2. Programmiersprachen und Compiler I Informationsverarbeitung II, Ernst-Reuter-Platz 8, D-1000, Berlin 10, Germany
Abstract:Some new restrictive devices for grammars are introduced: standard control-sets, G-control-sets, checking state grammars, besides the wellknown ones: matrix-sets, regular control-sets, programs. All these concepts turn out to be equivalent with respect to their generative power. So we get further characterizations of the class of recursively enumerable sets. The generative power of context-freelabel-grammars and Chomsky-grammars both with these restrictive devices is found to be equal. New characterizations of the unconditional-transfer programmed-grammars are introduced, namely unconditional-transfer programs correspond to all the other devices mentioned above under so-called “full-checking possibility” — i.e. the whole set of labels is the checking-set.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号