/* Ċ Ġ* ĠMIT ĠLicense Ċ Ġ* Ċ Ġ* ĠCopyright Ġ( c ) Ġ 2 0 2 0 ĠCh ang jian ĠZ hang Ċ Ġ* Ċ Ġ* ĠPermission Ġis Ġhereby Ġgranted , Ġfree Ġof Ġcharge , Ġto Ġany Ġperson Ġobtaining Ġa Ġcopy Ċ Ġ* Ġof Ġthis Ġsoftware Ġand Ġassociated Ġdocumentation Ġfiles Ġ( the Ġ" Software "), Ġto Ġdeal Ċ Ġ* Ġin Ġthe ĠSoftware Ġwithout Ġrestriction , Ġincluding Ġwithout Ġlimitation Ġthe Ġrights Ċ Ġ* Ġto Ġuse , Ġcopy , Ġmodify , Ġmerge , Ġpublish , Ġdistribute , Ġsublicense , Ġand / or Ġsell Ċ Ġ* Ġcopies Ġof Ġthe ĠSoftware , Ġand Ġto Ġpermit Ġpersons Ġto Ġwhom Ġthe ĠSoftware Ġis Ċ Ġ* Ġfurnished Ġto Ġdo Ġso , Ġsubject Ġto Ġthe Ġfollowing Ġconditions : Ċ Ġ* Ċ Ġ* ĠThe Ġabove Ġcopyright Ġnotice Ġand Ġthis Ġpermission Ġnotice Ġshall Ġbe Ġincluded Ġin Ġall Ċ Ġ* Ġcopies Ġor Ġsubstantial Ġportions Ġof Ġthe ĠSoftware . Ċ Ġ* Ċ Ġ* ĠTHE ĠSOFTWARE ĠIS ĠPROVIDED Ġ" AS ĠIS ", ĠWITHOUT ĠWARRANTY ĠOF ĠANY ĠKIND , ĠEXPRESS ĠOR Ċ Ġ* ĠIMPLIED , ĠINCLUDING ĠBUT ĠNOT ĠLIMITED ĠTO ĠTHE ĠWARRANTIES ĠOF ĠMERCHANTABILITY , Ċ Ġ* ĠFITNESS ĠFOR ĠA ĠPARTICULAR ĠPURPOSE ĠAND ĠNONINFRINGEMENT . ĠIN ĠNO ĠEVENT ĠSHALL ĠTHE Ċ Ġ* ĠAUTHORS ĠOR ĠCOPYRIGHT ĠHOLDERS ĠBE ĠLIABLE ĠFOR ĠANY ĠCLAIM , ĠDAMAGES ĠOR ĠOTHER Ċ Ġ* ĠLIABILITY , ĠWHETHER ĠIN ĠAN ĠACTION ĠOF ĠCONTRACT , ĠTORT ĠOR ĠOTHERWISE , ĠARISING ĠFROM , Ċ Ġ* ĠOUT ĠOF ĠOR ĠIN ĠCONNECTION ĠWITH ĠTHE ĠSOFTWARE ĠOR ĠTHE ĠUSE ĠOR ĠOTHER ĠDEALINGS ĠIN ĠTHE Ċ Ġ* ĠSOFTWARE . Ċ Ġ* Ċ Ġ*/ Ċ Ċ package Ġedu . cm u . isr . rob ust . wa Ċ Ċ import Ġedu . cm u . isr . rob ust . lts a .* Ċ import Ġedu . cm u . isr . rob ust . util . Simple Transitions Ċ import Ġedu . cm u . isr . rob ust . util . StateMachine Ċ Ċ class ĠCor ina 0 2 ( sys : ĠString , Ġenv : ĠString , Ġp : ĠString ) Ġ: ĠAbstract W AG ener ator ( sys , Ġenv , Ġp ) Ġ{ ĊĠ Ġ/** ĊĠĠ Ġ* ĊĠĠ Ġ*/ ĊĠ Ġprivate Ġval Ġalphabet R : ĠSet < String > ĊĊĠ Ġinit Ġ{ ĊĠĠĠ Ġ// ĠGenerate Ġal ph ab ets ĊĠĠĠ Ġval Ġl ts a Call Ġ= ĠLTS AC all () ĊĊĠĠĠ Ġval Ġenv Composite Ġ= Ġl ts a Call . do Compile ( env , Ġ" ENV "). do Compose () ĊĠĠĠ Ġprintln (" Environment ĠLTS : Ġ${ env Composite . composition . max States } Ġstates Ġand Ġ${ env Composite . composition . n transitions ()} Ġtransitions .") ĊĠĠĠ Ġval Ġalphabet ENV Ġ= Ġenv Composite . alphabet Set () ĊĊĠĠĠ Ġval Ġsys Composite Ġ= Ġl ts a Call . do Compile ( sys , Ġ" SYS "). do Compose () ĊĠĠĠ Ġprintln (" System ĠLTS : Ġ${ sys Composite . composition . max States } Ġstates Ġand Ġ${ sys Composite . composition . n transitions ()} Ġtransitions .") ĊĠĠĠ Ġval Ġalphabet SYS Ġ= Ġsys Composite . alphabet Set () Ċ Ċ // ĠĠĠ Ġval Ġalphabet P Ġ= Ġl ts a Call . do Compile ( p , Ġ" P "). alphabet Set () Ċ // ĠĠĠ Ġval Ġalphabet C Ġ= Ġalphabet SYS Ġintersect Ġalphabet ENV Ċ // ĠĠĠ Ġval Ġalphabet I Ġ= Ġalphabet SYS Ġ- Ġalphabet C Ċ // ĠĠĠ Ġalphabet R Ġ= Ġ( alphabet C Ġ+ Ġ( alphabet P Ġ- Ġalphabet I )) ĊĠĠĠ Ġalphabet R Ġ= Ġalphabet SYS Ġintersect Ġalphabet ENV ĊĠ Ġ} ĊĊĠ Ġ/** ĊĠĠ Ġ* ĠReturn Ġthe Ġalphabet Ġof Ġthe Ġweak est Ġassumption ĊĠĠ Ġ*/ ĊĠ Ġoverride Ġfun Ġalphabet Of WA (): ĠIterable < String > Ġ{ ĊĠĠĠ Ġreturn Ġalphabet R ĊĠ Ġ} ĊĊĠ Ġoverride Ġfun Ġweak est Ass umption ( name : ĠString ): ĠString Ġ{ ĊĠĠĠ Ġreturn Ġweak est Ass umption ( name , Ġfalse ) ĊĠ Ġ} ĊĊĠ Ġ/** ĊĠĠ Ġ* ĠReturn Ġthe ĠLT SA Ġspec Ġrepresenting Ġthe Ġweak est Ġassumption Ġof Ġthe Ġenv . ĊĠĠ Ġ*/ ĊĠ Ġfun Ġweak est Ass umption ( name : ĠString , Ġsink : ĠBoolean ): ĠString Ġ{ ĊĠĠĠ Ġreturn Ġcompose Sys P (). prune Error (). determinate ( sink ). minimize (). build F SP ( name ) ĊĠ Ġ} ĊĊĠ Ġ/** ĊĠĠ Ġ* ĊĠĠ Ġ*/ ĊĠ Ġprivate Ġfun Ġcompose Sys P (): ĠState Machine Ġ{ ĊĠĠĠ Ġval Ġl ts a Call Ġ= ĠLTS AC all () ĊĠĠĠ Ġval Ġspec Ġ= Ġcombine Specs ( sys , Ġp , Ġ" || C Ġ= Ġ( SYS Ġ|| ĠP ) @{ ${ alphabet R . join ToString (",") }} .") ĊĊĠĠĠ Ġ// ĠCompose Ġand Ġminim ise ĊĠĠĠ Ġval Ġcomposite Ġ= Ġl ts a Call . do Compile ( spec , Ġ" C "). do Compose (). minim ise () ĊĊĠĠĠ Ġif Ġ(! composite . composition . has ERROR ()) ĊĠĠĠĠĠ Ġprintln (" The Ġerror Ġstate Ġis Ġnot Ġreachable . ĠThe Ġproperty Ġis Ġtrue Ġunder Ġany Ġpermitted Ġenvironment .") ĊĊĠĠĠ Ġ// ĠGet Ġthe Ġcomposed Ġstate Ġmachine ĊĠĠĠ Ġreturn ĠState Machine ( composite ) ĊĠ Ġ} ĊĊĠ Ġ/** ĊĠĠ Ġ* ĊĠĠ Ġ*/ ĊĠ Ġprivate Ġfun ĠState Machine . prune Error (): ĠState Machine Ġ{ ĊĠĠĠ Ġvar Ġtrans Ġ= Ġthis . transitions ĊĠĠĠ Ġ// ĠP rune Ġthe Ġstates Ġwhere Ġthe Ġenvironment Ġcannot Ġprevent Ġthe Ġerror Ġstate Ġfrom Ġbeing Ġentered ĊĠĠĠ Ġ// Ġvia Ġone Ġor Ġmore Ġtau Ġsteps . ĊĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠ Ġval Ġs Ġ= Ġtrans . in Trans () [- 1 ]?. find Ġ{ Ġit . second Ġ== Ġthis . tau Ġ} Ġ?: Ġbreak ĊĠĠĠĠĠ Ġif Ġ( s . first Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġthrow ĠError (" Initial Ġstate Ġbecomes Ġthe Ġerror Ġstate , Ġno Ġenvironment Ġcan Ġprevent Ġthe Ġsystem Ġfrom Ġre aching Ġerror Ġstate ") ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġtrans Ġ= ĠSimple Transitions ( trans . all Trans () ĊĠĠĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġit . first Ġ!= Ġs . first Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġif Ġ( it . third Ġ== Ġs . first ) Ġit . copy ( third Ġ= Ġ- 1 ) Ġelse Ġit Ġ}) ĊĠĠĠ Ġ} ĊĠĠĠ Ġ// ĠE limin ate Ġthe Ġstates Ġthat Ġare Ġnot Ġbackward Ġreachable Ġfrom Ġthe Ġerror Ġstate ĊĠĠĠ Ġ// ĠFIXME : ĠThe ĠCor ina 0 2 Ġpaper Ġdescribes Ġthis Ġstep Ġto Ġremove Ġthe Ġunreachable Ġstates . ĠHowever , Ġin Ġthe Ġther ac 2 5 Ġexample , ĊĠĠĠ Ġ// Ġh Press B Ġwill Ġlead Ġto Ġ" dead lock " Ġ( fire Ġforever ) Ġand Ġthus Ġwill Ġbe Ġremoved . ĠIt Ġresults Ġin Ġno Ġh Press B Ġevent Ġin Ġthe ĊĠĠĠ Ġ// Ġweak est Ġassumption . ĠFor Ġnow , Ġwe Ġremove Ġthis Ġstep ! Ċ // ĠĠĠ Ġval Ġreachable Ġ= Ġthis . get Backward Reach able ( set Of (- 1 )) Ċ // ĠĠĠ Ġtrans Ġ= ĠSimple Transitions ( trans . all Trans (). filter Ġ{ Ġit . first Ġin Ġreachable Ġ&& Ġit . third Ġin Ġreachable Ġ}) ĊĊĠĠĠ Ġreturn ĠState Machine ( trans , Ġthis . alphabet ) ĊĠ Ġ} ĊĊĠ Ġ/** ĊĠĠ Ġ* ĊĠĠ Ġ*/ ĊĠ Ġprivate Ġfun ĠState Machine . determinate ( sink : ĠBoolean ): ĠState Machine Ġ{ ĊĠĠĠ Ġ// Ġtau Ġelim ination Ġans Ġsubset Ġconstruction ĊĠĠĠ Ġval Ġ( dfa , Ġd fa States ) Ġ= Ġthis . tau Elm And Subset Constr () ĊĠĠĠ Ġ// Ġmake Ġsink Ġstate ĊĠĠĠ Ġval Ġd fa Sink Ġ= Ġif Ġ( sink ) Ġd fa . make Sink State ( dfa States ) Ġelse Ġd fa ĊĠĠĠ Ġ// Ġdelete Ġall Ġerror Ġstates ĊĠĠĠ Ġreturn Ġd fa Sink . delete Errors ( dfa States ) ĊĠ Ġ} ĊĊĠ Ġ/** ĊĠĠ Ġ* ĊĠĠ Ġ*/ ĊĠ Ġprivate Ġfun ĠState Machine . make Sink State ( dfa States : ĠList < Set < Int >> ): ĠState Machine Ġ{ ĊĠĠĠ Ġval Ġnew Trans Ġ= Ġthis . transitions . all Trans (). to Mutable Set () ĊĠĠĠ Ġval Ġalphabet Idx Ġ= Ġthis . alphabet . indices . filter Ġ{ Ġit Ġ!= Ġthis . tau Ġ} ĊĠĠĠ Ġval Ġtheta Ġ= Ġd fa States . size ĊĠĠĠ Ġfor Ġ( s Ġin Ġd fa States . indices ) Ġ{ ĊĠĠĠĠĠ Ġfor Ġ( a Ġin Ġalphabet Idx ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( this . transitions . next States ( s , Ġa ). isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġnew Trans . add ( Triple ( s , Ġa , Ġtheta )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġfor Ġ( a Ġin Ġalphabet Idx ) Ġ{ ĊĠĠĠĠĠ Ġnew Trans . add ( Triple ( theta , Ġa , Ġtheta )) ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn ĠState Machine ( Simple Transitions ( new Trans ), Ġthis . alphabet ) ĊĠ Ġ} ĊĊĠ Ġ/** ĊĠĠ Ġ* ĊĠĠ Ġ*/ ĊĠ Ġprivate Ġfun ĠState Machine . delete Errors ( dfa States : ĠList < Set < Int >> ): ĠState Machine Ġ{ ĊĠĠĠ Ġval Ġerr States Ġ= Ġd fa States . indices . filter Ġ{ Ġd fa States [ it ]. contains (- 1 ) Ġ} ĊĠĠĠ Ġval Ġtrans Ġ= Ġthis . transitions . all Trans (). filter Ġ{ Ġit . first Ġ! in Ġerr States Ġ&& Ġit . third Ġ! in Ġerr States Ġ} ĊĠĠĠ Ġreturn ĠState Machine ( Simple Transitions ( trans ), Ġthis . alphabet ) ĊĠ Ġ} Ċ }