On the equality of grammatical families

摘要

A decision procedure involving the testing for containment is presented for determining whether two grammatical families (families generated by context-free grammar forms) are equal. It is also shown that every nontrivial grammatical family which is a proper subset of the family of context-free languages can be constructed in a unique canonical way from the family of regular sets by certain operations. Thus, two such grammatical families are equal iff their canonical representations are identical.