• :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! Q43E

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

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # In Exercises 43–49 find the language recognized by the given nondeterministic finite-state automaton. The result is$${\bf{L(M) = \{ 0,01,11\} }}$$.

See the step by step solution

## Step 1: According to the figure.

Here the given figure contains three states$${{\bf{s}}_{\bf{o}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}$$.

If there is an arrow from $${{\bf{s}}_{\bf{i}}}$$ to $${{\bf{s}}_{\bf{j}}}$$ with label x, then we write down in 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{1}}}$$ $${{\bf{s}}_{\bf{2}}}$$ $${{\bf{s}}_{\bf{2}}}$$

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

## Step 2: Find the final result.

To Move from $${{\bf{s}}_{\bf{o}}}$$ the final state $${{\bf{s}}_{\bf{2}}}$$(directly), I require that the input is 0 and thus the bit string 0 is in recognized language.

$$0 \in {\bf{L(M)}}$$

To move from$${{\bf{s}}_{\bf{o}}}$$to $${{\bf{s}}_{\bf{1}}}$$, the input can be either 0 or 1. To then move from $${{\bf{s}}_{\bf{1}}}$$to $${{\bf{s}}_{\bf{2}}}$$, the second input needs to be 1.Combined , I thus require an input of 01 or 11 to arrive at the final state $${{\bf{s}}_{\bf{2}}}$$,which then implies that 01 and 11 are both in the recognized language.

$$01,11 \in {\bf{L(M)}}$$

Therefore, the language generated by the machine is

$${\bf{L(M) = \{ 0,01,11\} }}$$ ### Want to see more solutions like these? 