Skip to content
GATEiit

GATE CSE 2026 Session 2 Q47: Compare the languages of two finite automata D1 and D2

Question

Consider the following two finite automata D1D_1 and D2D_2.

Two automata, each with a single accepting start state and cycles that return to it. D1 has length-3 cycles reading 000, 001, 010 and 101; D2 has length-3 cycles reading 011, 111, 100 and 110
Tap the figure to enlarge

Which of the following statements is/are true?

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: C, D (official GATE 2026 final answer key)

Concept used: Each automaton accepts concatenations of fixed length-3 blocks; compare the sets of blocks.

First step: Follow each cycle from the start state to list the 3-symbol blocks of D1D_1 and D2D_2, and check whether they overlap and together cover all 8 blocks.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 2 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2026 Session 2 questions →