Complexity Study of Language Operations Using Finite Group Automata
Asia Pacific Journal of Mathematics · 2024
We have explored the intricacies of deterministic finite automata for regular languages derived from applying various operations to languages accepted by finite group automata.These operations include Union, quotient, complement, difference, intersection, Kleene star, Kleene plus, and reversal.Our analysis has involved defining three types of finite group automata structures and examining their complexities.Specifically, we have looked into four complexities of finite group automata: state complexity, accepting state complexity, syntactic complexity, and quotient complexity.Our findings show that the accepting state complexity is the same for all operations defined in the finite group automata structures.Moreover, we have identified the precise values of the syntactic and quotient complexity of the languages accepted by finite group automata when the group is finite cyclic and have determined the range for other groups.