2
$\begingroup$

I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(1).

The definition requires the disjointness of certain sets; each set is defined as an infinite limit, but practically calculated via fixed-point iteration of an inductive, case-based equation.

Present in these equations is the definition of a new operator to simplify the notation (let $\epsilon$ be the empty sequence):

$$\forall S,T : S \oplus T = \begin{cases} S & \epsilon \not\in S \\ (S \setminus \{\epsilon\}) \cup T & \epsilon \in S \end{cases}$$

I know this operator in latex as \oplus. In an attempt to write readable-code, I want to give this operator a name (and endow scala Sets with a trait that expresses this name).

Is there a traditional name for this usage of $\oplus$? If so, what is it?

Bonus points: if the name is, e.g., add, is there an acceptable word like addable with the meaning that two objects—mathematical or code—are capable of being added?

$\endgroup$
  • $\begingroup$ Tagging this was surprisingly difficult; I'd be grateful if someone could suggest appropriate tags to get this to the right audience. $\endgroup$ – D. Ben Knoble Apr 23 at 3:07
  • $\begingroup$ You'd probably enjoy Parsing Theory by Sippu & Soisalon-Soininen. In section 5.5 (in volume 1), they present a thorough derivation of a relational expression for the LL(1) prediction relation. Together with the earlier discussion of computing relational expressions, you have a complete algorithm not dependent on least fixed point iteration. Hopefully, your library has a copy. $\endgroup$ – rici Apr 24 at 15:42
  • $\begingroup$ @rici thanks for the recommendation. Anything on category theory for computer scientists? $\endgroup$ – D. Ben Knoble Apr 24 at 17:24
  • $\begingroup$ Nope, sorry. My CS presence is actually pretty small. But good luck with it. $\endgroup$ – rici Apr 24 at 19:46
2
$\begingroup$

A set of values that comes with an "add" operation that is associative is called a semigroup. If it also comes with an element that plays the role of 0 (so that 0 + x = x and x + 0 = x for all x), it is a monoid.

In your case, you have a monoid, as $\{\epsilon\}$ plays the role of 0 (it is an identity).

$\endgroup$
  • $\begingroup$ I saw your update regarding the monoid—had to mentally prove the identity. Will update my own answer accordingly. Funny how these structures seem to arise. $\endgroup$ – D. Ben Knoble Apr 24 at 18:36
2
$\begingroup$

D.W.'s answer is excellent, and gave me a rabbit hole to dig through. The operator clearly establishes a magma, being a closed binary operator. I was able to construct a proof1 that $\oplus$ as defined is associative; thus, the definition gives (at least) a semigroup.

Further, I claim the following: Given any domain (call it the type $A$) and an element $a \in A$, parameterize $\oplus$ on $a$ such that

$$\forall S,T \in \mathcal{P}(A) : S \oplus_a T = \begin{cases} S & a \not\in S \\ (S - \{a\}) \cup T & a \in S \end{cases}$$

The resulting object $(\mathcal{P}(A), \oplus_a)$ is a semigroup.

I have also shown that $\oplus_a$ is not commutative, for let $X$ be some set not containing $a$ and $Y \neq (X \cup \{a\})$ be a set containing $a$: then $X \oplus_a Y = X$, but $Y \oplus_a X = (Y - \{a\}) \cup X \neq X$.

So the resulting object cannot be an Abelian group.

Proofs remain to be had regarding the (non)existence of an identity or the (non)invertibility. If identity can be shown, we have a monoid. If invertibility can be shown, we have an inverse semigroup. If both, then a full group.

The identity element, as pointed out by D.W., is $\Phi = \{a\}$. Put simply:

$$\forall S \in \mathcal{P}(A) : \Phi \oplus_a S = (\Phi - \Phi) \cup S = S$$ $$\forall S \in \mathcal{P}(A) : S \oplus_a \Phi = \begin{cases} S & a \not\in S \\ (S - \Phi) \cup \Phi = S & a \in S \end{cases} \big\}= S$$

So we have a monoid.


1 Proof of associativity is sketched as follows: we must show that $\forall X,Y,Z \in \mathcal{P}(A) : (X \oplus Y) \oplus Z = X \oplus (Y \oplus Z)$.

Now we consider that each of these sets has two states: it either contains or does not contain $a$. Because we need three two-bit states to represent the problem space (the set of cases), we have 7 cases, which we represent as a binary tuple $xyz$. If an element is $0$, it indicates that the corresponding set contains $a$ in the equation. If it is a $1$, it indicates that the corresponding set does not contain $a$ in the equation.

Finally, let $X^0$ be the set $X$ containing $a$ for each of our sets, and $X^1$ similarly be the set not containing $a$. Let $XY = X \cup Y$.

A few facts:

  • $X^0 \oplus Y^0 = X^1Y^0$
  • $X^0 \oplus Y^1 = X^1Y^1$
  • $X^1 \oplus Y^0 = X^1 \oplus Y^1 = X^1$
  • $X^1Y^1 \oplus Z^0 = X^1Y^1 \oplus Z^1 = X^1Y^1$

The cases are left as an exercise to the reader; they are incredibly straightforward.

Hint: $001$ follows from $000$. Similarly, $011$ follows from $010$. Both $101$ and $111$ follow from $100$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.