On the family of finite index matrix languages

摘要

It is proved that: 1.(1) Mƒλ is a substitution closed full AFL closed also under doubling (D(L) = {xx | x ϵ L}).2.(2) Mƒ = Mƒλ = Mac ƒ = Mac ƒλ = Mleft ƒ = Mleft ƒλ = PMƒ = PMƒλ!3.(3) LMƒ ⊂ Mƒ, strict inclusion. (The families M - Mleftλ are as in Salomaa's book [18], LM is the family or simple matrix languages of Ibarra [11] and PM, PMλ are the families of λ-free, respectively, arbitrary, parallel matrix languages [4]. For an arbitrary family of languages, L we denote by Lƒ the family of finite index languages in L, the index being considered with respect to the class of grammars generating languages in L.)4.(4) The emptiness and the finiteness problems for Mƒ are algorithmically solvable, whereas many other decision problems about Mƒ are unsolvable.5.(5) The composition does not increase the generative capacity of (context-free), arbitrary or of finite index, matrix grammars.A conjecture with many significant implications is formulated in the last part of the paper.