MSQ+2 / -0MediumDFAFinite Automata & Regular LanguagesTheory of Computation
Theory of Computation → Finite Automata & Regular Languages → DFA
Last updated
Question
Consider the following two finite automata D1 and D2.
Which of the following statements is/are true?
Correct answer
(C) L(D₁) ∩ L(D₂) = \ε\; (D) (L(D₁) ∪ L(D₂))^ consists of all strings in \0,1\^ whose length is divisible by 3
Solution
Let us analyze the languages accepted by the two automata D1 and D2.Analysis of D1:
States: q0 (start, final), q1, q2.
Transitions:
q00q1, q01q2
q11q0, q10q2
q20q0, q21q1
Let's assign values to states: q0≡0, q1≡1, q2≡2 (modulo 3).
Reading 0: 0→1(+1), 1→2(+1), 2→0(+1). So input 0 adds 1 mod 3.
Reading 1: 0→2(−1), 1→0(−1), 2→1(−1). So input 1 subtracts 1 mod 3.
The automaton maintains the value (n0−n1)(mod3).
It accepts strings where n0−n1≡0(mod3), i.e., n0≡n1(mod3).
Examples of accepted strings: ϵ, 01, 10, 000, 111, etc.
Analysis of D2:
States: p0 (start, final), p1, p2.
Transitions:
p01p1, p00p2
p11p0, p10p2
p20p0, p21p1
Let's trace some strings:
00: p00p20p0 (Accepted)
11: p01p11p0 (Accepted)
01: p00p21p1 (Rejected)
10: p01p10p2 (Rejected)
100: p01p10p20p0 (Accepted)
011: p00p21p11p0 (Accepted)
Comparing Languages:
L(D1) contains 01 (length 2), but L(D2) does not. Thus L(D1)=L(D2) and L(D1)⊂L(D2). Options (A) and (B) are false.
L(D2) contains 00 (length 2), but L(D1) does not (n0=2,n1=0⟹2≡0(mod3)).
Intersection: L(D1) requires n0≡n1(mod3). L(D2) accepts strings like 00,11,100,011. Checking intersection for short strings shows no common non-empty strings (e.g., 00,11 rejected by D1; 01,10 rejected by D2; 000,111 rejected by D2). Thus, it is likely that L(D1)∩L(D2)={ϵ}. Option (C) is true.
Union Closure: Since L(D1) contains 01 (length 2) and L(D2) contains 00 (length 2), the union contains strings of length 2. The Kleene star of the union will therefore contain strings of length 2, 4, etc., which are not divisible by 3. Thus, Option (D) is false.
Which of the following statements is/are true?