[PDF] A taxonomy of nite automata minimization algorithms

View - Download A taxonomy of nite automata minimization algorithms

Previous PDF

Next PDF

A taxonomyof?niteautomataminimization algorithms

?Bruce W? WatsonFaculty of Mathematics and Computing ScienceEindhoven Universityof TechnologyP?O? Box ?? ? MB EindhovenThe Netherlandse?mail?watson?win?tue?nlTel? ?? ? ???

May ? ?

?Abstract

This pap er presents a taxonomy of ?nite automata minimizatio n algorithms? Brzozowski?selegant minimizatio n algorithm diers from all other known minimizati on algorithms and isderived separately? All of the remaining algorithms dep end up on computing an equivalencerelation on states? We de?ne the equivalence relation the partition that it induces and itscomplement? Additionall y some useful prop erties are derived? It is shown that the equivalencerelation is the greatest ?xed p oint of an equation providing a useful characterization of therequired computation?We derive an upp erb ound on the numb er of approximation stepsrequired to compute the ?xed p oint?Algorithms computing the equivalence relation orthe partition or its complement are derived systematically in the same framework? Thealgorithms include Hop croft?s several algorithms from text?b o oks includin g Hop croft andUllman?s ?HU?? Wood?s ?Wo o d

? and Aho Sethi and Ullman?s ?ASU and several newalgorithms or variants of existing algorithms? ?Reprinted with corrections?

CONTENTS?Contents?Intro duction??An algorithm due to Brzozowski?Minimization by equivalence of states???Distinguishability??? ???? ??? ???? ??? ???? ??? ???? ??? ???? ????An upp erb ound on the numb er of approximation steps??? ???? ??? ???? ?????Characterizing the equivalence classes ofE?? ???? ??? ???? ??? ???? ??Algorithms computingEDorQ?E

????ComputingDandEbylayerwise approximations??? ??? ???? ??? ???? ?????ComputingD?E?andQ?E by unordered approximation?? ???? ??? ???? ??????More e

ciently computingDandEby unordered approximation? ??? ???? ??????An algorithm due to Hop croft and Ullman??? ???? ??? ???? ??? ???? ??????Hop crofts algorithm to compute Q?E

e

ciently??? ??? ???? ??? ???? ?????Computing p? q?E???? ??? ???? ??? ???? ??? ???? ??? ???? ?????ComputingEby approximation from b elow?? ???? ??? ???? ??? ???? ????Conclusions??A Some basic de?nitions??B Finite automata??B??Prop erties of nite automata??? ???? ??? ???? ??? ???? ??? ???? ??B?Transformations on nite automata???? ??? ???? ??? ???? ??? ???? ???References?

?INTRODUCTION?Intro ductionThe minimization of deterministic nite automata is a problem that has b een studied since the late??s? Simply stated? the problem is to nd the unique up to isomorphism minimal deterministic nite automaton that accepts the same language as a given deterministic nite automaton?Algorithms solving this problem are used in applications ranging from compiler construction tohardware circuit minimization? With suchavariety of applications? the numb er of diering presentations also grew most textb o oks present their own variation? while the algorithm with theb est running time Hop crofts remains obscure and di

cult to understand?This rep ort presents a taxonomy of nite automata minimization algorithms? The need for ataxonomy is illustrated by the following?Most textb o ok authors claim that their minimization algorithm is directly derived fromthose presented by Human Hu?? and Mo ore Mo or?? Unfortunately? most textb o okspresentvastly diering algorithms for example? compare AU??? ASU?? HU??? andWood?? and only the algorithms presented by Aho and Ullman and byWo o d are directlyderived from those originally presented in Hu?? Mo or???While most of the algorithms rely on computing an equivalence relation on states? manyof the explanations accompanying the algorithm presentations do not explicitly mentionwhether the algorithm computed the equivalence relation? the partition of states that itinduces? or its complement??Comparison of the algorithms is further hindered by the vastly diering styles of presentation sometimes as imp erative programs? or as functional programs? but frequently only as adescriptive paragraph?A related taxonomy of nite automata construction algorithms app ears in Wats????All except one of the algorithms rely on determining the set of automaton states which areequivalent

?? The algorithm that do es not make use of equivalent states is discussed in Section ?In Section ? the denition and some prop erties of equivalence of states is given?Algorithmsthat compute equivalent states are presented in Section ?? The main results of the taxonomyare summarized in the conclusions Section ? App endices A and B give the basic denitionsrequired for reading this pap er? The denitions related to nite automata are taken from Wats????The minimization algorithm relationships are shown in a family tree in Figure ??The principal computation in most minimization algorithms is the determination of equivalentor inequivalent states thus yielding an equivalence relation on states?In this pap er? weconsider the following minimization algorithms?Brzozowskis p ossibly nondeterministic nite automaton minimization algorithm as presented in Brzo?? This elegant algorithm Section was originally invented by Brzozowski?and has since b een reinvented without credit to Brzozowski? Given a p ossibly nondeterministic nite automaton without?transitions? this algorithm pro duces the minimal deterministic nite automaton accepting the same language??Layerwise computation of equivalence as presented in Wood? Mo or? Brau? Urba???This algorithm Algorithm ?? is a straightforward implementation suggested by the approximation sequence arising from the xedp oint denition of equivalence of states??Unordered computation of equivalence? This algorithm Algorithm ???? not app earing in theliterature computes the equivalence relation pairs of states for consideration of equivalenceare chosen in an arbitrary order??Unordered computation of equivalence classes as presented in ASU??This algorithmAlgorithm ??? is a mo dication of the ab ove algorithm computing equivalence of states?

?Equivalence of states is de?ned later? ?INTRODUCTION?

ASU ??

Hop croftUllman ??

imp erativeprogram??? ?????eq? classeseq? classeslistsoptimized list up date

Hop croft ??

Brzozowski ?x??x?

p ointwisememoization approx? from b elowImproved Equivalence of states ?x?equivalence relationapprox? from ab oveNaive ?x??? ??x????pg? ??? ?pg? ?? layerwiseunorderedstate pairs

??Figure ? The family trees of nite automata minimization algorithms? Brzozowskis minimizationalgorithm is unrelated to the others? and app ears as a separate single vertex tree? Each algorithmpresented in this pap er app ears as a vertex in this tree? For each algorithm that app ears explicitlyin this pap er? the construction numb er app ears in parentheses indicating where it app ears in thispap er? For algorithms that do not app ear explicitly? a reference to the section or page numberis given? Edges denote a renement of the solution and therefore explicit relationships b etweenalgorithms? They are lab eled with the name of the renement?

?INTRODUCTION??Improved unordered computation of equivalence? This algorithm Algorithm ??? not app earing in the literature also computes the equivalence relation in an arbitrary order? Thealgorithm is a minor improvementover the other unordered algorithm??Improved unordered computation of equivalence classes? This algorithm Algorithm ??? notapp earing in the literature is a mo dication of the ab ove algorithm to compute the equivalence classes of states? This algorithm is used in the derivation of Hop crofts minimizationalgorithm??Hop croft and Ullmans algorithm as presented in HU??? This algorithm Algorithm ??computes the inequivalence distinguishability relation?Although it is based up on thealgorithms of Human and Mo ore Hu?? Mo or?? this algorithm uses some interestingenco ding techniques??Hop crofts algorithm as presented in Hop c?? Grie??? This algorithm Algorithm ?? is theb est known algorithm in terms of running time analysis for minimization? As the originalpresentation by Hop croft is di

cult to understand? the presentation in this pap er is basedup on the one given by Gries??Pointwise computation of equivalence? This algorithm Algorithm ???? not app earing in theliterature computes the equivalence of a given pair of states?It draws up on some nonautomata related techniques? such as structural equivalence of typ es and memoization offunctional programs??Computation of equivalence from b elow with resp ect to renement? This algorithm Algorithm ???? not app earing in the literature computes the equivalence relation from b elow?Unlikeany of the other known algorithms? the intermediate result of this algorithm can b eused to construct a smaller although not minimal deterministic nite automaton?

?AN ALGORITHM DUE TO BRZOZOWSKI?An algorithm due to BrzozowskiMost minimization algorithms are applied to aDFA? In the case of a nondeterministicFA? thesubset construction is applied rst? followed by the minimization algorithm? In this section? weconsider the p ossibility of applying the subset construction with useless state removal after anas yet unknown algorithm to yield a minimalDFA?Wenow construct such an algorithm? Thealgorithm describ ed in this section can also b e used to construct the minimalComplete DFA?byreplacing functionsubsetoptwithsubset?LetM?

Q? ?V?T? ???S? ?F? bethe??freeFAto b e minimized andM? Q? ?V?T? ???S? ?F? b e the minimizedDFAsuch thatLFA M? LFA M? and of courseMinM?

see Denition B???? For the remainder of this section wemake use ofMinimalProp erty B?? as opp osedtoMin? Since we apply the subset construction last? wehavesomeintermediate nite automatonM?

Q? ?V?T? ???S? ?F? such thatM? usefuls subsetoptM? ? We require thatM? issomehow obtained fromM? ? and thatLFA M? LFA M? LFA M? ?From the denition ofMinimalM? Prop erty B??? we requirep? qp?Q? q?Q? pq ??Lp ??LqUsefulM?

For all statesq?Q?

wehaveq?PQ? sinceM? usefuls subsetoptM? ? Prop erty B? ofthe subset construction givespp?Q? ??Lp?qq?Q? q?p ??LqWe need a su cient condition onM? to ensureMinimalM? ? The following derivation gives sucha conditionMinimalM? ?fDenition ofMinimalProp erty B??gp? qp?Q? q?Q? pq ??Lp ??LqUsefulM? fProp erty B?M? usefuls subsetoptM? gp? qp?Q? q?Q? pq ??Lp ??Lq?Usefulf M? ?fDenition ofDet ?Prop erty B?? andUsefuls ?Usefulf

Remark B???gDet

?M R?

Usefuls

M R? fDet ?MDetMgDetM R?

Usefuls

M R?

The required condition onM?

can b e established by writing reversal as a prex functionM?

Rusefuls

subsetoptRM? ?The complete minimization algorithm for any??freeM? ?FAisM usefuls subsetoptRusefuls subsetoptRM?

This algorithm was originally given by Brzozowski in Brzo?? The origin of this algorithm wasobscured when Jan van de Snepscheut presented the algorithm in his Ph?D thesis vdSn?? Inthis thesis? the algorithm is attributed to a private communication from Prof? Peremans of theEindhoven UniversityofTechnology?Peremans had originally found the algorithm in an article byMirkin Mirk?? Although Mirkin do es cite a pap er by Brzozowski Brzo??? it is not clear whetherMirkins work was inuenced by Brzozowkis work on minimization? Jan van de Snepscheuts recentb o ok vdSn??? describ es the algorithm? but provides neither a history nor citations other thanhis thesis for this algorithm?

?MINIMIZATION BY EQUIVALENCE OF STATES?Minimization byequivalence of statesIn this subsection? we restrict ourselves to considering minimizationofComplete DFAs? Thisis strictly a notational convenience? as the minimization algorithms can b e mo died to workfor nonComplete DFAs? ACompleteminimizedDFAwill in general have one more state asink state than a nonCompleteminimizedDFA? unless the language of theDFAisV

?? LetMQ? V ? T ???S?Fbe aComplete DFA this particularDFAwill b e used throughout thissection? We also assume that all of the states ofMare startreachable? that isUsefuls

M? SinceMis deterministic andComplete?we will also take the transition relation to b e total functionT?QV??Qinstead ofT?QV??PQ?In order to minimize theDFAM?we compute an equivalence relationEQQdened asp? q?E?

??Lp

??LqSince this is an equivalence relation? we are really interested in unordered pairs of states? It isnotationally more convenient to use ordered pairs instead of unordered pairs?The equivalent states are merged according to equivalence relationEwith themergetransformation?Transformation ?

Merging statesFor any equivalence relationHsuch thatHE? thefunctionmergecan b e used to reduce the numb er of states in theDFA

??Functionmergeis denedasmergeQ? V ? T ???fsg?F?HletT ?fp?H ?a?q?H p? a? q?TginQ?H ?V?T ????fs?H g?F?H

endThe denition ofmergeis indep endentofthechoice of representatives of the equivalence classes?Functionmergesatises the prop ertythatL

FA mergeM? H LFA

MjmergeM? Hj jMj jmergeM? HjHand it preservesComplete???free?Useful?Det?andMinimal indeed?mergeis only dened on??freeand deterministicFAs??In order to compute relationE?we need a prop erty of function

??L?Prop erty?

Function

??LFunction ??Lsatises??Lp?aa?Vfag

??LTp? a?ifp?Fthenf?gelse???This allows us to give an alternate but equivalent characterization of equivalence of states?De?nition

Equivalence of statesEquivalence relationEis the greatest under renement xed p oint of the equivalencep? q?E?p?F?q?Faa?VTp? a?Tq? a?E?Remark The greatest xed p oint has the least numb er of equivalence classes of any suchxed p oint??Remark ?Any xed p oint of the equivalence in Denition ??? can b e used?In order tominimize the automaton? the greatest xed p oint is desired??

?WhenHis the identity relation on states functionmergewill not reduce the numb er of states? ?MINIMIZATION BY EQUIVALENCE OF STATESProp erty

ApproximatingEWe can compute this greatest xed p oint with successiveapproximations? The successive approximations ofEareasfollows forkp? q?Ek?

?p? q?Ek aa?VTp? a?Tq? a?Ek whereE? is dened byp? q?E? ?p?F?q?FAn equivalent denition ofE? isE? QnF ??F ??We also have the prop erty thatEk?

Ekfor allk??Remark IfEk

is an equivalence relation? then so isEk? ?E? is an equivalence relation??Remark ?An intuitive explanation ofEk is useful? A pair of statesp? qare said to b ekequivalent written p? q?Ek if and only if there is no stringwjwjksuch thatw? ??Lp?w?

??Lq? As a consequence?pandqarekequivalent if and only if?they are b oth nal or b oth nonnal? and?for alla?V?Tp? aandTq? a are k??equivalentby the denitions of

??LandT

???Remark ?An imp ortant prop ertyofEis that it is also the greatest xed p oint? underset containment instead of renement? of the equivalence in Denition ???? As the greatest xedp oint?Ecan b e computed with adescending sequence of relations? starting withQQ? Sucha sequence need not consist only of equivalence relations? There may b e more steps in suchanapproximating sequence than in theEk

sequence given ab ove?Fortunately?each such step isusually easier to compute than computingEk? fromEk

? Some algorithms that compute thesecheap er but longer sequences are given in Sections ???? and ????All previously known algorithms computeEby successive approximation from ab ove withresp ect to? A new algorithm in Section ?? computesEby successiveapproximation fromb elow? In that section? the practical imp ortance of this is explained????DistinguishabilityIt is also p ossible to computeEby rst computing its complementDE? RelationDcalledthe distinguishability relation on states is dened asp? q?D?

??Lp ??LqDe?nition ?? Distinguishability of statesDis the least under?setcontainment xed p oint of an equationp? q?D?p?F?q?Faa?VTp? a?Tq? a?D?Prop erty ??

ApproximatingDAs with equivalence relationE? relationDcan b e computed by successive approximations forkp? q?Dk?

?p? q?Dk aa?VTp? a?Tq? a?Dk withD? E?

QnFF?FQnF? For allkwehaveDk

Ek ?Wealsohavethe prop erty thatDk? Dk fork??

?Here?denotes normal set containment re?nement do es not apply sinceDis not necessarily an equivalencerelation?

?MINIMIZATION BY EQUIVALENCE OF STATESRemark ??As withEk ?anintuitive explanation ofDk is useful? A pair of statesp? qaresaid to b ekdistinguished written p? q?Dk if and only if there is a stringwjwjksuchthatw? ??Lp?w?

??Lq? As a consequence?pandqarekdistinguished some authors saykdistinguishable if and only if?one is nal and the other is nonnal? or?there existsa?Vsuch thatTp? aandTq? a are k??distinguished????An upp erb ound on the numb er of approximation stepsWe can easily place an upp erb ound on the numb er of steps in the computation ofE?LetEj

b e the greatest xed p oint of the equation deningE?Wehave the sequence ofapproximations whereIQ is the identity relation on statesE E? Ej IQThe indices of some of the equivalence relations in the approximation sequence are knownIQ jQjandE? ? We can deduce thatE E? Ej IQ jQjIn the case thatE? ?wehave thatE? is the greatest xed p oint? In the case thatE? ??either all states are nal states? or all states are nonnal ones in b oth casesE? is the greatestxed p oint? In the case thatE? ? wehaveiEiquotesdbs_dbs19.pdfusesText_25

[PDF] TP Informatique no 8 Algorithme de Dijkstra - Arnaud Jobin

[PDF] TD d 'algorithmique avancée Corrigé du TD 11 : Plus courts chemins

[PDF] corrigé - Irif

[PDF] Algorithmes de factorisation des entiers

[PDF] Reconnaissance de caractères ? l 'aide de réseaux de neurones

[PDF] - Partie 6 - Routage IP

[PDF] Programmation Problème de seuil TI 82-statsfr

[PDF] Correction TD1 algorithme

[PDF] Second degré - Académie en ligne

[PDF] Chapitre 6 Algorithmes numériques

[PDF] LES ÉTAPES DE L 'ALGORITHME DU SIMPLEXE

[PDF] Chapitre 3 Méthode du simplexe - Cours

[PDF] Algorithmique au lycée

[PDF] le programme d 'algorithmique sans ordinateur - Mathématiques

[PDF] Algorithmique programmation en langage C - vol1 - Hal