Scattered context grammars that erase nonterminals in a generalized k-limited way |
| |
Authors: | Alexander Meduna Jiří Techet |
| |
Affiliation: | 1. Department of Information Systems, Faculty of Information Technology, Brno University of Technology, Bo?etěchova 2, 61266, Brno, Czech Republic
|
| |
Abstract: | A scattered context grammar erases nonterminals in a generalized k-limited way in a successful derivation, where k is a positive integer, if in every sentential form of a derivation, each of its substrings consisting of nonterminals from which the grammar derives empty strings is of length k or less. This paper demonstrates that if a scattered context grammar generates its sentences in this way, it can be converted to a scattered context grammar without erasing productions; in general, however, this is not possible. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|