An introduction to formal languages and automata 3rd edition pdf

Contact Us. Upload eBook. Privacy Policy. New eBooks. Search Engine. An Introduction to Formal Languages and Automata. Skip carousel. Carousel Previous. Book Summary:Increas less formal writing style i, surely need it like.

One of them to outline and, also very good book forfurther studies they. Formal languages i've just my opinion. Skip to search form Skip to main content You are currently offline. Some features of the site may not work correctly. DOI: Hopcroft and J. Hopcroft , J. The authors present the theory in a concise and straightforward manner, with an eye out for the practical applications.

This book is an introduction to the theory of computation. Rajeev Motwani contributed to the , and later, edition. Solutions for Section 6. Solutions for Section 3. Hopcroft, John E. It has severtr,lA-trarrsitiotrs aud some unde- flned tra,nsitirlrrssuch as d q2,a.

Using as mir,ny. Definition 2. What is perltaps a little harder to scc is that this definition urn irlways be used to flnd d. Itr Section 1,1, we descrihcd art algorithm for finding all sirnple paths bctween two vertices.

We crr,nrrotuse this algorithm directly flirrce, as Ex- ilrnple 2. We catt ttrodify the sirnple path algorithrn, rernovirrg the restriction that no vettex or edge Figurc?. The new algorithrn will now generate successivelyall walks of length one, length two, length tlrree, arrd so on. There is still a difliculty. Given a ru, how lorrg can a walk labeled trr be? This is not immediately obvious. In Exa"rrrple 2.

The situation is saved by this obscrvation: If between two vertices r. The a,rgurnent for this is: While A-edges may be repeated, there is always a walk in which every repeatexl A-edge is separated by arr edge labeled with rr nonempty symbol.

Otherwise, thc walk contains a cycle labeled. We select fiom them those that are labeled zr. We prefer to use the rnore irrtuitivc and more manageablealternative irr Definition?. As for dfa's, the larrguagc acr:cpted by an nfa is definecl forrnally by the cxtended transition function. Irr words, the language consists of all strirrgs ur fbr which there is a walk labeled 'u I'rom the initia,l vertex of the transitiorr graph to some final vertex.

It is car,sy to see from the graph that tlrtl orrly way the nfa can stop in a final state is if the input is either a repetition of the string 10 or the empty strirrg. After reading the prefix 11, the automaton linds itself in state q2, with the transition d q2,0 undefined. We call such a,situatiotr a dead configu- ration, and we r:an visualize it as the automaton sirnply stopping without further action.

But we must always keep in mind that such visualizations are imprecise and carry with them some darrger of misinterpretation. Thus, no final state can be rttached by processingu, - , arxl hence the string is not accepted.

I Why Nondeterminism? In reasorritrgabout nondeterministic mat:hirres,we should be quite cautious in using irrtuitive notions. Intuition c:an tlasily lead us astray, and we mrrst be able to give precise arguments to substarrtiatc our conclusions.

Nonde- terrrrinisrn is a difficult concept. Digital conrputers are completely deter- ministic; tlteir state at anv time is uniqucly predictable from the input and the initial state, Thus it is natural to ask why we study nondeterttftristic rnachifies at all.

We are trying to rrrodel real systems, so why includc such nonrnechartical features as choice? A typical example is a game-plarying progrant.

Flequently, the best move is not known, but ca,nbe f'rrrrndusirrg arr exhaustive search with back- tracking. When several tr,ltt:rnatives are possible, we choose one arrd follow it until it becomes clear whcther or not it was best.

A notrdeterministic algorithur that can tnake the best choice would bc able to solve the problern withoul backtra,cking,brit a,dtltcrrtritristicolre can simulate nondeltcrmirristtt with some extra wrlrk. Nondctcrrnirristn is sometimes helpfirl in solvirrg probletns easily. Look at the rrfir itr F'igure 2. It is clear that thertt is a cltoice to be made.

The first alternaLive leads to the acceptarr:t:of tlte string ail, while the seconrl accepts all strings with an even mrmhnr of a's. While it is possible to find a dfa fcrt this Ianguage, the nondeterminisrn is quite natural. The language is the urriotr of two quite difftrrcrrt sets, and the uondeterminism lets us decide at the olrtset whir:h case we want.

As we go orr, we will seeother and more convincing exarnplt:sof the rmefulnessof nondeterrnirrisrn. Notice that tlrc definition of a gralrlrrlar invtllves a nondeterministic element. Irr ,9 - a,9bl. This It:tu rrs specify many different strittgs usirrg only two rules. Firrally, therreis a technica,lreason for irrtroducirrg rrondctcrminism. As we will see, tltlrtirirr results a,re more easily established for rrfats thtr,n for dfats. Our rrext maior resrilt indica,testhat there is rro essential diffcrcnce betweetr tlrt:sc two types of automata.

Consequently, allowing rron lctermin- ism ofterr sirrrplifies f'rrrmrr,larguments without affecting the gerreralitv of the conc:lusiorr. In Figure 2. Fbr the nfa,in Figurc?. Do yorr think Exercise 7 can be solvccl with fewer than three states'l ffi 9. Wtli"tr of thc strings 00, , , , are arceptetl by the following rrfa?

What is the complement of the language accepted by the nfa in Figure 2,10? L be the language accepted by the nfa in Figure 2. Give a simple description of the Ianguage in Exercise 1. Can Exercise 15 be solved using a dfa? If so, give the solution; if not, give convincing arguments for your conclusion. Consider the following modification of Definition 2,6. Show that for every nfa with multiple initial states there exists an nfa with a single initial state that accepts the same language.

Nft Suppose that in Exercise 17 we made the restriction Qo fl F : fi. Would this affect the conclusion? An nfa in which a there are no tr-trartsitions, and b for all g e I and all a e E, d q, a contains at most one element, is sometimes called an incomplete dfa.

This is reasorrable sirrce the conditions make it such that there is never arry choice of moves. In what sense are dfats and nfa's differerrt? Obviously, there is a difference irr their definition, but this does not imply that there is any essential distinction between them.

To explore this question, we introduce the notion of equivalence between automata. As mentioned, there are generally many accepters for a given language, so eny dfa or nfa has many equivalent accepters. Figttre 2. Let us look at this cluestiott for finite accepters. Since a dfa is in essencea restricted kind of nfa, it is clear that any language that is accepted by a dfa is also accepted by some nfa.

But the converse is not so obvious. We htrve added nondeterminism, so it is at least corrceivable that there is ir larrguage accepted by some nfa for which we cannot find a dfa.

But it turrrs out that this is not so. The classesof dfa's and nfa's are equally powerful: For every language accepted by sorrrerfa there is a dfa that accepts the same language.

This result is ttot obvious and certa,inly lms to be demonstrated. The argument, like most argurnents in this book, will be constructive. The corrstruction is not hard to understand; once the principle is clear it becomes the starting point for a rigorous argument. The rationale for the construction is the following. After arr rrfa has read a string? An equivalent dfa after reading the same string rrrust be in some definite state.

How can we make these two situations correspond? Since for a set of lQl states there are exa,t:tly2lQl subsets, the corresponding dfa will have a fi,nite number of states. Most of the work in this suggested construction Iies in the analysis of the nfa to get the correspondence betrveen possible states and inputs.

Before getting to the formal description of this, Iet us illustrate it with a simple example. Convert the nfa in Figure 2. After reading an a, the nfa c:an be itt state q1 or, by making a. A state labeled g represents an impossible move ftrr the nfa and, therefore, means nonacceptance of the string. Conseqrrently, this state in the dfa mrrst be a nonfinal trap state.

Remember that this state of the dfa corresponds to two possible states of the nfa, so we must refer back to the nfa. If the nfa is in state Q1and reads an a, it can go to q1.

If, for the same input, the nfa is in state q2, then there is no specified transition. At this point, every state has all transitions defined. The result, shown in Figure 2.

The nfa in Figure 2. For the corresponding dfa to accept every such w7 araystate whose label includes 91 must be made a final state. L be the language accepted by a nondeterministic finite accepter M1" : 8r, E, dry,qo,. Proof: Given M1y, we use the procedurc nf a-to-tlfa below to construct the trarsition graph Gp for X,tIp. To understand the constructitln? Every vertex must have exactly the lxl outgoing edges, each labeled with a different element of E. During construction, some of the edgesmay be missing, but the procedUre continues until they are all there.

Identify this vertex as the initial vertex, 2. Repeat the following steps until IIo lrlore edges are missing' Take any vertex qo,qj, '. Every state of GIr whose label containu a. There must then be a walk labeled u frorn qo to Q,iand an edge or a sequence of edges labeled a liom qt to qt. Bui by construction, there will be an edge from Qa to sone state whose label contains ql. The result then is that whenever dir So,trr contains a firml state 91, so tl xruthe label of di gs,tt.

We will fbllow this practice in the rest of the book, emphasizing the basic ideas irt ir proof arrd omitting minor deta,ils, which you may want to fill in yourself. The construction in the above proof is tedious but irnportarrt. Lnt uu rlrl rr,ncltherexa,mple to make sure we understand all the steps. There a,re now a number of missing edges, so we continue, using the :orrutructionof Theorem?. Since there a,restill some missing edges,we continue until we obtain the complete sohrtion in Figure 2.

Show irr tletail that if the label of d-i; q6,ur contairrs 97, then dfr So,tr. If Bo, prove it. II not' give a counterexample.. L0, Define a dta with multiple irritial states in an analogorrsway to thc correspond- ing nfa in Flxercise 17, Section 2.

Give a sirnplc verbal descriptiot of thc la,nguagear:r:eptedby thc dfa in Figure 2. Use this to find another dfa, erpivaletrt to thc given one, but with fcwer statreB. Chopter 2 FIuIrn Aurov. L be any langrrage. Corresponding to this, we can definc a language eaen L : l e u e r t u. Provc that if Z is regular, so is euen I , ffi Frtrm a Ianguage.

L is regular then cft. For a givcrr language, there are rnany dfa's that accept it. Thcre may be a considerable diflerence in the numlrer of states of such equivalertt inrtomata.

In terms of the questions we have corrsideredso far, all solutiorrs arc equally satisfactory, but if the results a,re to be applicd in a practical settitrg, tht:re may be reasolls fcrr preferring one over antlther. The two dfa's depictcrl in Figure 2. We notice sottre obviottsly unnecessary fcatrrres of Figure 2,17 a. The state q5 plays absolrrtelv no role in the autornrrton since it can nevet tlt: retr,chedfrom the initial state q0.

Such a statt: is inaccessible,and it carr btr removed along with tr. But even aftcr the removal of q5, the first tlrttomatotr has sollre redlrndant parts. The states rcachable subsequent to the Iirst move d S0,0 rrrirror those reachable frotn a first move d So,1.

The secorrdeurtomaton cotnbines these two options. From a strictly theoretica,l point of view, there is little reason for prefer- rirrg the automaton in Figure 2. However, in terms of simplicitv, the second alternative is clearly preferable. Repre- sentation of an automatorr for the purpose of computation requires space proportional to the number of states. For storage efficiency, it is desirable to reduce the number of stir,tes as far as possible.

We now describe an algorithm that accomplishes this. Chopter 2 Fu-rtre Auroneta Clearly, two states are either indistinguishable or distinguishable. We first describe a mothod for finding pairs of distinguishable states, procedure: mark 1, Remove all inaccessible states. This can be done by enumerating all simple paths of the graph of the dfa starting at the initial state' Any state not part of sonte path is inaccessible.

Consider all pairs of states p,q. If p e F and q fr F or vice versa, mark the pair p, q as distinguishable, 3. Repeat the following step until no previously unma,rked pairs are marked. If the pair po,eo is nmrked as distinguishable, mark p,q as distinguishable. We claim that this procedure constitutes an algorithm for marking all dis- iinguishable pairs. The procedure nlurlr.

Proof: Obviously, the procedure terminates, since there are only a finite number of pairs that can be marked. It is also easy to see that the states of any pair so marked are distinguishable. The only claim that requires elaboration is that the procedure fiuds all distinguishable pairs. Note first that states q,;and qj are distinguishable with a string of length ru, if and only if there are transitions 6 q r , , a : q n 2. In step 2, we mark all pairs indistinguishableby.

By this inductive assumption, at the beginning of the nth pass through the loop, all states distinguishable by strings of length up to rl - 1 have been marked.

Becauseof 2. By induction then, we can claim that, for any TL,at the completion of the nth pass, all pairs distinguishable by strings of length rz or less have been marked. This means that during the nth pass no new states were marked. Flom 2. As a consequence,whett the loop terminates, all distinguishable ptrirs have been marked. Using the results sketched in Exercise 11 at the end of this section, it can be shown that such a partitionirrg can always be found.

Flom these subsets we construct the minimal automaton by the next procedure. Use procedure mark to lind all pairs of distinguishable states. For each transition rule of M of ihe form 6 q,,a : qe, find the setsto which q' Ttd qo belong.

Consider the automaton depicted in Figure 2. Applying steps 2 and 3 of the procedure reduce therr yields the dfa in Figure 2. Proof: There are two parts. The first is to show that the dfa created by reduce is equivalent to the original dfa. All we have to do is to show that d. We will leave this as an exercise. The second part, to show that M is minimal, is harder. Since there are no inaccessible states in M, there must be distinct strings 'trr,'trz, This contradiction proves that M' cannot exist.

Minirnizethe rturrrberof statesin the dfa in Figure 2. Showthat the automatongeneratedby prot:etlurere. L is a norrernPty langrrage ,such that any r. Prove or disprove the following conjecture. If M : Q, X,,t, q6, F is a' minimal dfa for a regrrlar la,ngua,gc. Consider the following process, to be done after the corrrpletion of the pro- cedure rnar,b.

Put all states rrot marked distinguishable from ge irrto an equivalerrce set with qcl. Then take another state, not in the precedirrg equivalence set, and do the sarne thing' Repeat until there are no more states aw,ilable. Then formalize this suggestion to make it an algorithm, and prove that this algorithm does indeed partition the original state set into equivalence sets. Therefore, every regular language can be described by some dfa or some rrfa.

Such a description can be very useful, for exarnple, if wr: vrant to show the logic by which we decide if a given string is in a certairt language. But in many instances, we need more roncise ways of desr:ribitrg regular languages. In this chapter, we Iook at other ways of representinpJregular languages. These representatiorrs have important practical applications, a rnatter that is touched on in some of the examples and exercises.

Then l. If 11 a. A string is a regular expression if and only if it can be derived from the primitive regular expressions by a firritc mrmber of applications of the rules in 2. Repeating this, we eventually generate the whole string. If r is a regula. L r denote the languageassociatedwith r. If 11 and rz are regulaxexpressions,then 4. The last four rules of this definition are usedto reduceI r to simpler componentsrecursively; the first three are the termination conditions for this recursion.

To seewhat languagea given expressiondenotes,we apply theserules repeatedly. They define a Ianguage precisely if 11 and r?

Instead, we use a convention familiar from mathemat- ics artd programrning languages. We establish a set of precedence rules for evaluation in which star-closure precedes concatenation and concatenation precedes union. Also, the symbol for concatenation may be omitted, so we can write r1r2 for rL. Goirrg from an informal description or set notation to a regular expression tends to be a little harder.

Putting these observations together, we arrive at the solution r. Even though this looks similar to Exanple 3. This suggcsts thrr.

However, the a,nsweris still incornplete, sirrcrrthe utringu ending in 0 or c:onsistingof all l's a,re una,ccollntedf'or.

If we reasorr sliglrtly differently, we rniglrt corrrc up with arrother arrswer. If we see. L as the repetition of the strings 1 arrd 01, the shorter expression? Although tlrc two erxpressionskrok rliflilront, both ir,rrswcrs are corl'ect, as they denote the sarne language.

Generally, lhere are an r. Notc that this la,rrguagcis tlrc txlrnlllcmt:nt of thc languagc irr Exarnple 3. Howtlvtlr, tlrc rc:gtrlir,rcxllrcssiorrs ar l rrot verv sirnililr irrrrl do ttot suggest clearly l,he close relationship between the languages.

I The last example introduces the notion of equivalence of regula,r ex- pressions. We say the two regular expressionsare equivalent if they denote lhe same la,ngua,ge.

Find two other equivalent expressions. L s , Give regular e. Wfrot languagesdo thc cxprcssions. Give a regtrlar expression fo, L", where.

L is the larrguage in Exert:ise 1. L1, Find a regular exptessiorrfrrr the cornpletnent of the language in Example 3. Determine whether or not the following clairns are true for all regular expres- sions rr arxl rz. Givc a general method by wirich auy regular expressiortr can be changed into frsuch that I " " : L F. Prove rigorously that the cxpressions in Exarnple 3.

Formal languages carr be used to dcscribe a variety of two-dimcnsional figures. Arr exarnple o1 this notation is 'urdl, wirich stands for the squarc with sides of urrit length, Draw pictures of the ligurcs denoted try the expressions r'd -, urrLdru, -, alrd ruldr' '. In Exercise? We will slmw this in two parts. RegulorExpressions DenoleRegulor[onguoges We first show that if r is a relgular expression, then.

L r is a rcgular la,n- gua,ge. Our definition says that ir. Bet:arrseof the equivalence of nfats ir,nddfa's, a language is also regulirr if it is rr,cceptedby some nfa. We rrow show that if we have arry rcgular expressiorrrr 'we :irn construct an nfa that arx:eptsI r. The constructiorr for this relies orr the recursive definition for I r. We first construct simple automata for parts 1 , 2 , and 3 of Definition 3. Let r' bc ir regrtla,rexpression. Tlten thrlre exists some nondeterrrrirristir: finite accepter tlnt ir.

ConsequentlS I r is a regular language. Proof: We begirr with automata thal, accept thc ltr,ngua,gesfor the sirnple regula,r expressiorrso,. Assrrme now that we havc irutomata, M rr and M rz tha,t accept larrguagcsrlenoted by regular expressions 11 and 12, rcsptx:tively.

We neecl not explicitly r:onstruct these autornata, but may represerrttlx,. In this schema, the graph vertex at the lcft representsthe initial state, thc one on the right the firral state.

In Exercise 7, Srxrtion 2. With Jl,f r1 and M rr rt:prcst,'ntedin this way, wo then construct autorrrata frlr the regular expressiorrs,r. The constructions are showrr in Figures 3. Figure 3. It should be clear from the interpretation of the graphs in Figures 3. To argue more rigorously, we can give a formal method for constructing the states and traruitions of the combined machine from the states and transitions of the Jrarts, then prove by induction on the number of operators that the construction yields an automaton that accepts the language dettoted by any particula.

Putting thesetogether using the construction in Theorem 3. L should hokl, and thrr,t for clvtlry regular language, thero should exist a corresponding regular exprussiort. Sitrce any regultr,r lir,nguagc:ltas an a"ssociatednfa a,nd hence a transitiotr graph, all we neecl to rlcl is to lind a regula'r expresuitlrr captr,hlcof getrerating the la,bels of all thc walks from q0 to anY fintr,l state. This dot:s not Iook too clifficr.

This creates a bookkeeping probklrn that rnusl be hanclled carrcfully. Tltere are several ways to do this; one of the tnore intrdtivtt approaches requires a sidel trip into what are called generalized transition graphs. The edge qo, go Iabeled n is a cycle that can genertrtc any trumber of a's, that is, it represents L o.

Flom this observation, it follows that for everv regula'r latrguage, there exists a Figure 3. Conversely, every language iccepted by a generalizecltransitiolr graph. Siriffiiabel of Tvery w-at[-In a genetralized transition graph is a regular expressi6n, this appears to be an immediate consequenceof Theorenr 3.

However, there are some subtleties in the argument; we will not pursue them here, but refer the reader itrstead to Exercise 16, Section 4. We can d0 this if we do not change the language denoted by the set of labels that can be generated as we go from q0 to q.

The corntructiorr that achieves this is illustrated in Figure 3. The construction in Figure 3. Although we will not formally prove this, it can be shown that the construction yields an equivalent generalized transition graph. Accept- ing this, we are ready to show how any nfa can be associated with a regular expression.

Let tr be a regula,r language. Proof: Let M be arr nfa that accepts. We can assullle without any loss of generality that M has only one flnal state and that q0 f F'.

We interpret the graph of. To remove a vertex labeled q, we use the scheme in Figure 3. Ncuncps 83 r4 Figure 3. We continue this process, removing one vertex after the other, until we reach the situation shown in Figure 3. The corresponding generalizedtransition graph after removalof state q1 is shown in Figure 3. The construction involved in Theorem 3. An attempt ttt construct a regular expression directly from this description lcacls to all kinds of difficulties. We label the vertices with EE to dcnotc zrrl e,ven number of rr,'s and b'E with O;Lto detrote an odd ,rFumberof a's anr-an ,:.

Next, we rerllove tlrc vertex labeled O0' This gives Figure 3. Often, thc kcy to successfulpattern nratching Lsfincling an effective way to describe the pattertis.

This is a cornplicir. Alltexteclitors allow files to ht: st:arrrrcdfor the occurrerlce of a given strin65; mclst rNlitors c:xtt:rrd this to penrtit searching for patterns. We have to deal with an unlitnited rrurrrber of rrrbitrtr.

Tlxr pa,ttern description is part of the input, so the recognition pt:ocessmust be flexible. To solvc this probltrm, ideils from arttoma'ta'theorv a,reoften used. If the pa,ttern is specified by a regular expression, the patterrr recxrgrri- tion prqgram can take tltis description and cotlert it into arr cc rivalerrt nfh, lsing the constructiorr in Theorem 3,1, I'heoretn 2'2 rrray therr be ust:tl ttl recluce this to a dfa. This clfa, in the fomr of a trtrnsition tatrltt, is eft'ectively tltr pl,ttern-ma,tching a,lgorithrn.

Tlxl lffit:iunr:y of the progra,m must be considered also. If memory space is a problem, the state reductiorr rrrethotl rlt:st:ribedin Section 2.

Find an nfa for Exercise 15 f , section 8. Give explicit rules for the cons-truction suggested in Figure 3,g when various edges in 3. Prove that the constructions suggested by Figrrre 3. In sorrre applicatiOns, srrdr a-sPrograrrfr that cheCk spelliilg, we Inay rtot arr exact rrratch of t[e pattern, only a1 approxirnate otre.

As arr i llustratiorr of this, consider patterrrs derivcd from the original orres by inscrtion of orre syrnbol. Usc the conrrtnt:tion in Theorem 3. Is the result corrsistent with the defirrition of thesc la,nguages?

RegulorGrqmmqrs tffiffiffi A third wa. Grarnmars a,reof'tr:il ail alternative way of specifying languages. Whcrrrlver we define a, ltrrrguage family through irrr automaton or in sorncl other way, we err irrterested in knowing what kind of grammar we can associatewith tlrrl farnily, First, we look at grarrrmarsthat gurxlrate regular Iangua,ges. Note that in a regular Hrirrnma,r, a,t nlost one varia[le appt ilfs tl1 the right sicle of any productiorr.

Both Gr and G2 are regula. Flom this single instance it is ea"syto conjecture that. Thus, regular grammars a,rea,nothcr wrry of talking about regu a,r Iirrrgua,ges. Right-Lineor GrommorsGeneroteRegutqrlonguoges First, we show tlmi a language generir,tcdliy ri right-linear gra,rnmar is tr,lwir,ys rtlgulil,r. To do so, we coustruct tr. Srrl4xlsenow Lhat we have a,step in tr rlr:r. In this scheme,the stir. This sirnple icleais the basis for the fbllewirrs theorem. Then tr CJ is a regular ranguage.

The intermediate states that are needed to do this are of no concern and can be given arbitrary labels. The general scheme is shown in Figure 3.

Thc mrmplete automaton is a,ssetnbledfrom such individual parts. Supposenow that w e L G so that 3. Because of the way in which M wa,sconstructed, to accept ur the automaton has to pass through a seqqenceof states Vo,Vr,.

Hence ur is in I G , irrrd the theorem is proved. I to'that accepts the languagr: generated by the grammar V t - aVt, V - o,bVolb. We start the transition gra,ph,with vertices Vo,Vt, and VJ. Finally, we neecl to rrdd an edge labeled b between Vr and Vy, giving the autornaton shown irr l'igure 3. The lan- guage gerrerated bv the gramma,r ir,nd accepted hy the automaton is the regular la;rguage L aab.

The sta,tcsof the dfa now become the variahles of the grarnmar, and the symbols causing the tra,rrsitions hetxlrne the termi- nals in tlte productionu. L is a regular language on the a,lphabetE, then there exists rr right-linear g r a m r n a rG : V , t , 5 , P s r r c ht h a t L : L G. Therefore we cirn make tltc derivatiotr "' LnQt. QoI ut,ep4 aiai4r I aiai 1 u , ; , a. Conversely,1f u e L G , tht:n its derivation must havc the form 3'5.

With minor modification, the sarneconstnr :tion can be used if M is an nf'a. The transition firnction for att ttfa', togcther with thc corresponding gramrrrar prodrrctions, is given in Figure 3. The result was obtained by sirnply following the construction irr Thtxrrern 3.

I Equivolence BetweenRegulorLonguoges ond RegulorGrommors The previous two thrlclrerns esta,bliuli the connectit:rr between regular lan- guagcs and right-lincirr grammars.

A lanSirragetr is regrrlar if and only if there exists a left-linear ggammar G s u c ht h a t L : L G. Proof; We orrly outline the main idea. Next, we useExercise12,Section2. But thenso are. We now have several ways of describirrg regular languages: dfa's, nfa's, regular expressions, and regqlar gra,mmars' While in sorne irrstarxle one or the other of these may be most suitable, they are all cqually powerful' They all give a complete and unambiguous definition of a regular langnage' TIle connection between all tlrcse concepts is established by the four theorems il this c:hapter, as sltowrr in Figure 3.

GRerr,rrunRs 97 1. In Theorem3,5,provethat l, e : f G 8. W 1 G Suggesta construction by whicJra left-linear grammar can be obtairreclfrom an nfa directly. Find a regrrlar gramlnar that generates the set of all Pa"scal real numbers. We now raise the qrrcstirlrr of how general regula,r la,ngrralgcs arc.