The structure of context-free grammatical families

摘要

Let ℒCI be the family of context-free languages. Two characterization theorems are given for (context-free) grammatical families. The first says that the class of grammatical families not ℒCF is the smallest collection of sets of languages which contains the trivial ones and is closed under a union operator ∨, a concatenation operator ⊙, and ℐ, where ℐ is a ternary operator involving substitution into linear languages. The second asserts that the collection of all nontrivial grammatical families not ℒCF is the smallest collection of sets of languages which contains the family of regular sets, and is closed under ∨, ⊙, ℐ, and the full AFL operator ℱ^.