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

Suggested languages for you:

Americas

Europe

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