Consider the machine M shown below L(M)?
Consider the machine M shown below L(M)?
Answer: C. L(M) = {words containing aa or bb as a sub word — The machine starts at S_c and transitions to S_1 on 'a' or S_2 on 'b'. From S_1, reading 'a' leads to the accepting state S_3. From S_2, reading 'b' leads to…
- A.
L(M) = {words starting with aa or bb}
- B.
L(M) = {words ending with aa or bb}
- C.
L(M) = {words containing aa or bb as a sub word
- D.
None of these
Attempted by 131 students.
Show answer & explanation
Correct answer: C
The machine starts at S_c and transitions to S_1 on 'a' or S_2 on 'b'. From S_1, reading 'a' leads to the accepting state S_3. From S_2, reading 'b' leads to the accepting state S_4. The only way to reach an accept state is by reading 'aa' (S_c -> S_1 -> S_3) or 'bb' (S_c -> S_2 -> S_4). This means the language consists of strings that contain 'aa' or 'bb', in them. Therefore, option c is correct.