Languages and formations generated by \(D_4\) and \(Q_8\)

Jean-Éric Pin and Xaro Soler-Escrivà



Résumé : Nous décrivons les deux classes de langages reconnues par les groupes \(D_4\) et \(Q_8\), respectivement. Nous montrons ensuite que les formations de langages engendrées par ces deux classes sont les mêmes. Nous prouvons également que ces deux formations sont fermées par inverses de morphismes, ce qui donne une preuve en théorie des langages du fait que les formations de groupes engendrées par \(D_4\) et \(Q_8\), respectivement, sont deux variétés égales.


Abstract : We describe the two classes of languages recognized by the groups \(D_4\) and \(Q_8\), respectively. Then we show that the formations of languages generated by these two classes are the same. We also prove that these two formations are closed under inverses of morphisms, which yields a language theoretic proof of the fact that the group formations generated by \(D_4\) and \(Q_8\), respectively, are two equal varieties.

PDF file

Valid HTML 4.01!