edited by
17,013 views
65 votes
65 votes

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_____________.

edited by

12 Answers

Best answer
122 votes
122 votes

$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.

edited by
32 votes
32 votes

Another Approach to the same problem 

Good Read

15 votes
15 votes
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.
9 votes
9 votes
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:

Related questions

31 votes
31 votes
2 answers
1
36 votes
36 votes
6 answers
3
go_editor asked Feb 13, 2015
15,510 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.