The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 votes

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

Which of the following finite state machines is a valid minimal $\text{DFA}$ which accepts the same languages as $D$?

+29 votes

Best answer

(**A**) is the answer.

In **(B)** and **(C)** when the first letter of input is '$b$' we reach final state, while in the given **DFA** first letter '$b$' is not a final state. So, **(B)** and **(C)** are not accepting same language as the given **DFA.**

In **(D)** we can reach final state when the last letter is '$a$', whatever be the previous transitions. But in the given **DFA**, when the first $2$ letters are '$b$' we can never reach the final state. So, **(D)** is also accepting a different language than the given** DFA.**

+15 votes

Minimization using set of equivalent states

**First set of equivalent states **

$\pi$_{0} ={ I,II} I={p,q,r} set of non-final state II = {s,t} set of final state

now check states in set I are equivalents or not

p x a -> s [II , **goes to state that is in set II**] q x a -> t [II] r x a -> r [I]

p x b -> q [I] q x b -> r [I] r x b -> r[I]

it is clear p,q are equivalent (both states on symbol a goes to states that is in set II , both states on symbol b goes to states that is in set I) but r behaves differently, *set {p,q,r} divides into two set {p,q},{r}*

now check states in set II are equivalent or not

s x a -> s[II] t x a -> t [II]

s x b -> s[II] t x a ->t [II]

so s,t are equivalent states

that results in

**Second set of equivalent states **

$\pi$_{1} ={ I,II,III} I = {p,q} II = {r} III = {s,t}

check all states in I are equivalents or not , same for set II and set III using same procedure as above

**Third set of equivalent states **

$\pi$_{2} ={ I,II,III,IV} I = {p} II = {q} III = {r} IV = {s,t}

further

**$\pi$ _{3} =$\pi$_{2}**

s and t are equivalent states

Minimized DFA will be same as given in option A

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,751 questions

46,766 answers

140,657 comments

58,519 users