
doi: 10.1007/bf01937483
The Szilard language of a context-free grammar is context-free if and only if the grammar is ''half-bounded'', i.e. if there is a natural number k such that each sentential form contains at most k occurrences of all but possibly one nonterminal. However, it is quite natural to expect that also non-context-free Szilard languages of context-free grammars share some properties characteristic to context-free languages. The purpose of this paper is to study to what extent certain characterizations for context-free languages are applicable to non-context-free Szilard languages. It is shown that any non-context-free Szilard language does not have the classical pumping property of context-free languages (i.e. any such language does not satisfy the Bar-Hillel's lemma), but instead, the so-called generalized pumping is typical for Szilard languages. Moreover, it is shown that Sokolowski's criterion and Parikh's semilinearity theorem cannot distinguish between context-free and Szilard languages.
Szilard language, context-free grammar, context-free languages, Sokolowski's criterion, pumping, Formal languages and automata, Parikh mapping, semilinearity
Szilard language, context-free grammar, context-free languages, Sokolowski's criterion, pumping, Formal languages and automata, Parikh mapping, semilinearity
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
