Consider the following two finite automata. M1 accepts L1 and M2 accepts L2.…

2008

Consider the following two finite automata. M1 accepts L1 and M2 accepts L2.

2008_36


Which one of the following is TRUE?

  1. A.

    L1 = L2

  2. B.

    L1 ⊂ L2

  3. C.

    L1 ∩ L2\' = ∅

  4. D.

    L1 ∪ L2 ≠ L1

Attempted by 155 students.

Show answer & explanation

Correct answer: A

Answer: L1 = L2. Both automata accept exactly the set of binary strings that contain at least one '1'.

  • Analysis of M1: From the start state M1 loops on '0' (so leading zeros keep it in the start state). On reading the first '1' it moves to an accepting state that has a loop on both '0' and '1'. Therefore M1 accepts exactly those strings that contain at least one '1' (the first '1' moves it to acceptance and further symbols keep it accepting).

  • Analysis of M2: M2 also remains non-accepting while only '0's are seen, and transitions into an accepting state upon reading a '1', after which it loops on both '0' and '1'. This gives the same behaviour: M2 accepts exactly those strings that contain at least one '1'.

Conclusion: Since both M1 and M2 accept the same set—all binary strings with at least one '1'—we have L1 = L2.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir