GATE CS 2011 Q.45 (CS Q.45): Regular Expressions, Finite Automata and Regular Languages | GATE CS Mastery

A deterministic finite automaton (DFA) $D$ with alphabet $\Sigma = \{a, b\}$ is given below.

Deterministic finite automaton D with start state p, state q, trap state r, and accepting states s and t

Which of the following finite state machines is a valid minimal DFA which accepts the same language as $D$ ?

A

Option A candidate DFA with states p, q, trap state r, and single accepting state s

B

Option B candidate DFA with states p, q, s, and accepting state r

C

Option C candidate DFA with states p, accepting state q, and trap state r

D

Option D candidate DFA with states p, q, and accepting state s

Official answer and solution

Official answer: A
From: Official GATE 2011 answer key

Solution

Apply the standard table-filling / partition refinement algorithm to minimize DFA D.

The states of $D$ are $\{p, q, r, s, t\}$ , where accepting states are $F = \{s, t\}$ and non-accepting states are $\{p, q, r\}$ .

Initial partition: $P_0 = \{ \{s, t\}, \{p, q, r\} \}$ .

Test equivalence of accepting states $s$ and $t$ :

$\delta(s, a) = s \in \{s, t\}$ and $\delta(t, a) = t \in \{s, t\}$
$\delta(s, b) = s \in \{s, t\}$ and $\delta(t, b) = t \in \{s, t\}$
Since both transition to the same group on all inputs, $s \equiv t$ . They merge into a single state $\{s, t\}$ .

Refine non-accepting states $\{p, q, r\}$ on input $a$ :

$\delta(p, a) = s \in \{s, t\}$
$\delta(q, a) = t \in \{s, t\}$
$\delta(r, a) = r \in \{p, q, r\}$
State $r$ splits from $\{p, q\}$ because it remains in non-accepting states on $a$ , giving partition $\{ \{s, t\}, \{p, q\}, \{r\} \}$ .

Test $\{p, q\}$ on input $b$ :

$\delta(p, b) = q \in \{p, q\}$
$\delta(q, b) = r \in \{r\}$
Since $\delta(p, b)$ and $\delta(q, b)$ land in different partitions, $p$ and $q$ are distinguishable. The final partition is $\{ \{p\}, \{q\}, \{r\}, \{s, t\} \}$ .

The minimal DFA has 4 states $\{p, q, r, s\}$ where $s$ is the merged accepting state, matching Option A.

Final answer

A

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

Source

Paper: GATE 2011 Computer Science and Information Technology (CS)
Question: 45 of 65, printed as CS Q.45
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.