Descriptional Complexity of Block-Synchronization Context-Free Grammars

We consider the descriptional complexity of block-synchronization context-free grammars, BSCF grammars. In particular, we consider the number of necessary situation and begin symbols as complexity measures. For weak and strong derivations, one begin symbol and two situation symbols are sufficient to generate all respective language families. Surprisingly, one situation symbol with equality synchronization is also sufficient to generate all weak derivation BSCF languages. The family of synchronized context-free languages (SCF languages) generated by grammars with one situation symbol using equality synchronization gives a language family properly between that of E0L and ET0L languages. Some normal forms are also presented for all variations. In addition, we show that either prefix or equality synchronization can be used to describe all weak and strong derivation languages.