□

We can abstract from Example 1.23 the pattern for all mutual inductions;

Each of the statements must be proved separately in the basis and in the inductive step.

If the statements are if-and-only-if, then both directions of each statement must be proved, both in the basis and in the induction.

1.5 The Central Concepts of Automata Theory

In this section we shall introduce the most important definitions of terms that pervade the tlieory of automata. These concepts include the alphabet (a set of symbols), strings (a list of symbols from an alphabet), and language (a set of strings from the same alphabet).

1.5.1 Alphabets

An alphabet is a fiiute, nonempty set of symbols. Conventionally, we use the symbol E for an alphabet. Common alphabets include:

1. S = {0,1}, the binary alphabet.

1. [Si{n + 1); If] The hypothesis for this part is that n + 1 is even. Thus. n is odd. The if part of statement 82(71) saya that after n pushes, the automaton is in state on. The arc from on to off labeled Push tells us that the (n + l)st push will cause the automaton to enter state off. That completes the proof of the if part of Si{n + 1).

2. [Si{n + 1); Only-if] The hypothesis is that the automaton is in state off after n + 1 pushes. Lispecting the automaton of Fig, 1.8 tells us that the only way to get to state off after one or more moves is to be in state on and receive an input Push. Thus, if we are in state ojflafter n + I pushes, we must have been in state on after n pushes. Then, we may use the only-if part of statement S2{n) to conclude that n is odd. Consequently, n + 1 is even, whicli is the desired conclusion for the only-if portion of Si{n + 1).

3. [S2{n+l)\ If] This part is essentially the same as part (1), with the roles of statemtints and 2 exchanged, and with the roles of odd and even exchanged. The reader should be able to construct this part of the proof easily,

4. [S2in + 1); Only-if] This part is essentially the same as part (2), with the roles of statements 5i and S2 exchanged, and with the roles of odd and even exchanged.

1.5.2 Strings

A string (or sometimes wo7-d) is a finite sequence of symbols chosen from some alphabet. For example, 01101 is a string from the binary alphabet S = {0,1}, The string 111 is another string chosen from this alphabet.

The Empty String

The empty stHng is the string with zero occurrences of symbols. This string, denoted e, is a string that may be chosen from any alphabet whatsoever.

Length of a String

It is often useful to classify strings by their length, that is, the number of positions for symbols in the string. For instance, 01101 has length 5, It is common to say that the length of a string is the number of symbols in the string; this statement is colloquially accepted but not strictly correct. Thus, there are only two symbols, 0 and 1, in the string 01101, but there are five positions for symbols, and its length is 5, However, you should generally expect that -the number of symbols can be used when number of positions is meant. The standard notation for the length of a string w is \vj\. For example, 011( = 3 and \€\ = 0.

Powers of an Alphabet

If S is an alphabet, we can express the set of all strings of a certain length from that alphabet by using an exponential notation. We define to be the set of strings of length fc, each of whose symbols is in S.

Example 1.24: Note that TP ~ {e}, regardless of what alphabet E is. That is, e is the only string whose length is 0,

If S - (0,1), then - {0,1}, = {00,01,10,11},

= {ООО,001,010,011,100,101,110,111}

and so on. Note that there is a slight confusion between E and E. The former is an alphabet; its members 0 and 1 are symbols. The latter is a set of strings; its members are the strings 0 and 1, each of which is of length 1. We shall not try to use separate notations for the two sets, reljing on context to make it clear whether {0,1} or similar sets are alphabets or sets of strings. □

2. E = {a,6, ...,2}, the set of all lower-case letters.

3. The set of all ASCII characters, or the set of all printable ASCII characters.

Type Convention for Symbols and Strings

Commonly, we shall use lower-case letters at the beginiiuig of the alphabet (or digits) to denote symbols, and lower-case letters near the end of the alphabet, typically x, y, and to denote strings. You should try to get used to this convention, to help remind you of the types of the elements being discussed.

The set of all strings over an alphabet E is conventionally denoted S*. For instance, {0,1}* = {б,0,1,00,01,10,11,000,...}. Put another way,

= S и E и и

Sometunes, we wish to exclude the empty string from the set of strings. The set of nonempty strings from alphabet E is denoted E. Thus, two appropriate equivalences are:

. E+-E USUEU---. . E* = E+U{e}.

Concatenation of Strings

Let x and у be strings. Then xy denotes the concatenation of x and y, that is, the string formed by making a copy of x and following it by a copy of y. More precisely, if x is the string composed of г symbols x = oia - --ai and у is the string composed of j symbols у = bb-i - bj, then xy is the string of length i+ j: xy = aia-2 ajbibi --bj.

Example 1.25: Let x = 01101 and у = 110. Then xy = 01101110 and yx - 11001101. For any string w., the equations ew = we = m hold. That is, e is the identity for concatenation, since when concatenated with any string it yields the other string as a result (analogously to the way 0, the identity for addition, can be added to any number x and yields x as a result). □

1,5.3 Languages

A set of strings all of which are cho.sen from some £*, where E is a particular alphabet, is called a language. If S is an alphabet, and £ С E*, then L is a language over E. Notice that a langnage over E need not include strings with all the symbols of E, so once we have established that i is a language over E, we also know it is a language over any alphabet that is a superset of E.

The choice of the term language may seem strange. However, common languages can be viewed as sets of strings. .An example is English, where the