Operator Precedence Grammars and the Noncounting Property
Stefano Crespi Reghizzi, Giovanni Guida, Dino Mandrioli · SIAM Journal on Computing · 1981
The notion of noncounting language, initially introduced for regular languages recognized by counter-free finite machines, and recently extended to parenthesized context-free languages, is here further studied for general (i.e., nonparenthesized) context-free languages. While weakly equivalent context-free grammars do not, in general, fall in the same class with respect to the noncounting property, it is shown by a complex proof that weakly equivalent operator precedence grammars are all counting or all noncounting (a property which distinguishes the operator precedence languages from classical deterministically parsable families).