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

First understand the language, then go ahead and do as asked in the question..

---

Only one states is common between them so Ans is 1

---

try in this way

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

Can someone please explain how to find regular expressions for these kind of automata.

---

🕵️‍♂️

---

Set of Final States is the subset of Available states according to Formal Definition of DFA hence Final state can be null that's zero.

Answer 2

Another Approach to the same problem 

Good Read

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

Comments

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 ?

---

@KunuSwavik ideally yes

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.

Answer 5

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 6

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.