New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Mozell Lind


Mozell Lind
Texas A&M
GPA 3.58


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 10 page Class Notes was uploaded by Mozell Lind on Wednesday October 21, 2015. The Class Notes belongs to CPSC 489 at Texas A&M University taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/226084/cpsc-489-texas-a-m-university in ComputerScienence at Texas A&M University.

Similar to CPSC 489 at Texas A&M

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/21/15
Finite State Machines FSM I Functional decomposition into states of operation I Inputs and outputs are sequences of events I Typical domains of application 0 control functions 0 protocols telecom computers I Different communication mechanisms 0 synchronous classical FSMs Moore 64 Kurshan 90 o asynchronous CCS Milner 80 CSP Hoare 85 ASVquot Slide FSM Example I Informal speci cation If the driver turns on the key and does natfasten the seat belt within 5 seconds then an alarm beeps for 5 seconds or until the driver fastens the seat belt or until the driver turns off the key ASVquot Slide F SM Example IGEYioN gt SIARTJ39IM39ER ENDJ39IM39ERj gt ALARMpN ENDJIMERJo or BELLON or KEYioFF gt ALARMioFF If no condition is satidied implicit selfloop in the current state ASVquot Slide FSM Definition FSM1osr8x I KEY0N KEYOFF BELT0NENDTIMER5 ENDTIMER 10 o O STARTTIMER ALARMON ALARMOFF o S OFF WAIT ALARM o r OFF Set afa llsubsm afl implicit and All ather inputs Are implicitly absent 0 8 2I X S H S L eg 8 KEYOFF WAIT OFF 0 9 21X S H 20 eg 9 KEYON OFF STARTTIMER note selfloin not imnlied in the function SVquot Slide Nondeterministic FSMs I 8 and 9 may be relations instead of functions I o 8 g 2 gtlt S x S WEED m implicit a eg 8KEYOFF ENDTIMER5 WAIT OFF ALARM o 9 2I X S X 20 I Nondeterminism can be used to describe 0 an unspeci ed behavior incomplete speci cation 0 an unknown behavior environment modeling ASVquot Slide NDFSM incomplete Speci cation I Eg error checking rst partially speci ed BIT or Int BIT gt ERR BIT or not BIT gt a mBIT or not w s o a l BITor notBITgt SYNC gt I Then completed as even parity not B IT gt Q BIT gt ERR notBIT gt not BIT gt ERR not BIT gt T 3 Q IT gt not BIT gt re SYNC gt ASVquot Slide NDFSM time range I Special case of unspecifiedunknown behavior but so common to deserve special treatment for efficiency I Eg undetermined delay between 6 and 10 s START gt SEC gt SEC SEC 6 SEC gt ASVquot Slide FSM Composition I Bridle complexity via hierarchy FSM product yields an FSM I Fundamental hypothesis all the FSMs change state together synchronicity I System state Cartesian product of component states state explosion may be a problem I Eg seat belt control timer END75 STARTiTIM39ER gt SEC SEC gt SEC gt SEC gt EC e ASVquot Slide FSM COmposition IGEY ON and STARTiTIM39ER gt L STARTiTrMER A must be cnhzrznl not KEYioFF orBELTioN gt not SEC and KEYioFF or BELLQN gt u 39 nd ASVquot Slide 9 FSM Composition I Given 0 M1 I1 01 SI r1 81 My and M2 12a 02 Sza r2 82 9 2 L I Find the composition oMIOSr8 I given a set of constraints of the form o C o i1 i oisconnectedto i1 Li ASVquot Slide 10 FSM Compositio 1 11 u 12 o 01 u 02 39 39 S 51 X 52 Assume that ol 6 015i3 e 12 01 i3 conununication 8 and 9 are such that eg for each pair 81 i1a31t1 9L1 i1 sl 01 82 iza islasz 12 i27i3asz 02 we have 0 8i1izi3su 3 11 t2 0 M in i2 i3 Sp 32 01 0 ie i3 is in input pattern iff 02 is in output pattern 3 ASVquot Slide 11 FSM Composition I Problem what if there is a cycle 0 Moore machine 8 depends on inputand state 9 only on state EV composition is always welldefined o Mealy machine 8 and 9t depend on input and state EV composition may be undefined 0 what ifltl i1 s1 01 but 02 X2 i3 s2 Is 01 output or not i1 0 i H FSMl M FSM 02 o Causality analysis in Mealy FSMs Berry 98 ASVquot Slide 12 L Moore vs Mealy I Theoretically salne39 computational power almost I In practice different characteristics L I Moore machines 0 nonreactive response delayed by 1cycle 0 easy to compose always welldefined 0 good for implementation n software is always slow n hardware is better when 0 is latched ASVquot Slide L Moore vs Mealy I Mealy machines 0 reactive 0 response time o hard to campase problem with combinational cycles n Esterel compilation algorithm 0 problematic for implementation n software must be fast enough synchronous hypothesis up may be needed in hardware for speed ASVquot Slide H1erarch1 cal FSM models I Problem how to reduce the size of the39 representation Harel s classical papers on StateCharts language and bounded concurrency model 3 orthogonal exponential reductions I Hierarchy L normal 0 state a encloses an FSM 0 being ina means FSM inn is active m 0 states of a are called 0R states 0 used to model preemption and exceptions I Concurrency dune T ermr 0 two or more FSMs are simultaneously active 0 states are called AND states I Nondeterminism 0 used to abstract behavior ASVquot Slide Models Of Computation for reactive systems I Main MOCs o Communicating Finite State Machines 0 Data ow Process Networks 0 Petri Nets 0 Discrete Event 0 Codesign Finite State39Machines I Main languages 0 StateCharts o Esterel o Data ow networks ASVquot Slide Graphical Hierarchical FSM Languages quotquot quotquot quot 39 39 and 39 39 variants o StateCharts UML StateFlow Easy to use for controldominated systems Simulation animated SW and HW synthesis Extended with arithmetics Original StateCharts have problems with instantaneous reaction microsteps EV behavior is implementationdependent EV not a truly synchronous languagellll ASVquot Slide Synchronous Languages I Assumptions L o the system continuously reacts to internaland external events by emitting other events 0 events can occur only at discrete instants 0 zero negligible reaction time I Both control Esterel and data ow Lustre Signal I Very simple syntax and clean semantics based on FSMs I Deterministic behavior I Simulation software and hardware synthesis verification ASVquot Slide Summary of Finite State Machines I Advantages 0 Easy to use graphical languages m on 5mquot 0 Powerful algorithms for a n synthesis SW and HW 1quot n veri cation I Disadvantages 0 Sometimes overspecify implementation sequencing is fully speci ed 0 Numerical computations cannot be speci ed compactly need extended FSMs ASVquot Slide


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.