Americas
Europe
Q45E
ExpertverifiedIn Exercises 43–49 find the language recognized by the given nondeterministic finitestate automaton.
The result is \({\bf{L(M) = \{ \lambda \} \{ 0\} \{ 1\} *}} \cup {\bf{\{ }}0{\bf{\} \{ 0\} *\{ 1\} \{ 1\} *}}\).
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.
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\} *}}\).
94% of StudySmarter users get better grades.
Sign up for free