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