Investigations on Hotz groups for arbitrary grammars (Q1088413)

The Hotz group H(G) and the Hotz monoid M(G) of an arbitrary grammar \(G=(V,X,P,S)\) are defined by \(H(G)=F(V\cup X)/P\) and \(M(G)=(V\cup X)^*/P\) respectively. A language \(L\subset X^*\) is called a language with Hotz isomorphism if there exists a grammar G with \(L=L(G)\) such that the natural homomorphism F(X)/L\(\to H(G)\) is an isomorphism. The main result states that homomorphic images of sentential form languages are languages with Hotz isomorphism. This is a generalization of a result of Frougny, Sakarovitch, and Valkema on context-free languages. Hotz groups are used to obtain lower bounds for the number of productions which are needed to generate a language. Further it is shown that there are languages with Hotz isomorphism without being a homomorphic image of a sentential form language, and there are context-sensitive languages without Hotz isomorphism. The theory of Hotz monoids is used to get some results on languages generated by grammars with a symmetric set of rules.