On state-alternating context-free grammars

Etsuro Moriya*, Dieter Hofbauer, Maria Huber, Friedrich Otto

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    14 Citations (Scopus)


    State-alternating context-free grammars are introduced, and the language classes obtained from them are compared to the classes of the Chomsky hierarchy as well as to some well-known complexity classes. In particular, state-alternating context-free grammars are compared to alternating context-free grammars (Theoret. Comput. Sci. 67 (1989) 75-85) and to alternating pushdown automata. Further, various derivation strategies are considered, and their influence on the expressive power of (state-) alternating context-free grammars is investigated.

    Original languageEnglish
    Pages (from-to)183-216
    Number of pages34
    JournalTheoretical Computer Science
    Issue number1-3
    Publication statusPublished - 2005 Jun 9


    • Alternating context-free grammar
    • Alternating pushdown automaton
    • Context-free grammar with states
    • State-alternating context-free grammar

    ASJC Scopus subject areas

    • Computational Theory and Mathematics


    Dive into the research topics of 'On state-alternating context-free grammars'. Together they form a unique fingerprint.

    Cite this