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

Suggested languages for you:

Americas

Europe

Q21E

Expert-verified
Found in: Page 876

### Discrete Mathematics and its Applications

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\} }}*$$

See the step by step solution

## Step 1: According to the figure.

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.

## Step 2: Find the final result.

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\} }}*$$