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

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


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

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

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

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

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

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

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

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

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]

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

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

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

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




DOI: https://doi.org/10.23956/ijarcsse.v7i9.420

Refbacks

  • There are currently no refbacks.

Comments on this article

View all comments


Bookmark and Share


© International Journals of Advanced Research in Computer Science and Software Engineering (IJARCSSE)| All Rights Reserved | Powered by Advance Academic Publisher.