## Principality results about some matrix languages families.(English)Zbl 0551.68063

Automata, languages and programming, 11th Colloq., Antwerp/Belg. 1984, Lect. Notes Comput. Sci. 172, 151-161 (1984).
[For the entire collection see Zbl 0543.00014.]
Let M, $$M_{fin}$$ and $$M_ k$$, $$k\geq 1$$, be the families of (context- free) matrix languages, of finite index matrix languages, and of matrix languages of index not greater than k. It is known that all these families are semi-AFL’s and $$M_{fin}$$ is a non-principal full-AFL. The paper proves that M and $$M_ k$$, $$k\geq 1$$, are principal semi-AFL’s and investigates their generators. Some technical preliminary results are used: normal forms, the equivalence of matrix and controlled grammars of index not greater than k, $$k\geq 1$$, etc.
Reviewer: G.Păun

### MSC:

 68Q45 Formal languages and automata

### Keywords:

matrix languages; AFL

Zbl 0543.00014