Skip to content
GATEiit

GATE CSE 2021 Set 2 Q27: Number of length-8 strings accepted by a given DFA

Question

Consider the following deterministic finite automaton (DFA).

The number of strings of length 8 accepted by the above automaton is ________.

DFA: start state goes on 0 to an upper state and on 1 to a lower state; each of these goes on 0 to one middle-right state and on 1 to the other (edges cross); both middle-right states go on 0,1 to a single accepting state, which loops to itself on 0,1
Tap the figure to enlarge

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 256 (official GATE 2021 final answer key)

Concept used: Trace which strings reach the accepting sink state.

First step: Every input symbol moves one layer to the right, whatever it is, so every string of length at least 3 ends in the accepting state.

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 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2021 Set 2 questions →