The generative capacity of block-synchronized context-free grammars (Q557813)

The author gives an alternate characterization for the family of ET0L languages. So it is proved that the family of ET0L languages coincides with the family of the synchronized context-free languages and with the family of Block-Synchronized Context-Free (BSCF) languages, where the nesting or recursion depth is bounded above by any constant. For this purpose a normal form for BSCF grammars is provide. This result is useful for the study of the ET0L languages as it is often easier to describe a language using a BSCF grammar. By examination of the BSCF grammar it is shown that when the recursion of BSCF grammars can get arbitrarily deep, then the generated language family using two defined types of synchronization is equal to the family of indexed languages. It is proved that BSCF languages are more general than finite nesting depth BSCF using both types of synchronization.