Publications of the Research Institute for Mathematical Sciences


Full-Text PDF (2769 KB) | Table of Contents | PRIMS summary
Volume 9, Issue 1, 1973, pp. 61–92
DOI: 10.2977/prims/1195192738

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

Takeshi Hayashi[1]

(1) Department of Mathematics, Osaka University, 1-1 Machikaneyama-cho, Toyonaka-shi, 560-0043, OSAKA, JAPAN

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.

No keywords available for this article.

Hayashi T. On Derivation Trees of Indexed Grammars – An Extension of the uvwxy-Theorem. Publ. Res. Inst. Math. Sci. 9 (1973), 61-92. doi: 10.2977/prims/1195192738