O'Reilly logo

Discrete Mathematics by Babu Ram

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

9

Finite State Automata

In this chapter, we study abstract models of machines that can accept input, produce output and have primitive internal memory to keep information about previous inputs. In these machines, the output depends not only on the input but also on the state of the system at the time the input is introduced.

9.1 FINITE STATE MACHINES

Definition 9.1

A finite state machine (complete sequential machine) is an abstract model of a machine with a primitive internal memory. A finite state machine M consists of

  1. A finite set of I input symbols
  2. A finite set S of “internal” states
  3. A finite set O of output symbols
  4. An initial state s0 in S
  5. A next-state function f : S × IS
  6. An output function g: S × I0

A finite state machine M is ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required