A Discussion of Finite State Machine in String Search Based on Function & Class FSM Implementations

Lawerence M.O, Adewole O.O

Abstract


The simplest type of computing machine that is worth considering is called a ‘finite state machine’. As it  happens, the finite state machine is also a useful approach to many problems in software architecture, only in this case you don’t build one you simulate it. Essentially a finite state machine consists of a number of states – finite naturally! When a symbol, a character from some alphabet say, is input to the machine it changes state in such a way that the next state depends only on the current state and the input symbol. Notice that this is more sophisticated than you might think because inputting the same symbol doesn’t always produce the same behaviour or result because of the change of state.  A few examples based on the C++ implementation of the finite state algorithm based on the function & class objects is presented.

Full Text:

PDF

References


Alur, R., Kanade, A., Ramesh, S., & Shashidhar, K. C. Symbolic analysis for improving simulation coverage of Simulink/Stateflow models. International Conference on Embedded Software,Atlanta, GA: ACM, pp. 89-98,2008.

Belzer, Jack; Holzman, Albert George; Kent, Allen. Encyclopedia of Computer Science and Technology. 25. USA: CRC Press. p. 73, 1975.

Brutscheck, M., Berger, S., Franke, M., Schwarzbacher, A., Becker, S.: Structural Division Procedure for Efficient IC Analysis. IET Irish Signals and Systems Conference, (ISSC 2008), pp.18-23. Galway, Ireland, 18–19 June 2008. [1]

Hamon, G. A Denotational Semantics for Stateflow. International Conference on Embedded Software. Jersey City, NJ: ACM. pp. 164–172, 2005.

Harel, D. A Visual Formalism for Complex Systems. Science of Computer Programming , 231–274, 1987.

http://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf, p. 34

John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley, 1979.

Koshy, Thomas. Discrete Mathematics With Applications. Academic Press. p. 762, 2004.

Keller, Robert M. "Classifiers, Acceptors, Transducers, and Sequencers" (PDF). Computer Science: Abstraction to Implementation (PDF). Harvey Mudd College. p. 480, 2001.

Pouly, Marc; Kohlas, Jürg. Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. Chapter 6. Valuation Algebras for Path Problems, p. 223 in particular,2011.

Storer, J. A. An Introduction to Data Structures and Algorithms. Springer Science & Business Media. p. 337, 2001.

Tiwari, A. Formal Semantics and Analysis Methods for Simulink Stateflow Models, 2002.

Wright, David R. (2005). "Finite State Machines" (PDF). CSC215 Class Notes. David R. Wright website, N. Carolina State Univ. Retrieved July 14, 2012.




DOI: https://doi.org/10.23956/ijermt.v6i6.276

Refbacks

  • There are currently no refbacks.