GATE CSE 2015 Set 1 | Question: 52

Question

Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.

Comments

Simply the first DFA will accept strings ending with a  and Coming to second DFA it will accept Strings ending with b nowhere in DFA  there could be strings possible ending with both a and b so the language that is under intersection would be null so just simply construct a dfa  with single state but should not accept any string so no final state

---

@Kabir5454 @gatecse

Number of states in NFA???

---

Isn't every dfa is also a nfa 🤷

Answer 1

$L(M) = (a+b)^* \ a = \{a, aa, ba, aaa, aba, bba, \ldots\}$

$L(N) = (a+b)^* \ b = \{b, ab, bb, aab, abb, bbb, \ldots\}$

So, $L(M) \cap L(N) = \{\}$. So, in the minimal DFA, we just have $1$ start state with all transitions going to it self and no final state.

Comments

Thanks Dr. Suresh

---

Yes we will count the dead state also while calculating total number of states in DFA

---

Final state in DFA can be 0 (zero) , 1 or many. According to formal defination of DFA

Answer 2

Another Approach to the same problem 

Good Read

• How to Construct Compund Automata and Find Minimal Number of States

Comments

I got the same diagram as given in above figure but I am unable to reduce it. How will I get 1 state . Please help me to understand.

---

Abhishek Gupta If for any transition we can’t reach to any final state then the intersection is shown as a dead state only.

---

@pc  Consider a situation when we cross multiplying two DFSs, and one of the DFA has a dead state, should we have to multiply the dead state to other states of 2nd DFA ?

Answer 3

ANSWER-1;
Explanation:-
DFA (M)  accept all the string  end with "a".
DFA(N) accept all the string end with "b"

so there is nothing common between both DFA
means
L(M) ∩L(N)={}
so there is only one state to represent a empty string.which is starting and  final state.

Answer 4

One easier way to solve this question is to take product of two DFAs given.
Product of M and N will give us DFA with 4 states: (A,C), (A,D), (B,C) and (B,D). In this (A,C) will be the initial state of DFA and (B,D) will be the final state (since we are taking intersection).
Now draw transition of this dfa using the given two DFA. We will find that no transition leads us to (B,D) final state. Which shows that intersection is none. Hence we need only one state to represent it.