# Operator name in LL(1) computation

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?

• Tagging this was surprisingly difficult; I'd be grateful if someone could suggest appropriate tags to get this to the right audience. – D. Ben Knoble Apr 23 '19 at 3:07
• 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. – rici Apr 24 '19 at 15:42
• @rici thanks for the recommendation. Anything on category theory for computer scientists? – D. Ben Knoble Apr 24 '19 at 17:24
• Nope, sorry. My CS presence is actually pretty small. But good luck with it. – rici Apr 24 '19 at 19:46

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).

• 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. – D. Ben Knoble Apr 24 '19 at 18:36

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$$.