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 L0 denote the language of the word-acceptor. Then a subgroup word-acceptor exists if and only if the set of cosets CH = {H*w;w ∈ L0 and ∃h h ∈ H and h ∈ L0 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*wH and v*wH 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 CH, 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 CH must be finite.

Now let us suppose that CH 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 H1=H,H2,... in CH, and whose initial state 1 is also the unique accept state. The transitions are defined by σn^g→σm if Hn*g=HmCH, 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.