Explore BrainMass

Finite State Machine

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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.

© BrainMass Inc. brainmass.com October 24, 2018, 5:31 pm ad1c9bdddf

Solution Summary

This solution is provided in 719 words in an attached .doc file. It uses sequence diagrams and state transition diagrams and tables to answer the questions about the finite state machine.

See Also This Related BrainMass Solution

Determine which of the given strings are recognized by the given deterministic finite-state automaton.

Determine whether each of these strings is recognized by the given deterministic finite-state automaton (which is displayed in an attached .doc file):

(a) 010
(b) 1101
(c) 1111110
(d) 010101010

View Full Posting Details