JournalsprimsVol. 9, No. 1pp. 61–92

On Derivation Trees of Indexed Grammars – An Extension of the uvwxy-Theorem

  • Takeshi Hayashi

    Osaka University, Japan
On Derivation Trees of Indexed Grammars – An Extension of the uvwxy-Theorem cover
Download PDF

Abstract

In this paper, the uvwxy-theorem of context-free languages is extended to the case of indexed languages. Applying the extended theorem, it is shown that the finiteness problem for the indexed languages is solvable and certain languages such as {an! ∣ n ≥ 1} and {($ w)lwl| w ∈ {a, b}*} are not indexed languages.

Cite this article

Takeshi Hayashi, On Derivation Trees of Indexed Grammars – An Extension of the uvwxy-Theorem. Publ. Res. Inst. Math. Sci. 9 (1973), no. 1, pp. 61–92

DOI 10.2977/PRIMS/1195192738