Write a program that tests a string is accepted or rejected according to a certain Finite State Machine (FSM).

The program must read the FSM before testing the input string.

2 Years
Discussion Span
Last Post by rubberman

What have you tried so far?

Even if we wanted to help at this point we would be unable. What format is the FSM in, for example? To properly read and build a FSM in memory is a non-trivial task so you need to provide some more detail (and evidence that you've tried something yourself).


I've been writing FSM execution engines for 25+ years. These have been used to parse computer languages, implement TCP/IP protocols, and implement generic terminal emulation programs. What do YOU know about finite-state machines? How would you approach the problem (at a high level)?


rubberman and L7Sqr, thanks for yours' reply
Mr. rubberman the program is concerned with programming language only like C++


As I explained in my previous response, what you are trying to write is a lexical analyzer. I gave links to some helpful posts and resources in that post that you should have gone over by now.

No one here is going to write this program for you. We can only guide you in this project; we cannot and will not help you cheat on it by doing it for you. Please show us what you have done so far so we can give you advice, otherwise there isn't much we can do.

Edited by Schol-R-LEA


The FSM code I have written in the past has been for both C and C++. In any case, each state has events it responds to, and those transition to the same or a new state. So, a state such as "reading-a-word" will have an event handler, and if the event is "have-a-letter" it will accumulate the letter in the current word and transition back to "reading-a-word". If the event is "have-white-space", then it will store the current word somewhere (such as an array) and transition to the "reading-white-space" state. This is just a simple example of what you will need to do. You can do this with classes in C++, and with nested arrays in C. I have written both types for SQL parsers, terminal emulators, and tcp/ip protocol handlers. You can also use lex and yacc (bison) to build a compiled-in state machine. The generated code is ugly though, and difficult to debug - in my opinion, which is why I prefer to roll my own.

Edited by rubberman

This article has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.