Decidability and density in two-symbol grammar forms

AbstractIt is proved that form equivalence is decidable for context-free grammar forms with only one nonterminal and one terminal symbol. However it also proved that there are “many” grammatical families generated by such forms: with some trivial exceptions, the families are dense in the sense that between any two families one can “squeeze” in a third one. The results obtained are applied also to L forms