Language Semiring

I actually wrote this blog post a couple months ago but only decided to shape it up for posting today: june 18th.

In my computation theory class, after defining a regular expression, we also defined operations $\cdot$ and $\cup$. These operations would take a set of words in a regular language and construct yet another set of words. Interestingly, there were some special sets that make this look like a ring:

• The empty set $\emptyset$ which has the following properties:
  • It is an identity element for the $\cup$ operation: $\emptyset \cup A = A \cup \emptyset = A$.
  • It is an annihilator element for the $\cdot$ operation: $\emptyset \cdot A = A \cdot \emptyset = \emptyset$.
• The set with one element $\{\epsilon\}$ which is a language that only identifies the empty string has the following properties:
  • It is an identity element for the $\cdot$ operation: $\{ \epsilon \} \cdot A = A \cdot \{ \epsilon \} = A$.

This makes it almost a ring with:

For some given alphabet $\Sigma$, one has to prove that:

1. $(\Sigma^*, +) \in \mathbf{Ab}$
2. $(\Sigma^*, \times) \in \mathbf{Mon}$
3. $A \times (B + C) = A \times B + A \times C$

However, we immediately run into some problems. Since $\cup$ is closed and commutative, then $+$ is also closed and commutative. Previously we saw that $\emptyset$ acts as an identity element, so in order to prove (1.) it suffices to show that every set $A$ has an inverse $A'$ such that $A \cup A' = \emptyset$ (there are inverses). For non-empty sets $A$ or $B$, this is false. So this cannot be a group and therefore cannot be Abelian either. Not only is this not a group, every element can have more than identity. So, $A + A = A \cup A = A$.

• Proposition $(\Sigma^*, +)$ does not have inverses, for any $\Sigma$.
  • Proof (by contradiction): Suppose that $(\Sigma^*, +)$ does have inverses for some $\Sigma$. Then, there exists an element $(-1) \in \Sigma^*$ such that $1 + (-1) = 0$. However, since $A + A = A, \forall A,$ then $1 + 1 = 1$. Using the inverse of $1$ we have that $1 + 1 + (-1) = 1 + (-1)$ which simplifies to the expression $1 + 0 = 0$ or $1 = 0$. This is false since $\emptyset \ne \{\epsilon\}$.

Now we know that $(\Sigma^*, +)$ is a commutative monoid. This makes $(\Sigma^*, +, \cdot)$ a semiring.

Generalization

Since this doesn’t really use the structure of regular languages to prove that it is a semiring, then we can further generalize this. As it turns out, $(\mathbf{Set}, \cup, \times_\sim)$ is a semiring. So, of course a subset of $\mathbf{Set}$ that is closed under $\cup$ and $\times$ would also be a semiring.