StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q23E

Expert-verifiedFound in: Page 876

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}}}\) |

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.

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.

94% of StudySmarter users get better grades.

Sign up for free