<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
A derivation D in a context-free grammar G is said to be fair (a notion borrowed from the realm of nondeterministic programming) if either it is finite and terminating, or it is infinite and for each nonterminal symbol A which appears infinitely many times in D, each rule of the form \(A\to x\) in G is used infnitely many times in D. A context-free grammar is fairly terminating if all its fair derivations are finite; a context-free language is fairly generated if it has a fairly terminating grammar. The main question of the paper is: Is every context-free language fairly generated? The question is answered in the negative, by proving that exactly the non-expansive context-free grammars are fairly terminating (therefore all languages of infinite index are not fairly generated).
fairly generated context-free language, context-free grammar, Formal languages and automata, fairly terminating grammar, Engineering(all)
fairly generated context-free language, context-free grammar, Formal languages and automata, fairly terminating grammar, Engineering(all)
citations 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). | Top 10% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |