1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 12
Текст из файла (страница 12)
Thatis, if we let L = ~ and apply the definition above, then ~* is the set of all stringsthat can be written as WI 0 . . . 0 Wk for some k ::::: 0 and some WI, ... ,Wk E ~.Since the Wi are then simply individual symbols in ~, it follows that ~* is, asoriginally defined, the set of all finite strings whose symbols are in ~.For another extreme example, observe that 0* = {e}. For let L = 0 in theabove definition. The only possible concatenation WI 0 W2 0 ...
0 Wk with k ::::: 0and WI, ... ,Wk E L is that with k = 0, that is, the concatenation of zero strings;so the sole member of L' in this case is e!As a final example, let us show that if L is the language {w E {O, I} * :W has an unequal number of O's and l's}, then L* = {0,1}*. To see this, firstnote that for any languages LI and L 2, if LI ~ L 2, then Li ~ L2 as is evidentfrom the definition of Kleene star. Second, {O, I} ~ L, since each of 0 and 1,regarded as a string, has an unequal number of O's and 1 'so Hence {O, 1}* ~ L *;but L' ~ {O, I}' by definition, so L * = {O, 1}*.46Chapter 1: SETS, RELATIONS, AND LANGUAGESWe write L+ for the language LL*.
Equivalently, L+ is the language{w E~* : W=WI 0 W2 0 ... 0 Wkfor some k 2: 1 and someWI, ... , WkE L}.Notice that L+ can be considered as the closure of L under the function ofconcatenation. That is, L+ is the smallest language that includes L and allstrings that are concatenations of strings in L.Problems for Section 1.71. 7.1. (a) Prove, using the definition of concatenation given in the text, that concatenation of strings is associative.(b) Give an inductive definition of the concatenation of strings.(c) Using the inductive definition from (b), prove that the concatenationof strings is associative.1.
7 .2. Prove each of the following using the inductive definition of reversal givenin the text.(a) (wR)R = W for any string w.(b) If v is a substring of w, then v R is a substring of w R .(c) (wi)R = (wR)i for any string wand i 2: O.1. 7.3. Let ~ = {aI,' .. ,a26} be the Roman alphabet. Carefully define the binaryrelation < on ~* such that x < y if and only if x would precede y in astandard dictionary.1.
7.4. Show each of the following.(a)(b)(c)(d){e}* = {e}For any alphabet ~ and any L ~ ~*, (L*)* = L*.Ifa and b are distinct symbols, then {a,b}* = {a}*({b}{a}*)*.If ~ is any alphabet, e E LI ~~. and e E L2 ~ ~*, then (LI~*L2)* =~*.(e) For any language L, 0L = L0 =0.1.7.5. Give some examples of strings in, and not in, these sets, where(a) {w: for some u E ~~, w = uuRu}(b) {w: ww = www}(c) {w: for some u,v E ~*, uvw = wvu}(d) {w: for some u E ~*, www = uu}1.7.6. Under what circumstances is L+= L* -~= {a, b}.{e}?1.7.7.
The Kleene star of a language L is the closure of L under which relations?1.8: Finite Representations of Languages1.847FINITE REPRESENTATIONS OF LANGUAGESA central issue in the theory of computation is the representation of languagesby finite specifications. Naturally, any finite language is amenable to finite representation by exhaustive enumeration of all the strings in the language. Theissue becomes challenging only when infinite languages are considered.Let us be somewhat more precise about the notion of "finite representationof a language." The first point to be made is that any such representation mustitself be a string, a finite sequence of symbols over some alphabet ~.
Second, wecertainly want different languages to have different representations, otherwisethe term representation could hardly be considered appropriate. But these tworequirements already imply that the possibilities for finite representation areseverely limited. For the set ~* of strings over an alphabet ~ is count ablyinfinite, so the number of possible representations of languages is count ablyinfinite. (This would remain true even if we were not bound to use a particularalphabet ~, so long as the total number of available symbols was countablyinfinite.) On the other hand, the set of all possible languages over a givenalphabet ~ -that is, 2E * - is uncountably infinite, since 2N , and hence thepower set of any count ably infinite set is not count ably infinite.
With only acountable number of representations and an uncountable number of things torepresent, we are unable to represent all languages finitely. Thus, the most wecan hope for is to find finite representations, of one sort or another, for at leastsome of the more interesting languages.This is our first result in the theory of computation: No matter how powerful are the methods we use for representing languages, only countably manylanguages can be represented, so long as the representations themselves are finite. There being uncountably many languages in all, the vast majority of themwill inevitably be missed under any finite representational scheme.Of course, this is not the last thing we shall have to say along these lines.We shall describe several ways of describing and representing languages, eachmore powerful than the last in the sense that each is capable of describinglanguages the previous one cannot.
This hierarchy does not contradict the factthat all these finite representational methods are inevitably limited in scope forthe reasons just explained.We shall also want to derive ways of exhibiting particular languages thatcannot be represented by the various representational methods we study.
Weknow that the world of languages is inhabited by vast numbers of such unrepresent able specimens, but, strangely perhaps, it can be exceedingly difficult tocatch one, put it on display, and document it. Diagonalization arguments willeventually assist us here.To begin our study of finite representations, we consider expressions -48Chapter 1: SETS, RELATIONS, AND LANGUAGESstrings of symbols- that describe how languages can be built up by using theoperations described in the previous section.Example 1.8.1: Let L = {w E {O,I}*: whastwoorthreeoccurrencesof1,the first and second of which are not consecu ti ve }. This language can be described using only singleton sets and the symbols U, 0, and * as{O}*0{l} 0 {O}* 0 {O} 0 {I} 0 {Or0«{l} 0 {O}*) U 0*).It is not hard to see that the language represented by the above expression isprecisely the language L defined above.
The important thing to notice is that theonly symbols used in this representation are the braces { and }, the parentheses( and ), 0, 0, 1, *, 0, and U. In fact, we may dispense with the braces and 0 andwrite simplyL = 0*10*010*(10* U 0*).Roughly speaking, an expression such as the one for L in Example 1.8.1 iscalled a regular expression. That is, a regular expression describes a languageexclusively by means of single symbols and 0, combined perhaps with the symbolsU and *, possibly with the aid of parentheses. But in order to keep straight theexpressions about which we are talking and the "mathematical English" we areusing for discussing them, we must tread rather carefully.
Instead of using U,*, and 0, which are the names in this book for certain operations and sets, weintroduce special symbols U, *, and 0, which should be regarded for the momentas completely free of meaningful overtones, just like the symbols a, b, and 0 usedin earlier examples. In the same way, we introduce special symbols ( and )instead of the parentheses ( and ) we have been using for doing mathematics.The regular expressions over an alphabet I;* are all strings over the alphabetI; U {(,), 0, U,*} that can be obtained as follows.(1)(2)(3)(4)(5)0 and each member of I; is a regular expression.If a and f3 are regular expressions, then so is (af3).If a and f3 are regular expressions, then so is (aUf3).If a is a regular expression, then so is a*.Nothing is a regular expression unless it follows from (1) through (4).Every regular expression represents a language, according to the interpretation of the symbols U and * as set union and Kleene star, and of juxtaposition ofexpressions as concatenation.
Formally, the relation between regular expressionsand the languages they represent is established by a function £, such that if ais any regular expression, then £(a) is the language represented by a. That is,£ is a function from strings to languages. The function £ is defined as follows.1.8: Finite Representations of Languages49(1) £(0) = 0, and £(a) = {a} for each a E I:.(2) If a and (3 are regular expressions, then C«O'(3)) = £(O').c((3).(3) If a and (3 are regular expressions, then C«O'U(3)) = £(0') u C«(3).(4) If a is a regular expression, then £(0'*) = £(0')*.Statement 1 defines £(0') for each regular expression a that consists of asingle symbol; then (2) through (4) define .c(o') for regular expressions of some length in terms of £(0") for one or two regular expressions a' ofsmaller length.
Thus every regular expression is associated in this way withsome language.Example 1.8.2: What is £«(aUb)*a))? We have the following.£«(aUb)*a)) =C«aUb)*)C(a) by(2)=£«aUb)*){a} by (1)=£«aUb))*{a} by (4)=(.c(a) U £(b))*{a} by (3)=({a} U {b})*{a} by (1) twice={a,b}*{a}={w E {a,br : wends with an a}Example 1.8.3: What language is represented by (c*(aU(bc*))*)? This regularexpression represents the set of all strings over {a, b, c} that do not have thesubstring ac.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
