{
  "$type": "site.standard.document",
  "description": "RegEx notation looks a lot like ring expressions.",
  "path": "/posts/language-semiring/",
  "publishedAt": "2026-06-01T00:28:46.000Z",
  "site": "at://did:plc:6n2ngs7zpcpwxz3jaoxj56tu/site.standard.publication/3mo6y7ludvn2h",
  "tags": [
    "reference",
    "computer science"
  ],
  "textContent": "I actually wrote this blog post a couple months ago but only decided to shape it up for posting today: june 18th.\n\nIn my computation theory class, after defining a regular expression, we also defined operations $\\cdot$ and $\\cup$.\nThese operations would take a set of words in a regular language and construct yet another set of words.\nInterestingly, there were some special sets that make this look like a ring:\n\n- The empty set $\\emptyset$ which has the following properties:\n\t- It is an identity element for the $\\cup$ operation: $\\emptyset \\cup A = A \\cup \\emptyset = A$.\n\t- It is an annihilator element for the $\\cdot$ operation: $\\emptyset \\cdot A = A \\cdot \\emptyset = \\emptyset$.\n- The set with one element $\\{\\epsilon\\}$ which is a language that only identifies the empty string has the following properties:\n\t- It is an identity element for the $\\cdot$ operation: $\\{ \\epsilon \\} \\cdot A = A \\cdot \\{ \\epsilon \\} = A$.\n\nThis makes it almost a ring with:\n\n$$\n\t0 \\coloneqq \\emptyset \\\\\n\t1 := \\{ \\epsilon \\} \\\\\n\t+ \\coloneqq \\cup \\\\\n\t\\times := \\cdot\n$$\n\nFor some given alphabet $\\Sigma$, one has to prove that:\n\n1. $(\\Sigma^*, +) \\in \\mathbf{Ab}$\n2. $(\\Sigma^*, \\times) \\in \\mathbf{Mon}$\n3. $A \\times (B + C) = A \\times B + A \\times C$\n\nHowever, we immediately run into some problems.\nSince $\\cup$ is closed and commutative, then $+$ is also closed and commutative.\nPreviously 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).\nFor non-empty sets $A$ or $B$, this is false.\nSo this cannot be a group and therefore cannot be Abelian either.\nNot only is this not a group, every element can have more than identity.\nSo, $A + A = A \\cup A = A$.\n\n- Proposition $(\\Sigma^*, +)$ does not have inverses, for any $\\Sigma$.\n\t- 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\\}$.\n\nNow we know that $(\\Sigma^*, +)$ is a commutative monoid.\nThis makes $(\\Sigma^*, +, \\cdot)$ a semiring.\n\nGeneralization\n\nSince this doesn't really use the structure of regular languages to prove that it is a semiring, then we can further generalize this.\nAs it turns out, $(\\mathbf{Set}, \\cup, \\times_\\sim)$ is a semiring.\nSo, of course a subset of $\\mathbf{Set}$ that is closed under $\\cup$ and $\\times$ would also be a semiring.",
  "title": "Language Semiring"
}