Notation for concat in set theory

Question

I'm working on homework for a automata theory class. So far its just proofs involving regular expression nothing too crazy. Anyway, my question is this what is the proper set notation for concatenation? For example I know R + S would be the same as R union S but for the the life of me I can't remember what the set theory equivalent to concatenation is.

I'm not going to post any problems as I think I'll be fine working on them, could anyone give me a little nudge in the right direction?

Answer 1

I believe you're referring to the concatenation of regular sets. Usually, either concatenation or the dot operator denotes the concatenation of regular sets. The same notation applies to regular expressions. For instance

• AB = A·B = { xy : x ∈ A & y ∈ B }

Formally, the regular sets form a Kleene algebra, which is an idempotent semiring with the Kleene star operator that satisfies a collection of axioms. In algebras like an idempotent semiring, multiplication is usually expressed via concatenation or the dot operator. This is why concatenation of regular sets - the multiplication operation in the Kleene algebra - is denoted by concatenation or the dot operator. The same is true of regular expressions.

Answer 2

R + S is not the same as R union S, because strings are not sets. Strings are on an alphabet which is a set. (Though technically you could represent a string as a set of ordered pairs (char, index)).

You should just say R + S when you mean to concatenate. You cannot concatenate general sets.

However, you can concatenate sets of strings. For sets of strings U and V, the concatenation, UV consists of all strings of the form uv where u is a string from U and v is a string from V. It's a bit like a cross-product.