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

M=> it is the DFA for "ends with a" => (a+b)*a

N=>it is the DFA for " ends with b"=>(a+b)*b

so the intersection would result in null..

so only 1 state is required..

Comments

good explanation

Answer 2

M₁ :  language of all strings ends with a

M_2 :   language of all strings ends with b

all strings over alphabet {a,b} either ends with a or ends with b, 

hence intersection of these languages will result an empty set { }.

so, there will be only 1 state which is not final.

Answer 3

1 state 

Answer 4

M accepts the strings which end with a and N accepts the strings which end with B. Their intersection should accept empty language.
So answer is 1