Can someone please explain the word problem (from group theory) in Calculus III layman's terms

Question

I'd appreciate it if someone could offer a schematic explanation of the word problem from group theory in terms which someone at a calculus III level (but without any background in group theory or abstract algebra) could understand. If you are going to use "generators" in your explanation, please explain what a generator is.

Answer 1

Consider a finite alphabet $\Sigma$, i.e. a finite set of letters. For every letter $x$, call $x'$ another letter (not yet in $\Sigma$) and let $\Pi$ denote $\Sigma \cup \{ x' \mid x \in \Sigma \}$, i.e. all letters with and without prime.

A word is just a finite sequence of letters in $\Pi$; the set of all words is denoted by $\Pi^*$. The empty word is also a word; it is written as $\epsilon$.

Now you're given a finite set of rules that allow you to change a word into another word. There are always rules that allows you to remove or add occurences of $xx'$ and $x'x$ (with $x \in \Sigma$) from a word. Furthermore, there is a finite set of rules $R$ that tells you that you can replace a certain subsequence of a word by another subsequence. That is, $R$ is a finite set of pairs $(s_1,s_2)$ with $s_1, s_2 \in \Pi^*$; it means that you can replace an occurence of $s_1$ by $s_2$ or visa versa.

The word problem is: given such a $\Sigma$,a set of rules $R$, is there an algorithm that takes as input two words $w_1$ and $w_2$, and decides whether or not it is possible to change $w_1$ into word $w_2$ by applying the rules?

Example. Consider the letters $a$ and $b$ (and $a'$ and $b'$) and the rules $(aaaa,\epsilon)$, $(bb,\epsilon)$, $(b'ab,a')$. Then it is possible to transform $ab$ into $baaa$ (via $ab \to bb'ab \to ba' \to ba'aaaa \to baaa$), but it is not possible to transform $ab$ into $ba$. (If you know some group theory, you'll recognize this as a presentation of the dihedral group $D_4$.)