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

Q21E

Expert-verifiedFound in: Page 876

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**In Exercises 16–22 find the language recognized by the given deterministic finite-state automaton**

The result is:

\({\bf{L(M) = }}\lambda \cup {\bf{\{ 0\} \{ 1\} \{ 0\} }} \cup {\bf{\{ 10,11\} \{ 0,1\} }} \cup {\bf{\{ 0\} \{ 1\} \{ 01\} \{ 0,1\} }} \cup {\bf{\{ 0\} \{ 1\} \{ 00\} \{ 0\} \{ 1\} \{ 0,1\} }}*\)

Here the given figure contains five states\({{\bf{s}}_{\bf{o}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}{\bf{,}}{{\bf{s}}_{\bf{5}}}\).

If there is an arrow from \({{\bf{s}}_{\bf{i}}}\)to \({{\bf{s}}_{\bf{j}}}\)with label x, then we write it down in a row \({{\bf{s}}_{\bf{j}}}\)and in the row \({{\bf{s}}_{\bf{i}}}\)and in column x of the following table.

State | 0 | 1 |

\({{\bf{s}}_{\bf{o}}}\) | \({{\bf{s}}_{\bf{1}}}\) | \({{\bf{s}}_{\bf{2}}}\) |

\({{\bf{s}}_{\bf{1}}}\) | \({{\bf{s}}_{\bf{3}}}\) | \({{\bf{s}}_{\bf{1}}}\) |

\({{\bf{s}}_{\bf{2}}}\) | \({{\bf{s}}_4}\) | \({{\bf{s}}_4}\) |

\({{\bf{s}}_{\bf{3}}}\) | \({{\bf{s}}_{\bf{5}}}\) | \({{\bf{s}}_4}\) |

\({{\bf{s}}_{\bf{4}}}\) | \({{\bf{s}}_4}\) | \({{\bf{s}}_4}\) |

\({{\bf{s}}_{\bf{5}}}\) | \({{\bf{s}}_{\bf{5}}}\) | \({{\bf{s}}_4}\) |

\({{\bf{s}}_{\bf{o}}}\)is marked as the start state.

Because\({{\bf{s}}_{\bf{o}}}\)is the final state, the empty string is accepted. The string that drives the machine to the final state \({{\bf{s}}_{\bf{3}}}\)is precise\({\bf{\{ 0\} \{ 1\} \{ 0\} }}\).

There are three ways to get to the final state\({{\bf{s}}_{\bf{4}}}\), and once I get three, I stay there. The path thorough \({{\bf{s}}_{\bf{2}}}\)tells those strings in \({\bf{\{ 10,11\} \{ 0,1\} }}\) are accepted.

The path \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\) tells that the strings in \({\bf{\{ 0\} \{ 1\} \{ 01\} \{ 0,1\} }}\) are accepted and the path \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{5}}},{{\bf{s}}_{\bf{4}}}\)tells those strings in \({\bf{\{ 0\} \{ 1\} \{ 00\} \{ 0\} \{ 1\} \{ 0,1\} *}}\)are accepted.

Therefore, the language recognized by machines is:

\({\bf{L(M) = }}\lambda \cup {\bf{\{ 0\} \{ 1\} \{ 0\} }} \cup {\bf{\{ 10,11\} \{ 0,1\} }} \cup {\bf{\{ 0\} \{ 1\} \{ 01\} \{ 0,1\} }} \cup {\bf{\{ 0\} \{ 1\} \{ 00\} \{ 0\} \{ 1\} \{ 0,1\} }}*\)

94% of StudySmarter users get better grades.

Sign up for free