# abstract algebra: how would you define \$ + \$ for this potential ring that describes the single-chain CFGs \$ s \$?

Leave $$s in Sigma ^ *$$. Leave elements of the finite set $$A$$ be collections of subintervals $$(i, j)$$ from $$(0, | s |)$$. Such that yes $$x in A$$ Y $$y, z in x$$ then also $$y subset z, z subset and$$ or $$y cap z = {}$$. Clearly, this captures the idea of ​​a chain grouping $$s$$:

$$((abc) d) f (a (bc) d) e$$

through parentheses. It is also obvious that you can convert the previous grouping into a CFG generator $$s$$:

$$S to AfBe \ A a Cd \ B a aDd \ C a abc$$

and vice versa. Therefore, the generation of CFG $$s$$ correspond one by one with valid parenthesis groupings of $$s$$. Grouping notation is easier to work than grammar notation.

Now define $$(i, j) cap (a, b) = ( max (i, a), min (j, b))$$ where if the result is $$(l, k)$$ Y $$k leq l$$ we say that they don't cross or that their intersection is $$0$$.

Now for any $$x, y in A$$ define $$x cdot y = {a cap b: a in x, b in y }$$. This operation forms a monoid through the associativity of $$cap$$ giving associativity of the intersection of elements, and identity is the element $${(0, | s |) } in A$$. We will refer to that element as $$1$$. There is a zero element, namely $${}$$ which is multiplied by anything to match $${}$$.

Henceforth, $$(i, j) equiv {(i, j) } in A$$ with notation

If we define the union of two singleton elements $$(i, j), (a, b) in A$$ be $${(i, j), (a, b) }$$ Yes $$i neq b$$ Y $$j neq to$$ Y $$(i, j) cap (a, b) = 0$$, and if they touch or overlap $$(i, j) cap (a, b): = ( min (i, a), max (j, b))$$ (its union in the rope $$s$$); so Can we have a ring using some kind of symmetric difference or element by element?

Note that the power set of a set forms a ring below $$+ =$$ symmetric difference

Also, keep in mind that I have posted about this ring before, but I ran into problems that don't have singleton junctions two joints if they touch or overlap.

If you need to define the plugin first, say if you were trying $$x + y = x overline {y} cup overline {x} y$$ trick, then obviously yes $$(i, j)$$ it's a singleton in $$A$$, its complement would be:

$${(0, i), (j, | s |) } in A$$

It is very confusing for me how to extend the complement to other elements, etc. Please try it.