Introduction to Universal Algebra

George Voutsadakis1

1 Mathematics and Computer Science

Lake Superior State University

LSSU Math 400

George Voutsadakis (LSSU) Universal Algebra June 2020 1 / 44

 Outline

1 Selected Topics
Steiner Triple Systems, Squags and Sloops
Quasigroups, Loops and Latin Squares
Orthogonal Latin Squares
Finite State Acceptors

George Voutsadakis (LSSU) Universal Algebra June 2020 2 / 44

 Selected Topics Steiner Triple Systems, Squags and Sloops

Subsection 1

Steiner Triple Systems, Squags and Sloops

George Voutsadakis (LSSU) Universal Algebra June 2020 3 / 44

 Selected Topics Steiner Triple Systems, Squags and Sloops

Steiner Triple Systems

Definition
A Steiner triple system on a set A is a family S of three-element subsets
of A, such that each pair of distinct elements from A is contained in exactly
one member of S . |A| is called the order of the Steiner triple system.

If |A| = 1, then S = ;.
If |A| = 3, then S = {A}.
If |A| = 2, there are no Steiner triple systems on A.

George Voutsadakis (LSSU) Universal Algebra June 2020 4 / 44

 Selected Topics Steiner Triple Systems, Squags and Sloops

Necessary Conditions on |A| and |S |

Theorem
If S is a Steiner triple system on a finite set A, then:
|A|(|A|−1)
(a) |S | = 6 ;
(b) |A| ≡ 1 or 3 (mod 6).

(a) Note that each member of S contains three distinct pairs of elements
of A. Each pair of elements appears in only one member of S. Thus,
the number of pairs of elements from A is exactly 3|S |, i.e.,
¡|A|¢ |A|(|A|−1)
2 = 3|S |. This gives 2 = 3|S | whence the conclusion follows.
(b) Fix a ∈ A and let T1 , . . . , Tk be the members of S to which a belongs.
No pair of elements of A is contained in two distinct triples of S .
Thus, the doubletons T1 − {a}, . . . , Tk − {a} are mutually disjoint. Each
member of A − {a} is in some triple along with the element a. So
A − {a} = (T1 − {a}) ∪ · · · ∪ (Tk − {a}). Thus, 2 | |A| − 1, so |A| ≡ 1
(mod 2). From (a), |A| ≡ 0 or 1 (mod 3); hence, |A| ≡ 1 or 3 (mod 6).
George Voutsadakis (LSSU) Universal Algebra June 2020 5 / 44
 Selected Topics Steiner Triple Systems, Squags and Sloops

The Steiner Triple System of Order 7

After |A| = 3, the next possible size |A| is 7.

The figure shows a Steiner triple system of

order 7, where we require that three num-
bers be in a triple iff they lie on one of the
lines drawn or on the circle.
This is the only Steiner triple system of
order 7 (up to a relabeling of the elements).

George Voutsadakis (LSSU) Universal Algebra June 2020 6 / 44

 Selected Topics Steiner Triple Systems, Squags and Sloops

Steiner Quasigroups
To construct new Steiner triple systems from old ones,
we convert it to an algebraic system;
use standard constructions in universal algebra.
A natural way of introducing a binary operation · on A is to require
a·b = c if {a, b , c } ∈ S .
Since a · a is left undefined, we define a · a = a.
The associative law for · fails (look at the system of order 3).
Nonetheless, we have the identities:
(Sq1) x · x ≈ x;
(Sq2) x · y ≈ y · x;
(Sq3) x · (x · y ) ≈ y .

Definition
A groupoid satisfying the identities (Sq1)-(Sq3) above is called a squag (or
Steiner quasigroup).
George Voutsadakis (LSSU) Universal Algebra June 2020 7 / 44
 Selected Topics Steiner Triple Systems, Squags and Sloops

Squads Correspond to Steiner Triple Systems

Theorem
If 〈A, ·〉 is a squag, define S to be the set of three-element subsets {a, b , c }
of A, such that the product of any two elements gives the third. Then S is
a Steiner triple system on A.

Suppose a · b = c holds. Then a · (a · b) = a · c, so by (Sq3), b = a · c.

Similarly, b · c = a. Thus, in view of (Sq1), if any two are equal, all
three are equal. Consequently, for any two distinct elements of A,
there is a unique third element (distinct from the two) such that the
product of any two gives the third. Thus, S is indeed a Steiner triple
system on A.

George Voutsadakis (LSSU) Universal Algebra June 2020 8 / 44

 Selected Topics Steiner Triple Systems, Squags and Sloops

Steiner Loops

Another approach to converting a Steiner triple system S on A to an

algebra is to adjoin a new element, called 1, and replace a · a = a by

a · a = 1, a · 1 = 1 · a = a.

This leads to a groupoid with identity 〈A ∪ {1}, ·, 1〉, satisfying the

identities:
(Sℓ1) x · x ≈ 1;
(Sℓ2) x · y ≈ y · x;
(Sℓ3) x · (x · y ) ≈ y .

Definition
A groupoid with a distinguished element 〈A, ·, 1〉 is called a sloop (or
Steiner loop) if the identities (Sℓ1)-(Sℓ3) hold.

George Voutsadakis (LSSU) Universal Algebra June 2020 9 / 44

 Selected Topics Steiner Triple Systems, Squags and Sloops

Sloops and Steiner Triple Systems

Theorem
If 〈A, ·, 1〉 is a sloop and |A| ≥ 2, define S to be the three-element subsets
of A − {1}, such that the product of any two distinct elements gives the
third. Then S is a Steiner triple system on A − {1}.

Similar to the preceding theorem.

George Voutsadakis (LSSU) Universal Algebra June 2020 10 / 44

 Selected Topics Quasigroups, Loops and Latin Squares

Subsection 2

Quasigroups, Loops and Latin Squares

George Voutsadakis (LSSU) Universal Algebra June 2020 11 / 44

 Selected Topics Quasigroups, Loops and Latin Squares

Quasigroups Formalisms
A quasigroup is usually defined to be a groupoid 〈A, ·〉, such that, for
any elements a, b ∈ A, there are unique elements c , d, satisfying

a · c = b, d · a = b.

The previously
²
adopted
±
definition of quasigroups has two extra binary
operations and , left division and right division respectively, which
allow us to consider quasigroups as an equational class.
± ²
Recall that the axioms for quasigroups 〈A, , ·, 〉 are given by
² ±
x (x ²· y ) ≈ y (x ±· y ) y ≈ x
x · (x y ) ≈ y (x y ) · y ≈ x .

To convert a quasigroup 〈A, ·〉 in the usual definition to one in our

definition we let
±
a²b be the unique solution c of c · b = a;
a b be the unique solution d of a · d = b.
George Voutsadakis (LSSU) Universal Algebra June 2020 12 / 44
 Selected Topics Quasigroups, Loops and Latin Squares

Quasigroups Formalisms (Cont’d)

± ²
Conversely, let 〈A, , ·, 〉 be a quasigroup by our definition.
² ²
If a, b ∈ A, we have a · (a b) = b. So there is a c := a b, such that
a · c = b. ² ²
Suppose a, b²∈ A and c is such that a · c = b. Then a (a · c) = a b.
Hence c = a b. So only one such c is possible.
Similarly, we ±can show that there is exactly one d, such that d · a = b,
namely d = b a.
Thus, the two definitions of quasigroups are, in an obvious manner,
equivalent.

George Voutsadakis (LSSU) Universal Algebra June 2020 13 / 44

 Selected Topics Quasigroups, Loops and Latin Squares

Quasigroups with Identity and Squags

A loop is usually defined to be a quasigroup with ±an ²identity element

〈A, ·, 1〉. In our definition, we have an algebra 〈A, , ·, , 1〉 and such
loops form an equational class.
Suppose S is a Steiner triple system on A.
The associated squag 〈A, ·〉 is a quasigroup: If a · c = b, then
a · (a · c) = a · b. So c = a · b. Furthermore, a · (a · b) = b. Hence, if we
are given a, b, there is a unique c, such that a · c = b. Similarly, there is
a unique d, such that d · a = b.
In the case ±of squags
²
we do not need to introduce the additional
operations and to obtain an equational class:
±²
In this case , and · are all the same.
Squags are sometimes called idempotent totally symmetric
quasigroups.

George Voutsadakis (LSSU) Universal Algebra June 2020 14 / 44

 Selected Topics Quasigroups, Loops and Latin Squares

Cayley Tables and Quasigroups

Given any finite groupoid 〈A, ·〉, we can write

out the multiplication table of 〈A, ·〉 in a square
array, giving the Cayley table of 〈A, ·〉.

Theorem
A finite groupoid A is a quasigroup iff every element of A appears exactly
once in each row and in each column of the Cayley table of 〈A, ·〉.
If we are given a, b ∈ A, then there is exactly one c satisfying a · c = b
iff b occurs exactly once in the a-th row of the Cayley table of 〈A, ·〉
and there is exactly one d, such that d · a = b iff b occurs exactly once
in the a-th column of the Cayley table.

George Voutsadakis (LSSU) Universal Algebra June 2020 15 / 44

 Selected Topics Quasigroups, Loops and Latin Squares

Latin Squares

Definition
A Latin square of order n is an n × n matrix (aij ) of elements from an n
element set A, such that each member of A occurs exactly once in each
row and each column of the matrix.

The figure shows a Latin square of order 4:

a b c d
d c a b
b a d c
c d b a

From the theorem, Latin squares are in an obvious one-to-one

correspondence with quasigroups by using Cayley tables.

George Voutsadakis (LSSU) Universal Algebra June 2020 16 / 44

 Selected Topics Orthogonal Latin Squares

Subsection 3

Orthogonal Latin Squares

George Voutsadakis (LSSU) Universal Algebra June 2020 17 / 44

 Selected Topics Orthogonal Latin Squares

Orthogonal Latin Squares

Definition
If (aij ) and (bij ) are two Latin squares of order n with entries from a set A
with the property that, for each 〈a, b 〉 ∈ A × A, there is exactly one index ij,
such that 〈a, b 〉 = 〈aij , bij 〉, then we say that (aij ) and (bij ) are orthogonal
Latin squares.
The figure shows an example of orthogonal Latin squares of order 3.
a b c a b c
b c a c a b
c a b b c a
Euler conjectured that, if n ≡ 2 (mod 4), then there do not exist
orthogonal Latin squares of order n.
In 1900 Tarry verified the conjecture for n = 6
Macneish gave a construction for all orders n, where n 6≡ 2 (mod 4).
Bose, Parker, and Shrikhande showed that n = 2, 6 are the only values
for which Euler’s conjecture is actually true.
George Voutsadakis (LSSU) Universal Algebra June 2020 18 / 44
 Selected Topics Orthogonal Latin Squares

Pairs of Orthogonal Latin Squares

Two orthogonal ±Latin ²
squares ±on a² set A correspond to two
quasigroups 〈A, , ·, 〉 and 〈A, ◦, ◦, ◦〉, such that the map
〈a, b 〉 7→ 〈a · b , a ◦ b 〉 is a permutation of A × A.
For a finite set A, this will be a bijection iff there exist functions ∗ℓ
and ∗r from A × A to A, such that ∗ℓ (a · b , a ◦ b) = a, ∗r (a · b , a ◦ b) = b.
Definition (Evans)
± ²± ²
A pair of orthogonal Latin squares is an algebra 〈A, , ·, , ◦, ◦, ◦, ∗ℓ , ∗r 〉,
with eight binary operations such that:
± ²
(i) 〈A, , ·, 〉 is a quasigroup;
± ²
(ii) 〈A, ◦, ◦, ◦〉 is a quasigroup;
(iii) ∗ℓ (x · y , x ◦ y ) ≈ x;
(iv) ∗r (x · y , x ◦ y ) ≈ y .
The order of such an algebra is the cardinality of its universe. Let POLS
be the variety of pairs of orthogonal Latin squares.
George Voutsadakis (LSSU) Universal Algebra June 2020 19 / 44
 Selected Topics Orthogonal Latin Squares

Existence of POLS of Prime Power

Lemma
If q is a prime power and q ≥ 3, then there is a member of POLS of order q.

Let 〈K , +, ·〉 be a finite field of order q, and let e1 , e2 be two distinct

nonzero elements of K . Then define two binary operations ä1 and ä2
on K by
aäi b = ei · a + b , i = 1, 2.

Claim: The two groupoids 〈K , ä1 〉 and 〈K , ä2 〉 are quasigroups.

aäi c = b iff c = b − ei · a, and d äi a = b iff d = ei−1 · (b − a).
Also we have that 〈aä1 b , aä2 b 〉 = 〈c ä1 d , c ä2 d 〉 implies
e1 · a + b = e1 · c + d, e2 · a + b = e2 · c + d. Hence, e1 · (a − c) = d − b,
e2 · (a − c) = d − b. Thus, as e1 6= e2 , a = c and b = d.
Thus, the Cayley tables of 〈K , ä1 〉 and 〈K , ä2 〉 give rise to orthogonal
Latin squares of order q.
George Voutsadakis (LSSU) Universal Algebra June 2020 20 / 44
 Selected Topics Orthogonal Latin Squares

Existence of POLS

Theorem
If n ≡ 0, 1, or 3 (mod 4), then there is a pair of orthogonal Latin squares of
order n.
Note that n ≡ 0, 1 or 3 (mod 4) iff n = 2α p1α1 · · · pkαk , with α 6= 1, αi ≥ 1,
and each pi is an odd prime.
The case n = 1 is trivial;
For n ≥ 3, use the preceding lemma to construct A0 , A1 , . . . , Ak in POLS
of order 2α , p1α1 , . . . , pkαk respectively.
Then A0 × A1 × · · · × Ak is the desired algebra.

George Voutsadakis (LSSU) Universal Algebra June 2020 21 / 44

 Selected Topics Orthogonal Latin Squares

The Class IPOLS

Definition
An algebra A = 〈A, F 〉 is a binary algebra if each of the fundamental
operations is binary.
A binary algebra A = 〈A, F 〉 is idempotent if f (x , x) ≈ x holds in A, for
each function symbol f .

Definition
Let IPOLS be the variety of idempotent algebras in POLS.

George Voutsadakis (LSSU) Universal Algebra June 2020 22 / 44

 Selected Topics Orthogonal Latin Squares

Binary Idempotent Varieties and 2-Designs

Definition
A variety V of algebras is binary idempotent if:
(i) the members of V are binary idempotent algebras;
(ii) V can be defined by identities involving at most two variables.

Note that IPOLS is a binary idempotent variety.

Definition
A 2-design is a tuple 〈B , B1 , . . . , Bk 〉 where:
(i) B is a finite set;
(ii) each Bi is a subset of B (called a block);
(iii) |Bi | ≥ 2, for all i;
(iv) each two-element subset of B is contained in exactly one block.

George Voutsadakis (LSSU) Universal Algebra June 2020 23 / 44

 Selected Topics Orthogonal Latin Squares

2-Designs and Binary Idempotent Algebras in a Variety

Lemma
Let V be a binary idempotent variety and let 〈B , B1 , . . . , Bk 〉 be a 2-design.
Let n = |B |, ni = |Bi |. If V has members of size ni , 1 ≤ i ≤ k, then V has a
member of size n.

Let Ai ∈ V , with |Ai | = ni . We can assume Ai = Bi . Then, for each

binary function symbol f in the type of V , we can find a binary
function f B on B, such that, when we restrict f B to Bi , it agrees with
f Ai (essentially we let f B be the union of the f Ai ). As V can be
defined by two variable identities p(x , y ) ≈ q(x , y ) which hold on each
Ai , it follows that we have constructed an algebra B in V , with
|B | = n.

George Voutsadakis (LSSU) Universal Algebra June 2020 24 / 44

 Selected Topics Orthogonal Latin Squares

Existence of IPOLS of Prime Power Order

Lemma
If q is a prime power and q ≥ 4, then there is a member of IPOLS of size q.
In particular, there are members of sizes 5, 7 and 8.

Let K be a field of order q, let e1 , e2 be two distinct elements of

K − {0, 1}.
Define two binary operations ä1 , ä2 on K by

aäi b = ei · a + (1 − ei ) · b .

aäi c = b iff ei · a + (1 − ei ) · c = b iff c = (1 − ei )−1 (b − ei · a)

d äi a = b iff ei · d + (1 − ei ) · a = b iff d = ei−1 (b − (1 − ei ) · a);
aäi a = ei · a + (1 − ei ) · a = a.
Thus, the Cayley tables of 〈K , ä1 〉 and 〈K , ä2 〉 give rise to idempotent
Latin squares.
George Voutsadakis (LSSU) Universal Algebra June 2020 25 / 44
 Selected Topics Orthogonal Latin Squares

Existence of IPOLS of Prime Power Order (Cont’d)

If aä1 b = c ä1 d and aä2 b = c ä2 d, we get

e1 · a + (1 − e1 ) · b = e1 · c + (1 − e1 ) · d and
e2 · a + (1 − e2 ) · b = e2 · c + (1 − e2 ) · d, whence
e1 · (a − c) = (1 − e1 ) · (d − b) and e2 · (a − c) = (1 − e2 ) · (d − b). Since
e1 , e2 6= 0, 1 and e1 6= e2 , we must have a = c and b = d.
Hence, the Cayley tables of 〈K , ä1 〉 and 〈K , ä2 〉 give rise to an
idempotent pair of orthogonal Latin squares.

George Voutsadakis (LSSU) Universal Algebra June 2020 26 / 44

 Selected Topics Orthogonal Latin Squares

Projective Plane of Order n

Given a finite field F of cardinality n, we form a projective plane P n

of order n by letting:
the points be the 1-dimensional subspaces U of the vector space F 3 ;
the lines be the 2-dimensional subspaces V of F 3 .
A point U belongs to a line V if U ⊆ V .
One can readily verify that:
every line of P n has n + 1 points;
every point of P n belongs to n + 1 lines;
there are n2 + n + 1 points and n2 + n + 1 lines.
Finally, we have:
Any two distinct points belong to exactly one line;
Any two distinct lines meet in exactly one point.

George Voutsadakis (LSSU) Universal Algebra June 2020 27 / 44

 Selected Topics Orthogonal Latin Squares

An IPOL of Order 54

Lemma
There is a 2-design 〈B , B1 , . . . , Bk 〉, with |B | = 54 and |Bi | ∈ {5, 7, 8}, for
1 ≤ i ≤ k.

Let π be the projective plane of order 7. This has 57 points and each
line contains 8 points. Choose three points on one line and remove
them. Let B be the set of the remaining 54 points, and let the Bi be
the sets obtained by intersecting the lines of π with B. Then
〈B , B1 , . . . , Bk 〉 is easily seen to be a 2-design, since each pair of points
from B lies on a unique line of π, and |Bi | ∈ {5, 7, 8}.
Theorem
There is an idempotent pair of orthogonal Latin squares of order 54.
Combine the preceding three lemmas.

George Voutsadakis (LSSU) Universal Algebra June 2020 28 / 44

 Selected Topics Finite State Acceptors

Subsection 4

Finite State Acceptors

George Voutsadakis (LSSU) Universal Algebra June 2020 29 / 44

 Selected Topics Finite State Acceptors

Finite State Acceptors and Unary Terms

Definition
A finite state acceptor (abbreviated f.s.a.) of type F (where the type is
finite with unary symbols) is a 4-tuple A = 〈A, F , a0 , A0 〉, where:
〈A, F 〉 is a finite unary algebra of type F ;
a0 ∈ A;
A0 ⊆ A.
The set A is the set of states of A, a0 is the initial state, and A0 is the
set of final states.

Definition
If we are given a finite type F of unary algebras, let 〈F ∗ , ·, 1〉 be the
monoid of strings on F . Given a string w ∈ F ∗ , an f.s.a. A of type F , and
an element a ∈ A, let w (a) be the element resulting from applying the
“term” w (x) to a. E.g., if w = fg , then w (a) = f (g (a)), and 1(a) = a.
George Voutsadakis (LSSU) Universal Algebra June 2020 30 / 44
 Selected Topics Finite State Acceptors

Accepted Languages and Regular Languages

Definition
A language of type F is a subset of F ∗ . A string w from F ∗ is
accepted by an f.s.a. A = 〈A, F , a0 , A0 〉 of type F if w (a0 ) ∈ A0 .
The language accepted by A, written L (A), is the set of strings from
F ∗ accepted by A.

Definition
Given languages L, L1 and L2 of type F let
L1 · L2 = {w1 · w2 : w1 ∈ L1 , w2 ∈ L2 },
L∗ = the subuniverse of 〈F ∗ , ·, 1〉 generated by L.
The set of regular languages of type F is the smallest collection of
subsets of F ∗ which contains the singleton languages {f }, f ∈ F ∪ {1}, and
is closed under the set-theoretic operations, ∪, ∩, ′ and the operations · and
∗
, defined above.
George Voutsadakis (LSSU) Universal Algebra June 2020 31 / 44
 Selected Topics Finite State Acceptors

Partial Algebras and Partial f.s.a.’s

Definition
A partial unary algebra of type F is a pair 〈A, F 〉, where F is a family of
partially defined unary functions on A indexed by F , i.e., the domain and
range of each function f are contained in A.

Definition
A partial finite state acceptor (partial f.s.a.) A = 〈A, F , a0 , A0 〉 of type
F has the same definition as an f.s.a. of type F , except that we only
require that 〈A, F 〉 be a partial unary algebra of type F .
The language accepted by A, L (A), is defined as for an f.s.a. (but, for
a given w ∈ F ∗ , w (a) might not be defined, for some a ∈ A).

George Voutsadakis (LSSU) Universal Algebra June 2020 32 / 44

 Selected Topics Finite State Acceptors

Languages Accepted by Partial f.s.a’s and Ranges

Lemma
Every language accepted by a partial f.s.a. is accepted by some f.s.a.

Let A = 〈A, F , a0 , A0 〉 be a partial f.s.a. Choose b 6∈ A and let

B = A ∪ {b }. For f ∈ F and a ∈ A ∪ {b }, if f (a) is not defined in A, let
f (a) = b. This gives an f.s.a. which accepts the same language as A.

Definition
If 〈A, F , a0 , A0 〉 is a partial f.s.a., then, for a ∈ A and w ∈ F ∗ , the range of
w applied to a, written Rg(w , a), is the set
½ © ª
fn (a), fn−1 fn (a), . . . , f1 · · · fn (a) , if w = f1 · · · fn
Rg(w , a) =
{a}, if w = 1

George Voutsadakis (LSSU) Universal Algebra June 2020 33 / 44

 Selected Topics Finite State Acceptors

f.s.a.’s and Regular Languages

Lemma
The language accepted by any f.s.a. is regular.

Let L be the language of the partial f.s.a. A = 〈A, F , a0 , A0 〉. We will

prove the lemma by induction on |A|.
First note that ; is a regular language as ; = {f } ∩ {f }′ , for any f ∈ F .
For the ground case suppose |A| = 1. If A0 = ;, then L (A) = ;, a
regular language. If A0 = {a0 }, let G = {f ∈ F : f (a0 ) is defined}. Then
L (A) = G ∗ = ( f ∈G {f })∗ , also a regular language.
S

For the induction step assume that |A| > 1, and for any partial f.s.a.
B = 〈B , F , b0 , B0 〉, with |B | < |A| the language L (B) is regular. If
A0 = ;, then, as before, L (A) = ;, a regular language. So assume
A0 6= ;. The crux of the proof is to decompose any acceptable word
into: (a) a product of words which one can visualize as giving a
sequence of cycles when applied to a0 ; (b) followed by a noncycle,
mapping from a0 to a member of A0 if a0 6∈ A0 .

George Voutsadakis (LSSU) Universal Algebra June 2020 34 / 44

 Selected Topics Finite State Acceptors

f.s.a.’s and Regular Languages (Cont’d)

Let C = {〈f1 , f2 〉 ∈ F × F : f1 wf2 (a0 ) =
a0 , for some w ∈ F ∗ , f2 (a0 ) 6= a0 and
Rg(w , f2 (a0 )) ⊆ A − {a0 }}. For 〈f1 , f2 〉 ∈
C , let Cf1 f2 = {w ∈ F ∗ : f1 wf2 (a0 ) =
a0 , Rg(w , f2 (a0 )) ⊆ A − {a0 }}. Then Cf1 f2
is the language accepted by
〈A − {a0 }, F , f2 (a0 ), f −1 (a0 ) − {a0 }〉. Hence, by induction, Cf1 f2 is regular.
Set H = {f ∈ F : f (a0 ) = a0 } ∪ {1}, D = {f ∈ F : f (a0 ) 6= a0 }. For f ∈ D ,
let Ef = {w ∈ F ∗ : wf (a0 ) ∈ A0 , Rg(w , f (a0 )) ⊆ A − {a0 }}. We see that
Ef is the language accepted by 〈A − {a0 }, F , f (a0 ), A0 − {a0 }〉. Hence, by
induction, it is also regular. Let

if a0 6∈ A0
½ S
E · {f },
E= Sf ∈D f .
( f ∈D Ef · {f }) ∪ {1}, if a0 ∈ A0

Then L = E · (H ∪ 〈f1 ,f2 〉∈C {f1 } · Cf1 f2 · {f2 })∗ , a regular language.
S

George Voutsadakis (LSSU) Universal Algebra June 2020 35 / 44

 Selected Topics Finite State Acceptors

Deletion Homomorphisms
Definition
Given a type F , t 6∈ F , the deletion homomorphism δt : (F ∪ {t })∗ → F ∗
is the homomorphism defined by δt (f ) = f , for f ∈ F , δt (t) = 1.

Lemma
If L is a language of type F ∪ {t }, where t 6∈ F , which is also the language
accepted by some f.s.a., then δt (L) is a language of type F which is the
language accepted by some f.s.a.
Let A = 〈A, F ∪ {t }, a0 , A0 〉 be an f.s.a. with L (A) = L. For w ∈ F ∗ ,
define Sw = {w (a0 ) : w ∈ (F ∪ {t })∗ , δt (w ) = w }, B = {Sw : w ∈ F ∗ }.
This is of course finite as A is finite. For f ∈ F , define f (Sw ) = Sfw .
This makes sense as Sfw depends only on Sw , not on w . Next let
b0 = S1 , and let B0 = {Sw : Sw ∩ A0 6= ;}. Then 〈B , F , b0 , B0 〉 accepts w
iff w (S1 ) ∈ B0 iff Sw ∩ A0 6= ; iff w (a0 ) ∈ A0 , for some w ∈ δ− 1
t (w ), iff
−1
w ∈ L, for some w ∈ δt (w ), iff w ∈ δt (L).
George Voutsadakis (LSSU) Universal Algebra June 2020 36 / 44
 Selected Topics Finite State Acceptors

Kleene’s Theorem

Theorem (Kleene)
Let L be a language. Then L is the language accepted by some f.s.a. iff L
is regular.

(⇒) This has already been proven.

(⇐) By induction.
f
If L = {f }, then we can use the partial f.s.a. a ←− a0 , where all functions
not drawn are undefined, and A0 = {a}.
If L = {1} use A = A0 = {a0 }, with all f ’s undefined.
Next suppose L1 is the language of 〈A, F , a0 , A0 〉 and L2 is the language
of 〈B , F , b0 , B0 〉. Then L1 ∩ L2 is the language of
〈A × B , F , 〈a0 , b0 〉, A0 × B0 〉, where f (〈a, b 〉) is defined to be 〈f (a), f (b)〉.
L′1 is the language of 〈A, F , a0 , A − A0 〉.
Combining these we see by De Morgan’s law that L1 ∪ L2 is the
language of a suitable f.s.a..

George Voutsadakis (LSSU) Universal Algebra June 2020 37 / 44

 Selected Topics Finite State Acceptors

Kleene’s Theorem (Cont’d)

To handle L1 · L2 , we first expand our type

to F ∪ {t }. Then, mapping each member
of B0 to the input of a copy of A, we see
that L1 ·{t }·L2 is the language of some f.s.a.
Hence, if we use the preceding lemma, it
follows that L1 · L2 is the language of some
f.s.a..
Similarly for L∗1 , let t map each element of
A0 to a0 . Then (L1 ·{t })∗ ·L1 is the language
of this partial f.s.a.; Hence,

L∗1 = δt [(L1 · {t })∗ · L1 ∪ {1}]

is the language of some f.s.a..

George Voutsadakis (LSSU) Universal Algebra June 2020 38 / 44

 Selected Topics Finite State Acceptors

Monoid of Words and Free Algebra

Definition
Let τ be the mapping from F ∗ to T (x), the set of terms of type F over
x, defined by τ(w ) = w (x).

Lemma
The mapping τ is an isomorphism between the monoid 〈F ∗ , ·, 1〉 and the
monoid 〈T (x), ◦, x 〉, where ◦ is “composition”.

If w1 6= w2 , then, in T (x), w1 (x) 6= w2 (x). Thus τ is 1-1;

If w (x) ∈ T (x), then τ(w ) = w (x) and τ is also onto.
Thus τ is a bijection.
Finally, we have
τ(1) = 1(x) = x;
τ((f1 · · · fn ) · (g1 · · · gm )) = f1 (· · · (fn (g1 · · · (gm (x)) · · · )) · · · ) =
(f1 · · · fn )((g1 · · · gm )(x)) = τ(f1 · · · fn ) ◦ τ(g1 · · · gm ).
George Voutsadakis (LSSU) Universal Algebra June 2020 39 / 44
 Selected Topics Finite State Acceptors

Congruences

Definition
For θ ∈ Con〈F ∗ , ·, 1〉, let θ(x) = {〈w1 (x), w2 (x)〉 : 〈w1 , w2 〉 ∈ θ}.

Lemma
The map θ 7→ θ(x) is a lattice isomorphism from the lattice of congruences
on 〈F ∗ , ·, 1〉 to the lattice of fully invariant congruences on T(x).

Suppose θ ∈ Con〈F ∗ , ·, 1〉 and 〈w1 , w2 〉 ∈ θ.

For u ∈ F ∗ , we have 〈uw1 , uw2 〉 ∈ θ. Thus, θ(x) is a congruence on
T(x).
For u ∈ F ∗ , we have 〈w1 u , w2 u 〉 ∈ θ. Hence, θ(x) is fully invariant.

George Voutsadakis (LSSU) Universal Algebra June 2020 40 / 44

 Selected Topics Finite State Acceptors

Acceptance by f.s.a.’s and Finite Index

Lemma
If L is a language of type F accepted by some f.s.a., then there is a
θ ∈ Con〈F ∗ , ·, 1〉, such that θ is of finite index (i.e., 〈F ∗ , ·, 1〉/θ is finite)
and Lθ = L, i.e., L is a union of cosets of θ.
Choose A an f.s.a. of type F , such that L (A) = L. Let FA (x) be the
free algebra freely generated by x in the variety V (〈A, F 〉). Let
α : T(x) → FA (x) be the natural homomorphism defined by α(x) = x,
and let β : FA (x) → 〈A, F 〉 be the homomorphism defined by β(x) = a0 .
Then, with L(x) = {w (x) : w ∈ L},
L(x) = α−1 (β−1 (A0 )) =
[
p/kerα.
p ∈β−1 (A0 )

Hence, L(x) = L(x)ker α . But kerα is a fully invariant congruence on

T(x). Thus, kerα = θ(x), for some θ ∈ Con〈F ∗ , ·, 1〉. Hence,
L(x) = L(x)θ(x ) and L = Lθ . We know kerα is of finite index. Thus, θ
is also of finite index.
George Voutsadakis (LSSU) Universal Algebra June 2020 41 / 44
 Selected Topics Finite State Acceptors

Myhill’s Theorem
Theorem (Myhill)
Let L be a language of type F . Then L is the language of some f.s.a. iff
there is a θ ∈ Con〈F ∗ , ·, 1〉 of finite index such that Lθ = L.

(⇒) This was proved by the preceding lemma.

(⇐) Suppose θ is a congruence of finite index on F ∗ , such that Lθ = L. Let
A = {w /θ : w ∈ F ∗ }, f (w /θ) = fw /θ, for f ∈ F ,
a0 = 1/θ, A0 = {w /θ : w ∈ L}.
We have
〈A, F , a0 , A0 〉 accepts w iff w (1/θ) ∈ A0
iff w /θ ∈ A0
iff w /θ = u/θ for some u ∈ L
iff w ∈ L.

George Voutsadakis (LSSU) Universal Algebra June 2020 42 / 44

 Selected Topics Finite State Acceptors

Equivalence of Words Modulo a Language

Definition
Given a language L of type F , define the binary relation ≡L on F ∗ by
w1 ≡L w2 iff (uw1 v ∈ L ⇔ uw2 v ∈ L, for u , v ∈ F ∗ ).

Lemma
If we are given L, a language of type F , then ≡L is the largest congruence
θ on 〈F ∗ , ·, 1〉, such that Lθ = L.
≡L is an equivalence relation on F ∗ . If w1 ≡L w2 and t1 ≡L t2 , then for
u , v ∈ F ∗ , uw1 t1 v ∈ L iff uw1 t2 v ∈ L iff uw2 t2 v ∈ L. Hence,
w1 t1 ≡L w2 t2 and ≡L is a congruence on 〈F ∗ , ·, 1〉.
Suppose w ∈ L and w ≡L t. Then 1 · w · 1 ∈ L ⇔ 1 · t · 1 ∈ L implies
t ∈ L. Hence, w /≡L ⊆ L. Thus, L≡L = L.
Finally, suppose Lθ = L. Then, for 〈w1 , w2 〉 ∈ θ and u , v ∈ F ∗ ,
〈uw1 v , uw2 v 〉 ∈ θ , whence, since uw1 v /θ = uw2 v /θ , we obtain
uw1 v ∈ L ⇔ uw2 v ∈ L. So w1 ≡L w2 . Hence, θ ⊆ ≡L .
George Voutsadakis (LSSU) Universal Algebra June 2020 43 / 44
 Selected Topics Finite State Acceptors

The Syntactic Monoid and Regular Languages

Definition
If we are given a language L of type F , then the syntactic monoid ML of
L is defined by
ML = 〈F ∗ , ·, 1〉/≡L .

Theorem
A language L is accepted by some f.s.a. iff ML is finite.

Lis accepted by some f.s.a. iff, by Myhill’s Theorem, there exists

θ ∈ Con〈F ∗ , ·, 1〉 of finite index, such that Lθ = L, iff, by the preceding
lemma, L≡L has finite index iff ML = 〈F ∗ , ·, 1〉/≡L is finite.

George Voutsadakis (LSSU) Universal Algebra June 2020 44 / 44