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

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) = \{ \lambda \} \{ 0\} \{ 1\} *}} \cup {\bf{\{ }}0{\bf{\} \{ 0\} *\{ 1\} \{ 1\} *}}$$.

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{2}}}$$

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

## Step 2: Find the final result.

The start state $${{\bf{s}}_{\bf{o}}}$$ is also the final state, which implies that the empty strings $${\bf{\lambda }}$$ is present in the recognized language.

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

To Move from $${{\bf{s}}_{\bf{o}}}$$ the final state$${{\bf{s}}_{\bf{2}}}$$ (directly), I require that the input is 0. However, since there is a loop at $${{\bf{s}}_{\bf{2}}}$$ for input 1. and thus, the string starting with a 0 followed by any sequence of 1’s will be in recognized language.

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

To move from $${{\bf{s}}_{\bf{o}}}$$ to $${{\bf{s}}_{\bf{1}}}$$, the input has to be a 0. Then move from $${{\bf{s}}_{\bf{1}}}$$ to $${{\bf{s}}_{\bf{2}}}$$, the input needs to be 1. However, since there is a loop at $${{\bf{s}}_{\bf{1}}}$$ for input 0. The string needs to have at least one 0 before the 1 to go from $${{\bf{s}}_{\bf{o}}}$$ to $${{\bf{s}}_{\bf{1}}}$$ and $${{\bf{s}}_{\bf{1}}}$$ to $${{\bf{s}}_{\bf{2}}}$$. Since there is also a loop at $${{\bf{s}}_{\bf{2}}}$$ for input 1 any string with sequence of at least one 0 followed by at least 1 will be in recognized language.

$${\bf{\{ 1\} \{ 0\} *\{ 1\} \{ 1\} *}} \subseteq {\bf{L(M)}}$$

Therefore, the language generated by the machine is

$${\bf{L(M) = \{ \lambda \} \{ 0\} \{ 1\} *}} \cup {\bf{\{ }}0{\bf{\} \{ 0\} *\{ 1\} \{ 1\} *}}$$. ### Want to see more solutions like these? 