On context-free and Szilard languages (Q794440)

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.