GATE CS 2021 Set 2 Q.27 (CS Q.17): Regular Expressions, Finite Automata and Regular Languages

Consider the following deterministic finite automaton (DFA).

DFA: the start state goes to an upper state on 0 and a lower state on 1. The upper state goes to the upper-right state on 0 and to the lower-right state on 1; the lower state goes to the upper-right state on 0 and to the lower-right state on 1. Both right states go to the accepting state on 0,1, and the accepting state loops on 0,1. — DFA state transition diagram

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

Your answer

Official answer and solution

Official answer: 256
From: Official GATE 2021 answer key

Solution

Trace the transitions of the given 6-state DFA to determine which strings of length 8 reach an accepting state.

From the DFA transition diagram:

Start state is $q_0$ .
On either input symbol 0 or 1, $q_0$ transitions to $q_1$ (after 1 symbol).
On either input symbol 0 or 1, $q_1$ transitions to $q_2$ (after 2 symbols).
On either input symbol 0 or 1, $q_2$ transitions to $q_3$ (after 3 symbols).

State $q_3$ is an accepting state. From $q_3$ , every transition on 0 and 1 leads to states $\{q_4, q_5\}$ , which are also accepting states, and all transitions from $q_4$ and $q_5$ remain within the set of accepting states $\{q_4, q_5\}$ .

Thus, any binary string of length at least 3 ends in an accepting state. There are no trap states reachable from $q_3$ .

Since every binary string of length 8 has length $\ge 3$ , all binary strings of length 8 are accepted by the DFA. The total number of binary strings of length 8 is:

2^8 = 256

Final answer

256

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 27 of 65, printed as CS Q.17
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source