MAF : Background : Subgroup word-acceptors
## Subgroup word-acceptors

We prove here that given that a unique word-acceptor for the group exists, a subgroup word-acceptor for a subgroup *H* exists if and only if a certain set of right cosets of *H* is finite. For any word *w* let *P(w)*={*w(i)*} the set of all prefixes of *w* and Let *L*_{0} denote the language of the word-acceptor. Then a subgroup word-acceptor exists if and only if the set of cosets *C*_{H} = {*H*w*;*w ∈ L*_{0} and ∃*h* *h ∈ H* and *h ∈ L*_{0} and *w ∈ P(h)*} is finite. (Technically speaking in this definition I am guilty of regarding words and elements as being interchangable, but given that we are considering only irreducible words I hope the reader will forgive me).

First let us suppose that the subgroup word-acceptor exists. In this case we can assume that it is trim. Let us consider what it means if a state σ is reached by two different words *u*,*v*. Clearly there is some word *w* such that *u*w* ∈ *H* and *v*w* ∈ *H* otherwise the acceptor would not be trim. So we have *u*w =*_{G} h1 and *v*w =*_{G} h2 where *h1, h2* are presumably distinct elements of *H*. But therefore *u =*_{G} h1*W and *v =*_{G} h2*W. "Multiplying" on the left by *H* to find the corresponding cosets gives us *H***u = H*h1*W* = *H*W* and *H*v = H*h2*W = H*W*.

This shows both that any state of a subgroup word-acceptor is associated with a unique coset. The subgroup word-acceptor must not reach its failure state for any of the words *w* mentioned in the definition of the set *C*_{H}, so every element of this set must correspond to at least one state, and no two elements to the same state. Since the set of states is finite *C*_{H} must be finite.

Now let us suppose that *C*_{H} is finite, and that the word-acceptor for the group exists. Clearly we can form a (partial) membership FSA whose states 1..n are labelled by the n cosets *H*_{1}=H,H_{2},... in *C*_{H}, and whose initial state 1 is also the unique accept state. The transitions are defined by *σ*_{n}^g→σ_{m} if *H*_{n}*g=H_{m} ∈ *C*_{H}, and by *σ*_{n}^g→0 otherwise. Now the "and" of this FSA with the word-acceptor for the group is the subgroup word-acceptor whose existence we wished to prove.