Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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 by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

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

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

In Exercises 43–49 find the language recognized by the given nondeterministic finite-state automaton.

Step by Step Solution

Step 1: According to the figure.

Step 2: Find the final result.

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

In Exercises 43–49 find the language recognized by the given nondeterministic finite-state automaton.

Step by Step Solution

Step 1: According to the figure.

Step 2: Find the final result.

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths