关键词: (V,R)-半群,(V,R)-语言,超图半群,超图语言,无向图语言,有向图语言,正则语言,Rees同余 中图法分类号TP301.2文献标识码A

Abstract: V is an alphabet.FV is a free semigroup on V．R is a subset of FV．At first,we proposed a concept—(V,R)-semigroup and proved that graph-semigroup and digraph-semigroup are both(V,R)-smigroups．Second,we proposed a concept—hypergraph semigroup．The theories of hypergraphs and free semigroups are connected by the hypergraph semigroups．On this base,we proposed two concepts--(V,R)-languages and hypergraph language．The theories of hypergraphs and formal languages are connected by the hypergraph languages．Furthermore,we proved that the hypergraph language,undirected graph and digraph language are all(V,R)-languages．Third,we proved that the undirected graph language and the digrapg language are both regular languages,which answers the open problems in references of “undirected graph languages” and “digraph languages “．(V,R-)semigroups and(V,R)-languages are new theories and methods of studying free semigroups and formal languages．

Key words: (V,R)-semigroup,(V,R)-language,Hypergraph semigroup,Hypergraph language,Undirected graph language,Digraph language,Regular language,Rees congruence