Log In
49 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_____________.

in Theory of Computation
edited by
  • $\epsilon$ is an empty string$\implies \mid \epsilon \mid = 0$ (Its string length is zero.)

  • $L=  \emptyset=\{\}$  is a empty language
@Lakshman Patel i think it's the other way around..{} is empty language..and epsilon is empty string.

10 Answers

100 votes
Best answer

$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
is a final state not necessary in dfa?
Nopes. In the definition of DFA, final states is defined as a subset of set of states. So, it can be null also.
When they ask questions of number of states , are we supposed to count Dead State as well ?
This is the DFA that iterates over (0|1)* but does not accept anything (not even empty string).

Thus the language it accepts is the empty set
@arjun sir great catch
A final state is needed as it is in the definition of DFA. What about final state?

According to me, there should be final state. Arjun Sir, please give some light to my query.
L(M) intersection L(N)={}

->A-----a/b----B(dead state)

A is initial stae.

what is wrong in it?
@Abhisek here, initial state is itself dead state in minimal dfa.
@Naveen Kumar 3

but epsilon not accepted by that dfa.

???{} in language
@Abhishek $L(M) ∩L(N)$= {} ,i.e., empty set. (epsilon & empty set are different)

and, empty set language does not accept any thing.
@Arjun sir what if they are asked for NFA?Can we still use that dead state?

@Arjun sir,

why are we not considering the final states in DFA.

final state can be present as a unreachable state from initial state????


@Arjun sir,

why are we not considering the final states in DFA.

final state can be present as a unreachable state from initial state????



It is not a compulsion that final state must be there in a DFA even if it is not required. So after minimization there is no requirement of final state & hence we have not considered it.

Final state is a subset.Hence not required always in a DFA.

25 votes

Another Approach to the same problem 

Good Read


@pC when you club all states into one state - AXBY then won't it also be the final state b/c it has BY present?

How you make final and non final state in transition table..
And by considering your table how only one state is possible
i think there is no need to take BY while taking product automata .

as we take only those states on which we are going while taking product automata

(same as we do in subset conversion algo : converting NFA to DFA)

since in the first 3 rows of the table we are not going on BY so no need to take BY.

and then we are left with only 3 rows in the table that can be merged, but they donot contain BY,so the product dfa or the intersection of 2 dfa's contain only 1 state and that too not final state!

hope it clears a bit..u can chk this qn too.

Nice Solution
Minimize the table using partition method or myhill-nerode theorem to get minimal dfa.
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.
13 votes
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
L(M) ∩L(N)={}
so there is only one state to represent a empty string.which is starting and  final state.
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.
5 votes
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..
good explanation
3 votes

M1 :  language of all strings ends with a

M:   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.

1 vote

1 state 

1 vote

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


Related questions

23 votes
2 answers
Consider a system with byte-addressable memory, $32-bit$ logical addresses, $4$ $kilobyte$ page size and page table entries of $4$ $bytes$ each. The size of the page table in the system in $megabytes$ is_________________.
asked Feb 12, 2015 in Operating System makhdoom ghaya 4.7k views
26 votes
5 answers
The output of the following C program is_____________. void f1 ( int a, int b) { int c; c = a; a = b; b = c; } void f2 ( int * a, int * b) { int c; c = * a; *a = *b; *b = c; } int main () { int a = 4, b = 5, c = 6; f1 ( a, b); f2 (&b, &c); printf ("%d", c - a - b); }
asked Feb 12, 2015 in Programming makhdoom ghaya 4.4k views
27 votes
5 answers
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
asked Feb 13, 2015 in Theory of Computation jothee 5.9k views
29 votes
2 answers
Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression contains $n$ states $n+1$ states $n+2$ states None of the above
asked Sep 23, 2014 in Theory of Computation Kathleen 9.6k views