Strings and languages
We next formalize mathematically the notion of a string and a set of strings.
Alphabet is a finite set of elements. (It represents characters of a string.) Let's denote it .
A string is a potentially empty, finite sequence of alphabet elements. Often strings are called “words” in automata theory terminology. We use to denote an empty string. We denote the set of all strings by . We can represent strings of length by -tuples, so we can define
We use centered dot for string concatenation, as in , and we sometimes omit it, as in (programming language Objective Caml uses ^ to denote string concatenation; other languages often use + as an overloaded operator).
The concatentation is an operation . It is associative, and is left and right neutral element:
Therefore, is a monoid.
If is a word, we define and .
A language is any set of strings, that is, a set .
Languages are sets, so operations all apply to them.
We define concatenation and iteration of languages by
Also directly from definition follows: