June 15, 1997
June 15, 1997
June 18, 1997
2.209.1 - 2.209.11
FROM FINITE STATE MACHINES TO COMPLEX 1 REACTIVE SYSTEMS WITH VISUAL FORMALISMS
Carl W. Steidley, Jeffrey W. Roule Department of Computer Science Southeastern Louisiana University Hammond, Louisiana 70402 Abstract
It is well known, that a digital computer stores information internally in binary form. At any instant, the computer contains certain data, so its internal storage is set in certain patterns of binary digits. We call this the state of the computer at that instant. Since the computer contains a finite amount of storage, there is a finite (although large) number of states that the computer can assume, thus a computer can be formally and abstractly defined and represented with a finite state machine of the form M=[S,I,O,fs,fo] where S is a finite set of states, I is the finite input alphabet, O is the finite output alphabet, fs:SxI->S, and fo:S->O. Another and generally more accessible way to define such machines is the visual formalism of a directed graph called a state graph or more often a state-transition diagram (or state diagram for short).
Generally, a transformational system is specified by a transformation or function, so that an input/output relationship is usually considered a sufficient specification. A reactive system, in contrast with a transformational system, is characterized by being, to a large extent, event-driven, continuously having to react to external and internal stimuli.
There has been a major problem in the specification and design of large and complex reactive systems. This problem is rooted in the difficulty of describing reactive behavior in ways that are clear and realistic, and at the same time formal and rigorous enough to be amenable to detailed computer simulation.
In this paper we will describe a broad extension of the conventional formalism of state machines and their visual formalism, state diagrams, developed by Harel, that is relevant to the specification and design of complex, discrete-event systems, such as multi-computer real-time systems, communications protocols, and digital control units.
In a naive sense it may be said that computer scientists are interested in solving two questions: What problems can be solved with a computer, and if a problem is theoretically solvable, what is the most effective way to solve it? Answers to the first question arise through development and study of models of computation. During the undergraduate experience we introduce students to the foundations of computation, which address the first question through abstract models of the computer. This model is frequently the finite state machine or finite state automaton. Finite state _____________________ 1. Partial support for this project was provided by the National Aeronautics and Space
Roule, J. W., & Steidley, C. W. (1997, June), From Finite State Machines To Complex 1 Reactive Systems With Visual Formalisms Paper presented at 1997 Annual Conference, Milwaukee, Wisconsin. 10.18260/1-2--6583
ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 1997 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015