1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 11
Текст из файла (страница 11)
An example is, naturally, the Roman alphabet {a, b, ... , z}. An alphabet particularlypertinent to the theory of computation is the binary alphabet {O, I}. In fact,any object can be in an alphabet; from a formal point of view, an alphabet issimply a finite set of any sort. For simplicity, however, we use as symbols onlyletters, numerals, and other common characters such as $, or #.A string over an alphabet is a finite sequence of symbols from the alphabet.Instead of writing strings with parentheses and commas, as we have written othersequences, we simply juxtapose the symbols.
Thus watermelon is a string overthe alphabet {a,b, ... ,z}, and 0111011 is a string over {O,I}. Also, using thenatural isomorphism, we identify a string of only one symbol with the symbolitself; thus the symbol a is the same as the string a. A string may have nosymbols at all; in this case it is called the empty string and is denoted bye.We generally use u, v, x, y, z, and Greek letters to denote strings; for example,we might use w as a name for the string abc.
Of course, to avoid confusion it isa good practice to refrain from using as symbols letters we also use as names ofstrings. The set of all strings, including the empty string, over an alphabet ~ isdenoted by ~*.The length of a string is its length as a sequence; thus the length of thestring acrd is 4. We denote the length of a string w by Iwl; thus 11011 = 3 andlei = O.
Alternatively (that is, via a natural isomorphism) a string w E ~* canbe considered as a function w : {I, ... , Iwl} H ~; the value of w(j), where 1 ~ j ~Iwl, is the symbol in the jth position of w. For example, if w = accordion, thenw(3) = w(2) = c, and w(I) = a. This alternative viewpoint brings out a possiblepoint of confusion. Naturally, the symbol c in the third position is identical tothat in the second. If, however, we need to distinguish identical symbols atdifferent positions in a string, we shall refer to them as different occurrencesof the symbol.
That is, the symbol a E ~ occurs in the jth position of the stringw E ~* if w(j) = a.Two strings over the same alphabet can be combined to form a third bythe operation of concatenation. The concatenation of strings x and y, writtenx 0 y or simply xy, is the string x followed by the string y; formally, w = x 0 y if431.7: Alphabets and Languagesand only if Iwl = Ixl + IYI, w(j) = x(j) for j = 1, ... , lxi, and w(lxl + j) = y(j)for j = 1, ...
, Iyl. For example, 010001 = 01001, and beach 0 boy = beachboy.Of course, woe = eo w = w for any string w. And concatenation is associative:(wx)y = w(xy) for any strings w, x, and y. A string v is a substring of a stringw if and only if there are strings x and y such that w = xvy. Both x and y couldbe e, so every string is a substring of itself; and taking x = wand v = y = e, wesee that e is a substring of every string. If w = xv for some x, then v is a suffixof w; if w = vy for some y, then v is a prefix of w.
Thus road is a prefix ofroadrunner, a suffix of abroad, and a substring of both these and of broader. Astring may have several occurrences of the same substring; for example, abababhas three occurrences of ab and two of abab.For each string wand each natural number i, the string wi is defined asthe empty stringwO =e,Wi+l =w i0wfor each i 2: 0Thus w l = w, and do 2 = dodo.This definition is our first instance of a very common type: definitionby induction. We have already seen proofs by induction, and the underlyingidea is much the same. There is a basis case of the definition, here the definitionof Wi for i = 0; then when that which is being defined has been specified forall j ~ i, it is defined for j = i + 1. In the example above, Wi+l is defined interms of wi.
To see exactly how any case of the definition can be traced backto the basis case, consider the example of do 2 • According to the definition (withi = 1), (do)2 = (do)l odo. Again according to the definition (with i = 0) (do)l =(do)O odo. Now the basis case applies: (do)O = e. So (do)2 = (eodo) odo = dodo.The reversal of a string w, denoted by w R , is the string "spelled backwards": for example, reverseR = esrever. A formal definition can be given byinduction on the length of a string:(1) If w is a string of length 0, then w R = w = e.(2) If w is a string of length n + 1 > 0, then w = ua for some a E ~, andw R = au R .Let us use this definition to illustrate how a proof by induction can dependon a definition by induction.
We shall show that for any strings wand x,(wx)R = xRw R . For example, (dogcat)R = (cat)R(dog)R = tacgod. We proceedby induction on the length of x.Basis Step. IxlxRw R .= O.Then x= e,and (wx)R= (we)R = w R = ew R = eRw R =Induction Hypothesis. If Ixl ~ n, then (wx)R = xRw R .Chapter 1: SETS, RELATIONS, AND LANGUAGES44IxlInduction Step. Letthat lui = n.= n(wx)R =(w(ua))R=((wu)a)RThen x = ua for some u E~*and a E~suchsince x = uasince concatenation is associativeby the definition of the reversal of (wu)a=a(wu)R=auRw Rby the induction hypothesis=(ua) Rw R=xRw R+ 1.by the definition of the reversal of uasince x= uaNow we move from the study of individual strings to the study of finite andinfinite sets of strings.
The simple models of computing machines we shall soonbe studying will be characterized in terms of regularities in the way they handlemany different strings, so it is important first to understand general ways ofdescribing and combining classes of strings.Any set of strings over an alphabet ~ --that is, any subset of ~'- will becalled a language. Thus ~', 0, and ~ are languages. Since a language is simplya special kind of set, we can specify a finite language by listing all its strings.For example, {aba, czr, d, f} is a language over {a, b, ... ,z}. However, mostlanguages of interest are infinite, so that listing all the strings is not possible.Languages that might be considered are {O,OI,Oll,OIll, ...}, {w E {O,I}* :w has an equal number of o's and I's}, and {w E ~* : w = w R }.
Thus we shallspecify infinite languages by the schemeL = {w E~*: w has property P},following the general form we have used for specifying infinite sets.If ~ is a finite alphabet, then ~. is certainly infinite; but is it a countablyinfinite set? It is not hard to see that this is indeed the case. To construct a bijection f : N f-t ~* , first fix some ordering of the alphabet, say ~ = {aI, ... , an},where aI, ... , an are distinct. The members of ~* can then be enumerated inthe following way.(1) For each k ~ 0, all strings of length k are enumerated before all strings oflength k + 1.(2) The n k strings oflength exactly k are enumerated lexicographically, thatis, ai, ... aik precedes aj, ...
ajk' provided that, for some Tn,Tnk - 1,if = if for £ = 1, ... , Tn, and im+l < jrn+l'°:sFor example, if~= {a, I}, the order would be as follows:e,O,I,OO,OI,IO,II,OOO,OOI,OIO,OII, ...:s451.7: Alphabets and LanguagesIf ~ is the Roman alphabet and the ordering of ~ = {al, ... , a26} is the usualone {a, ...
, z}, then the lexicographic order for strings of equal length is theorder used in dictionaries; however, the ordering described by (1) and (2) for allstrings in ~* differs from the dictionary ordering by listing shorter strings beforelonger ones.Since languages are sets, they can be combined by the set operations ofunion, intersection, and difference. When a particular alphabet ~ is understoodfrom context, we shall write A -the complement of A- instead of the difference ~. - A.In addition, certain operations are meaningful only for languages. The firstof these is the concatenation of languages. If LI and L2 are languages over~, their concatenation is L = LI oL 2, or simply L = L 1 L 2, whereL= {wE ~* :W=x0y for some x E LI and y E L 2}.For example, if ~ = {O, I}, LI = {w E ~* : W has an even number of O's} andL2 = {w : W starts with a 0 and the rest of the symbols are 1's}, then LI 0 L2 ={w : W has an odd number of O's}.Another language operation is the Kleene star of a language L, denotedby L *.
L * is the set of all strings obtained by concatenating zero or more stringsfrom L. (The concatenation of zero strings is e, and the concatenation of onestring is the string itself.) Thus,L*= {wE ~* : W= WI0 ... 0 Wkfor some k ::::: 0 and someWI •... ,WkE L}.For example, if L = {01, 1, 100}, then 110001110011 E L*, since 110001110011 =1 0 100001 0 1 0 1000 1 0 1, and each of these strings is in L.Note that the use of ~* to denote the set of all strings over ~ is consistentwith the notation for the Kleene star of ~, regarded as a finite language.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
