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.
Which of the following statements are TRUE? Select all that apply.
Answer: A. L1 = L2; C. L1 ∩ L2c = ∅ — ConceptA finite automaton accepts a string when at least one complete run ends in an accepting state. To compare two accepted languages, characterize what…
- A.
L1 = L2
- B.
L1 ⊂ L2
- C.
L1 ∩ L2c = ∅
- D.
L1 ∪ L2 ≠ L1
Attempted by 185 students.
Show answer & explanation
Correct answer: A, C
Concept
A finite automaton accepts a string when at least one complete run ends in an accepting state. To compare two accepted languages, characterize what each state records and derive the exact condition under which an accepting state becomes reachable.
Application
Trace M1: Its start state loops on 0. Reading 1 moves to the middle state, which records that the most recent symbol is 1. From there, 0 returns to the start state, while another 1 reaches the accepting state. The accepting state then loops on both 0 and 1. Hence M1 accepts exactly the strings that contain the substring 11.
Trace M2: Its start state loops on both 0 and 1 and also has a transition on 1 to the middle state. This nondeterministic branch guesses the first symbol of a possible 11. A second consecutive 1 reaches the accepting state, which then loops on both symbols. Hence M2 also accepts exactly the strings that contain the substring 11.
Compare the languages: Both automata therefore accept the same set, so L1 = L2. Equality also implies L1 ⊆ L2 and thus L1 ∩ L2c = ∅.
Cross-check
Example string | M1 | M2 | Reason |
|---|---|---|---|
10 | Not accepted | Not accepted | The substring 11 is absent. |
0110 | Accepted | Accepted | The substring 11 occurs once. |
1011 | Accepted | Accepted | The suffix is 11. |
Because the languages are equal, the strict-subset statement L1 ⊂ L2 and the union statement L1 ∪ L2 ≠ L1 do not hold.
Result
L1 = L2
L1 ∩ L2c = ∅
A video solution is available for this question — log in and enroll to watch it.