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


68Q45 Formal languages and automata


Zbl 0543.00014