CHAPTER II

Preliminaries

Before starting on the main body of this thesis a brief review is given of common definitions and known results relevant to this work.

2.1 Star-Free Regular Events

Regular events and regular expressions are well known for their usefulness in describing the behaviour of sequential circuits [1, 2, 3]. Since this thesis is concerned with a subclass of regular events we require some concepts from the theory of regular events.

Consider sets of finite sequences of symbols from a finite alphabet A={a₁, a₂, ..., a_n}. These sets will be called events or languages. Each finite sequence of symbols is called a word. The empty set of words is called the empty event φ. The word consisting of no symbols is called the empty word λ. If P and Q are any two events, then the following operations are defined:

1. union (+), a binary operation such that event P+Q={w|w∈P or w∈Q or both},
2. concatenation (⋅), a binary operation such that event P⋅Q={w|w=uv, u∈P, v∈Q},
   (the dot is usually omitted for convenience,)
3. complement ('), a unary operation such that event P'={w|w∉P},
4. star (*), a unary operation such that event P*=Σ_n=0^∞Pⁿ, where Pⁿ=PPP...P, n times when n>0, and P⁰={λ}.

It is easily shown that union is associative and commutative, that concatenation is associative, and that concatenation distributes over union. The following special relationships can also be shown:

A regular expression over alphabet A={a₁, a₂, ..., a_n} is defined inductively. Let λ and φ be two distinct symbols not in A. Let (+) and (⋅) be binary operations and let (') and (*) be unary operations. The inductive definition of a regular expression is:

1. a₁, a₂, ..., a_n, λ and φ are regular expressions,
2. if P and Q are regular expressions then so are P+Q, PQ, P' and P*,
3. nothing else is a regular expression.

Regular expressions denote events according to the mapping from regular expressions to events:

An event P is regular if, and only if, there exists a regular expression R such that |R|⇒P.

Star-free events are those regular events which can be denoted by a regular expression without using the star operation. The class of star-free events will be denoted by the abbreviation SF. Obviously, the class of star-free events is contained in the class of regular events. It will be shown later by counter example that the containment is proper. Considering an alphabet A={0, 1}, the following are examples of regular expressions:

The last example is a very useful one as 0+1 is the union of all the symbols in the alphabet and may be represented by A=0+1. Taking the star operation of the alphabet gives us all the possible words over the alphabet. For this reason this is also given a special symbol I=A*=(0+1)*. Now we have I, the set of all possible words over alphabet A and φ the empty set. We can see that although I was initially defined as a star expression I=A*, it can also be represented as a star-free expression I=φ'. Other examples of such identities are:

Consider the first example. 1* denotes the event consisting of the empty word λ and every word containing only ones. I0I denotes the event consisting of all words which start with any word, are followed by a zero and end with any word. Since I denotes all words, including λ, it can be seen that I0I denotes all words containing at least one zero. Since the alphabet A = {0, 1} contains only zero and one, it is obvious that the two expressions 1* and I0I are complementary, hence 1* = (I0I)'. Since the event denoted by 1* can be expressed without using a star it is a star-free event. For events denoted by more complex expressions with stars it is more difficult to determine whether there exists an equivalent star-free expression or not. A simple test for the star-free property will be given later.

2.2 Non-Counting Regular Events

Papert and McNaughton have defined a class of events called non-counting events [4]. These are basically events for which the membership of a word in the event may be tested without counting beyond some finite threshold. It is obvious that even counting modulo some integer is excluded from these events. The formal definition of a non-counting event is as follows:

The class of non-counting events is denoted by NC. It can be shown [8] that every star-free event is a non-counting event, that is SF⊆NC.

• Theorem 2.2.1 Every star-free event is a non-counting event.
  
  Proof: By induction on the number of operators. In the expression defining the event:
  
  
  1. φ, {λ} and A={a₁, a₂, ..., a_n} are trivially in NC.
  2. Let events P and Q be in NC. Then for any v, w, x in A* there exist some integers k and h such that vw^kx is in P if and only if vw^k+1x is in P and vw^hx is in Q if and only if vw^h+1x is in Q. Assume vw^k+h+1x is in PQ. Now either there exists a y in Q such that vw^kw^h+1x = vw^kx₁y and vw^kx₁ is in P, or there exists a u in P such that vw^k+1w^hx = uv₁w^hx and v₁w^hx is in Q. In the first case if vw^kx₁ is in P then vw^k+1x₁ is in P. In the second case if v₁w^hx is in Q then v₁w^h+1x is in Q. In either case we see that vw^k+h+2x is in PQ. Conversely, by reversing the argument, we can show that if vw^k+h+2x is in PQ, then so is vw^k+h+1x. Hence PQ is in NC.
  3. Let events P and Q be in NC. Then for any v, w, x in A* there exists some positive integer k such that vw^kx is in P if and only if vw^k+1x is in P and some h such that vw^hx is in Q if and only if vw^h+1x is in Q. Then obviously m=max(k,h) is an integer such that vw^mx is in P+Q if and only if vw^m+1x is in P+Q. Hence P+Q is in NC.
  4. If P is in NC then P' is obviously in NC. This completes the proof by induction.

2.3 Automata and Monoids

The definition of automata given below is based on Rabin and Scott [5].

A (finite state) automaton is a quintuple M={A,S,T,s₁,F} where:

The transition mapping T can be extended recursively over A* so that for all a in A and x in A*,

A reduced automaton is an automaton such that for every pair of states s_i, s_j in S, i≠j, there is some x in A* such that one but not both of T(s_i,x and T(s_j,x) is in F. An input sequence x in A* is accepted by automaton M if and only if T(s₁,x) is in F. An automaton M realizes an event R if and only if the set of sequences accepted by M is exactly R. It has been shown that the class of events realized by (finite state) automata is exactly the class of regular events, and algorithms exist for finding automata that realize any regular event and for finding regular events that are realized by any automaton [6, Appendix B]. For example consider an automaton that realizes the regular event R=(01)*:

Where T is defined as:

T may be depicted in tabular form as in figure 2.3.1a or in graphic form as in figure 2.3.1b.

Figure 2.3.1b
Flow Graph - Event (01)*

The successor of s_i under input a_j is T(s_i,a_j).

• Definition 2.3.1 The ordered successor set of a set S_i=(s_i1, s_i2, ..., s_in) under input a_m is the ordered set S_j=(s_j1, s_j2, ..., s_jn) such that each s_jk is the successor of s_ik under input a_m, that is s_jk=T(s_ik,a_m) for all k, 1≤k≤n.

Note that the mapping T may be extended so that T(s_i,a_m) is the ordered successor set S_j of S_i under a_m. In conjunction with the previous extension this defines T(S_i,xa)=T(T(S_i,x),a). When T(S,u)=T(S,v) for u, v in A* then u and v are said to be congruent modulo M, written as

It is clear then that this congruence relation defines a partition on A* and since the set A* of words is closed under concatenation, the set of congruence classes is also closed under concatenation. The empty input string λ acts as the unit for concatenation of words in A* and hence its congruence class will act as the unit for multiplication of the congruence classes. It is clear then that the congruence classes form a monoid under concatenation. This monoid is called the syntactic monoid of the automaton M. By finding all the ordered successor sets up to congruence mod M of the automaton M we can find the congruence classes. Taking the automaton from figure 2.3.1a we obtain the extended transition table shown in figure 2.3.2a.

By letting the first encountered member of a congruence class stand for its class we get a reduced table shown in figure 2.3.2b.

We introduce a convention here to distinguish between the congruence classes and the words they contain. Let w represent the congruence class containing the word w. We can now construct the multiplication table for the syntactic monoid, for this example shown in figure 2.3.2c.

2.4 Group-Free Monoids, Automata and Events

Schutzenberger [7] has developed the study of subgroups of a monoid. A subgroup of a monoid is a submonoid of that monoid whose elements form a group under the monoid operation. A monoid is said to be group-free if and only if all its subgroups are trivial, that is, have only one element. An automaton is group-free if and only if its syntactic monoid is group-free. An event is called group-free if and only if it is realized by a group-free automaton. The class of group-free events will be denoted by GF. The following theorem due to Meyer [8] defines a test for the group-free property.

• Theorem 2.4.1 If there exists an integer k≥0 such that w^k=w^k+1 for all elements w of the monoid, the monoid is group-free.
  
  Proof: Let u be any element of the monoid. If u is the member of a subgroup, then there exists a unit e in the subgroup and an inverse u^-1 such that uu^-1=e. If u^k=u^k+1 for some k then e=u^k(u^-1)^k=u^k+1(u^-1)^k=u. Hence u is the unit and the subgroup is trivial.

As an example consider the monoid of figure 2.3.2. By looking down the diagonal of the multiplication table in figure 2.4.1 we find that λ, 00, 01 and 10 satisfy w^k=w^k+1 for k=1.

These are called idempotents. We need now only test 0 and 1. We find 0²=0³ and 1²=1³, hence the automaton of figure 2.3.2 is group-free and (01)* is in GF.

To take another example consider R=(11)*, realized by M={A={0,1},S={A,B,C},T,s1=A,F={A}. Figure 2.4.2 shows (a) the state table representing the transition function T, (b) the congruence classes and (c) the monoid multiplication table.

It can readily be seen that there is a non-trivial group {1 , λ} around idempotent λ, because 1¹=1, 1²=λ, 1³=1, 1⁴=λ, etc. Note that Papert and McNaughton [4] have shown in a theorem that we need not go beyond the order of the monoid for a suitable k, that is beyond k=3 in this case. Even without that we can see in this case that there is no k such that 1^k=1^k+1. Hence (11)* is not in GF.

• Lemma 2.4.1 [4] Any finite monoid has a finite k≥0 such that w^k=w^2k for all w in the monoid. This k is called the order of the monoid.
  
  Proof: Every element w defines a power series w, w², w³, ... . Since the monoid is finite, eventually an element will be reached which has appeared earlier in the power series. Let n be the lowest integer such that wⁿ=w^m where n>m. Let q=n-m. Now w^m=wⁿ=w^m+q=w^mw^q. Hence w^m=w^mw^rq, where r is any positive integer. Let k=rq, an integral multiple of q such that m≤k≤n-1. Let p=k-m. Now w^k=w^pw^m=w^pw^mw^rq=w^pw^mw^k=w^2k. Hence w^k is an idempotent. Each element w in the monoid has an associated k_i such that w^k_i=w^2k_i. The lowest common multiple of all the k_i is the required order of the monoid.

• Theorem 2.4.2 [4] The class of group-free regular events is contained in the class of non-counting regular events.
  
  Proof: Suppose R is not in NC. Let k be the order of the syntactic monoid of the automaton M realizing the event R. Then by definition of NC, there exist words v, w and x in A* such that one but not both of vw^kx and vw^k+1x is in R. Let w be the congruence class of the syntactic monoid containing w. The by Lemma 2.4.1 w^k=w^2k and w^k+1=w^2k+1. Consider the cyclic subgroup {w^k+1, w^k+2, ..., w^2k}. If this subgroup is trivial w^k+1=w^k, hence vw^kx is in R if and only if vw^k+1 is in R, which is a contradiction. Therefore the subgroup is non-trivial and R is not in GF. Hence GF⊆NC.