Computer Sciences > GATE 2026 SET-2 > Theory of Computation
Consider the following two finite automata D₁ and D₂.
Which of the following statements is/are true?
A
L(D₁) = L(D₂)
B
L(D₁) is a proper subset of L(D₂)
C
L(D₁) ∩ L(D₂) = {ε}
D
(L(D₁) ∪ L(D₂))* consists of all strings in {0,1}* whose length is divisible by 3

Correct : c,d

The correct answers are Option C and Option D.
The DFAs D1 and D2 are defined over the alphabet Σ = {0,1}, and each accepts strings formed by concatenating specific 3-bit blocks.
L(D1) consists of strings formed using blocks like 000, 001, 010, 101.
L(D2) consists of strings formed using the remaining blocks like 011, 100, 110, 111.
Option A is false:
L(D1) ≠ L(D2). For example, “000” is accepted by D1 but not by D2, while “011” is accepted by D2 but not by D1.
Option B is false:
Neither language is a subset of the other, since each accepts strings that the other does not.
Option C is true:
The 3-bit blocks used in D1 and D2 are disjoint. So, no non-empty string can belong to both languages. The only common string is the empty string ε.
Hence, L(D1) ∩ L(D2) = {ε}.
Option D is true:
The union L(D1) ∪ L(D2) contains all possible 3-bit strings. Repeating these blocks any number of times (including zero) generates all strings whose length is a multiple of 3.
Hence, (L(D1) ∪ L(D2)* ) generates all strings over {0,1} with length divisible by 3.

Similar Questions

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0, 1}, and has the set of states {s,p,q,r}, with s being th...
#952 MCQ
Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: Which one of the fo...
#956 MCQ
Consider the context-free grammar G below: S -> aSb | X X -> aX | Xb | a | b where S and X are non-terminals, and a and b are terminal symbols. The starting non...
#974 MCQ

Related Topics

GATE 2026 GATE CS 2026 Set 2 GATE CS 2026 Q37 finite automata GATE DFA GATE Theory of Computation GATE language intersection GATE Kleene star GATE regular language GATE 2026 L(D1) cap L(D2) automata union star TOC GATE question

Unique Visitor Count

Total Unique Visitors

Loading......