• :00Days
  • :00Hours
  • :00Mins
  • 00Seconds
A new era for learning is coming soonSign up for free
Log In Start studying!

Select your language

Suggested languages for you:
Deutsch (DE)
Deutsch (UK)
Deutsch (US)

Americas

Europe

Answers without the blur. Sign up and see all textbooks for free! → Illustration

Q1E

Expert-verified
Discrete Mathematics and its Applications
Found in: Page 863
Discrete Mathematics and its Applications

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Register for Free I’ll do it later
Illustration

Short Answer

Draw the state diagrams for the finite-state machines with these state tables.

(a): State diagram of the finite-state machine is shown below.

(b): State diagram of the finite-state machine is shown below.

(c): State diagram of the finite-state machine is shown below.

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :
TABLE OF CONTENTS

Step 1: General form

Finite-State Machines with Outputs (Definition):

A finite-state machine\({\bf{M = }}\left( {{\bf{S,}}\,\,{\bf{I,}}\,\,{\bf{O,}}\,\,{\bf{f,}}\,\,{\bf{g,}}\,\,{{\bf{s}}_0}} \right)\) consists of a finite set S of states, a finite input alphabet I, a finite output alphabet O, a transition function f that assigns to each state and input pair a new state, an output function g that assigns to each state and input pair output and an initial state\({{\bf{s}}_0}\).

Step 2: Draw the state diagram for the given state table

Given that, a state table is shown below:

Using the state table draw a state diagram for the finite-state machines.

Construction:

Now, we make a node for each state as\({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}\).

Then, \({{\bf{s}}_0}\) is assigned as the start.

And the labelled arrow is added for every transition, where the label is \(\left( {{\bf{x,y}}} \right)\) with x the input and y the output of the transition.

Not: the output is given under g in the table.

The state diagram is shown below.

Therefore, the result shows the diagram of a finite-state machine.

Step 3: Draw the state diagram for the given state table

Given that, a state table is shown below.

Using the state table draw a state diagram for the finite-state machines.

Construction:

Now, we make a node for each state as\({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}\).

Then, \({{\bf{s}}_0}\) is assigned as the start.

And the labelled arrow is added for every transition, where the label is \(\left( {{\bf{x,y}}} \right)\) with x the input and y the output of the transition.

Not: the output is given under g in the table.

The state diagram is shown below

Hence, the result shows the diagram of a finite-state machine.

Step 4: Draw the state diagram for the given state table

Given that, a state table is shown below.

Using the state table draw a state diagram for the finite-state machines.

Construction:

Now, we make a node for each state as\({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\).

Then, \({{\bf{s}}_0}\) is assigned as the start.

And the labelled arrow is added for every transition, where the label is \(\left( {{\bf{x,y}}} \right)\) with x the input and y the output of the transition.

Not: the output is given under g in the table.

The state diagram is shown below.

Therefore, the result shows the diagram of a finite-state machine.

Most popular questions for Math Textbooks

Find five other valid sentences, besides those given in Exercise 1.

Show that the grammar given in Example 7 generates the set,

\({\bf{\{ }}{{\bf{0}}^{\bf{n}}}{{\bf{1}}^{\bf{n}}}{{\bf{2}}^{\bf{n}}}{\bf{|}}\,{\bf{n = 0,}}\,{\bf{1,}}\,{\bf{2,}}\,...{\bf{\} }}\).

a) Construct a phrase-structure grammar that generates all signed decimal numbers, consisting of a sign, either + or −; a nonnegative integer; and a decimal fraction that is either the empty string or a decimal point followed by a positive integer, where initial zeros in an integer are allowed.

b) Give the Backus–Naur form of this grammar.

c) Construct a derivation tree for −31.4 in this grammar.

Show that if A is a set of strings, then\({\bf{A}}\emptyset {\bf{ = }}\emptyset {\bf{A = }}\emptyset \).

Describe the set of strings defined by each of these sets of productions in EBNF.

\(\begin{array}{c}\left( {\bf{a}} \right){\bf{string :: = L + D?L + }}\\{\bf{L :: = a }}\left| {{\bf{ b }}} \right|{\bf{ c }}\\{\bf{D :: = 0 | 1}}\\\left( {\bf{b}} \right){\bf{string :: = signD + |D + }}\\{\bf{sign :: = + | - }}\\{\bf{D :: = 0 | 1|2|3|4|5|6|7|8|9}}\\\left( {\bf{c}} \right){\bf{string :: = L*}}\left( {{\bf{D + }}} \right){\bf{?L* }}\\{\bf{L :: = x |y }}\\{\bf{D :: = 0 | 1}}\end{array}\)
Icon

Want to see more solutions like these?

Sign up for free to discover our expert answers
Get Started - It’s free

Recommended explanations on Math Textbooks

Decision Maths

Read explanation

Calculus

Read explanation

Probability and Statistics

Read explanation

Statistics

Read explanation

Mechanics Maths

Read explanation

Geometry

Read explanation

Pure Maths

Read explanation

94% of StudySmarter users get better grades.

Sign up for free
94% of StudySmarter users get better grades.