Abstract Algebra / Automata Theory

Proof 1 : Associativity, Non-Commutativity and the Identity Element of the Concatenation Operation of Strings over a Finite Alphabet

jssandh2Leave a comment

An input sequence of strings from a given alphabet are given as:
w = a_{1}a_{2}.....a_{n}, \ni, a_{i} \in A, where A is a finite set called the Language.
We say that all sequences over an alphabet are in the Kleene-Concatenation, that is:
w \in A^{*}, where, A^{*} = \{\epsilon\}\cup\{A\}\cup\{A.A\}....., where,
\epsilon is the empty string. Note: \epsilon \neq \phi
We will show that the concatenation operation that builds up the Kleene-Set is associative, non-commutative and has an identity element.
Definition: Concatenation is defined as a.b = a_{1}a_{2}...a_{m}b_{1}b_{2}...b_{n} , \forall a_{i}, b_{j} \in A

1) Associativity : We will show that  (a.b).c = a.(b.c), where,  a = a_{1}...a_{l}, b = b_{1}...b_{m}, c = c_{1}..c_{n}
For the LHS of the equation, by definition of concatenation, we have that:
(a.b) = a_{1}..a_{l}b_{1}..b_{m}
So, (a.b).c = (a_{1}..a_{l}b_{1}..b_{m}).c = a_{1}..a_{l}b_{1}..b_{m}c_{1}..c_{n}
For the RHS, we have that,
(b.c) = b_{1}..b_{m}c_{1}..c_{n}
So, a.(b.c) = a.(b_{1}..b_{m}c_{1}..c_{n} = a_{1}..a_{l}b_{1}..b_{m}c_{1}..c_{n}
Clearly, a.(b.c) = (a.b).c
Therefore, the concatenation operation is associative.

2) Non-Commutativty: We will show that, \exists a,b \in A^{*}, \ni, a.b \neq b.a
a = a_{1}...a_{m}, b = b_{1}..b_{n}
By definition,
a.b = a_{1}..a_{m}b_{1}..b_{n} and b.a = b_{1}..b_{n}a_{1}..a_{m}
We can see that for a.b = b.a, we need that (if m = n):
a_{1} = b_{1}.... and ultimately a_{i} = b_{i} \forall i \in \{1, m\}
However, if they are not equal, we see that commutativity is broken. The creation of complements of strings concatenated together is one simple example of strings that break commutativity.
In the event that m \neq n, commutativity may be broken by choosing the smaller string to be a substring of the larger one, and \forall i \in {m + 1, n} arrange the alphabets such that they complement the first {1, m - 1} alphabets of the smaller one.
Clearly, commutativity does not always hold.
Therefore, Concatenation is not Commutative.

3) Identity Element: It is trivial to see that the identity element is the empty string. Now, for the identity element, a.e = a and e.a = a, where e is the identity element. By definition, concatenation with the empty string at the beginning or ending of another string yields the latter string.
Therefore, concatenation has the identity element e = \epsilon

Note : The fact that concatenation is not a commutative operation over the Finite Alphabet L, tells us that there is no finite basis in any Vector Space made from field elements F = L that can span the Kleene-Concatenation of a Language. This tells us that the set is incredibly rich, and beyond the scope of Linear Algebra with a finite basis. Furthermore, one can see that though there exists an identity element, there exists no inverse element for the operation of concatenation.

Reference: 1) Problem D. Automata: The Algebra of Input/Output Sequences, Problems 1 -3, Pages 24, A Book of Abstract Algebra, Charles C. Pinter, Second Edition

Leave a comment