• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

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

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

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Construct a deterministic finite-state automaton that recognizes the set of all bit strings beginning with 01.

The result is:

 State 0 1 $${{\bf{s}}_{\bf{0}}}$$ $${{\bf{s}}_{\bf{2}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{2}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{3}}}$$ $${{\bf{s}}_{\bf{3}}}$$ $${{\bf{s}}_{\bf{3}}}$$ $${{\bf{s}}_{\bf{3}}}$$
See the step by step solution

## Step 1: Construction of deterministic finite-state automaton.

Let $${\bf{S = \{ 01\} \{ 0,1\} *}}$$

Let's start state be $${{\bf{s}}_{\bf{0}}}$$. Since the empty string is not in the set S, $${{\bf{s}}_{\bf{0}}}$$ is not a final state.

If the input starts with a 1, then I move on to a non-final state $${{\bf{s}}_{\bf{1}}}$$ and remain there no matter what the next bits are.

If the input starts with a0, then I move on to a non-final state $${{\bf{s}}_{\bf{2}}}$$. If the next digit is a 0, then I move on to $${{\bf{s}}_{\bf{1}}}$$ and remain there no matter what the next bits are. If the next digit was a 1, then I move to the final state $${{\bf{s}}_{\bf{3}}}$$ and remain there no matter what the next bits are.

## Step 2: Sketch of deterministic finite-state automaton. ## Step 3: Another way of representing in tabular form.

 State 0 1 $${{\bf{s}}_{\bf{0}}}$$ $${{\bf{s}}_{\bf{2}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{2}}}$$ $${{\bf{s}}_{\bf{1}}}$$ $${{\bf{s}}_{\bf{3}}}$$ $${{\bf{s}}_{\bf{3}}}$$ $${{\bf{s}}_{\bf{3}}}$$ $${{\bf{s}}_{\bf{3}}}$$

Therefore, this is the required construction. ### Want to see more solutions like these? 