Finite State Machine

Finite State Machine

A finite state machine (FSM) is either deterministic or non-deterministic. A deterministic FSM (DFSM) is a FSM with at most one transition for each symbol and state. A non-deterministic FSM (NDFSM) is a FSM whose transition function maps input symbols and states to a (possibly empty) set of next states. The transition function also may map the null symbol (no input symbol needed) and states to next states.

Consider the DFSM M = {I, O, S, d, l, S0) defined by:
- Input set I = {1, 0}
- Output set O = {}
- State set S = {A, B, C, D}
- State transition function d
- Output function l

Suppose that the initial state of the machine M is B and the input sequence is 0110, the machine will proceed through states A, B, C and A. If the input is either 110 or 111, and initial state is B, then the machine will visit the states A, C and D. Similarly, for the same initial state, with the input sequence 010100 the machine will proceed to states B, A, B, A, B, A and A.

1) Design the state diagram of this DFSM.

2) Describe the functionality of the above DFSM using transition tables. Consider that the system starts always from state B. What happens if the system will start from another state - say A?

3) Follow the transitions made by this FSM and try to describe its functionality in your own words based on your interpretation of the sequence of events and states obtained after each transition.

4) Try to classify the system as being Mealy or Moore.

5) Construct a DFSM that reads a text and finds the first occurrence of the substring "0101f". More precisely, assume the alphabet is {0, 1, f}, and construct a DFSM that accepts the language {x0101f: x in {0, 1, f}}. Be careful; consider the behaviour of your machine on the string 010101f. Also, note that the problem asks for a deterministic machine. Explain how your machine works.