Consider the following two finite automata D1 and D2. Which of the following statements is/are true?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2026 Set 2 · Q47
Time

Select all that applyOne or more correct
Solution
Official answer: C) L(D1) ∩ L(D2) = { }; D) (L(D1) ∪ L(D2))* consists of all strings in {0,1}* whose length is divisible by 3
Regular Expressions and Finite AutomataLet us analyze the languages accepted by and :
In both automata and , the start state is the only accepting state (indicated by the double circle).
Every simple directed cycle from the start state back to itself in both automata has a length of . Thus, any accepted string must be composed of cycles of length , which means every string in and has a length that is a multiple of .
Examining the transitions of length returning to the start state:
In , the accepted length- strings are: , , , and (from the other paths). Specifically, contains strings of length formed by paths such as , , , etc.
In , the accepted length- strings are generated by its respective paths.
No non-empty string is accepted by both automata simultaneously because their transitions for any path of length back to the start state are mutually exclusive. Thus, the only common string accepted by both is the empty string , giving:
Therefore, (C) is true.
Since , neither language is a subset of the other, so (A) and (B) are false.
The union of the length- strings accepted by and covers all possible binary strings of length , i.e., . Therefore, generates all strings in whose length is divisible by . Hence, (D) is true.
Try the question first, then check your work.
Examiner trap
Check the lengths of all closed cycles returning to the initial/accepting state, and determine the intersection of the strings generated in one full cycle.
This Regular Expressions and Finite Automata previous year question is Q47 of the GATE CSE 2026 Set 2 paper. Find more GATE CSE PYQs on Regular Expressions and Finite Automata in Theory of Computation, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Regular Expressions and Finite Automata PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Regular Expressions and Finite Automata has 41 GATE CSE PYQs across 24 papers from 2011 to 2026. 4 of them are 2-mark MSQs like this one, and it is the only one in GATE CSE 2026 Set 2.
How GATE tests Regular Expressions and Finite AutomataIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.