The Gateway to Computer Science Excellence
+47 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 by Boss (30.8k points)
edited by | 4.6k views
  • $\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.

8 Answers

+94 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.

by Veteran (431k points)
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.

+23 votes

Another Approach to the same problem 

Good Read

by Boss (21.5k points)

@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.
by (365 points)
+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.
by Active (3.5k points)
+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..
by Active (1.9k points)
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.

by Active (1.5k points)
+1 vote

1 state 

by Boss (36.7k points)
0 votes

Different Approach to solve such questions
1)identify meaning of both DFA and determine intersection of both.
2)make compound table for both then make dfa. 

for more - Good Read
3)determine Regular expression by dissolving all states one by one in both DFA & then find intersection of both.

by Active (4.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,370 answers
105,276 users