On sentential forms of context-free grammars |
| |
Authors: | Arto Salomaa |
| |
Affiliation: | (1) Mathematics Department, University of Turku, Turku, Finland |
| |
Abstract: | Summary There is no algorithm for deciding whether two linear context-free grammars generate the same sentential forms. The equivalence problem for propagatingOL-systems is undecidable. The finiteness problem forOL-systems is decidable.SF-languages, i.e., languages which equal the set of sentential forms of a context-free grammar, possess some of the properties of context-free languages but their family is not closed under any of the ordinary operations. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|