Operator Precedence Grammars and the Noncounting Property

Authors:
  • SCStefano Crespi-Reghizzi
    Stefano Crespi-Reghizzi
  • GGGiovanni Guida
    Giovanni Guida
  • DMDino Mandrioli
    Dino Mandrioli
Publisher website
Google Scholar
Abstract
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).

This publication has 16 references indexed in Scilit: