0
$\begingroup$

If ${\bf G}$ and ${\bf H}$ have regular normal forms, then so does ${\bf G}$ x ${\bf H}$ and ${\bf G}$ * ${\bf H}$.

I am new to the concepts of regular normal forms. If anyone could offer any suggestions on how to attack this problem, then that would be great.

1 Answers 1

2

Let's assume that $G$ and $H$ intersect only in the identity element. We can also assume that the normal form representative of the identity element is the empty word $\varepsilon$ for both $G$ and $H$. If not, then just replace these representatives by $\varepsilon$ and you will still have a regular normal form.

The regular normal forms are presumably over finite symmetric (i.e. closed under inversion) generating sets $S$ and $T$ of $G$ and $H$. Denote the sets of normal form words of $G$ and $H$ by $W(G)$ and $W(H)$. These are, by assumption, regular languages over $S$ and $T$ respectively.

For a regular normal form for $G \times H$, you can just take the concatenation $W(G)W(H)$.

For the free product, you could take

$W(G)\, ((W(H) \setminus \{\varepsilon\}) (W(G) \setminus \{\varepsilon\}))* \,W(H)$

where $*$ is the Kleene Star operator. ($X*$ denotes the concatenation of 0 or more elements of $X$.)

Note that the first and last components of such words, in $W(G)$ and $W(H)$, are allowed to be empty, but the other components in the starred middle term must be nonempty and therefore represent non-identity elements of $H$ and $G$.