Volume 23, Issue 3, 1975
Filozofia Przyrody
Mieczysław Lubański
Pages 37-47
On the Algebraic Aspects of the Theory of Formal Languages
Theory of formal languages is an youngest branch of contemporary mathematics. The purpose of this paper is to present some kind of algebraic characteristics of the theory of formal languages.
Let S be an alphabet. By a word over the alphabet S we mean a finite immediate sequence of letters. The set of all words over the alphabet S is denoting by S+. We define in the set S+ the operation of concatenation. Let a and b are two words over the alphabet S. The concatenation of the words a and b is the following procedure. We construct a new word, which contain all letters of the word a and all letters of the second word b. The operation of concatenation is an associative operation. Therefore the set S+ with the operation of concatenation is a semigroup.
By a formal language over the alphabet S we mean any subset of the set S+. Let K and L are the languages over the alphabet S. We may define some set- - theoretical operations on the languages K and L; their sum, intersection, product, the complement, the inversion and the iteration of an language. Thus we obtain here some algebraic constructions. In the special case there are the semigroups.
On this way one obtain the possibility of an application of the theory of semigroups to the theory of formal languages. It seems to be an interesting thing. And also this gives, in at least some degree, a reasonable hope to have a background to justify the proposition concerning the hypothesis of the unification of knowledge.