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

From MaRDI portal
scientific article
Language Label Description Also known as
English
The generative capacity of block-synchronized context-free grammars
scientific article

    Statements

    The generative capacity of block-synchronized context-free grammars (English)
    0 references
    0 references
    30 June 2005
    0 references
    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.
    0 references
    ET0L languages
    0 references
    synchronization
    0 references
    rewriting systems
    0 references
    indexed languages
    0 references

    Identifiers