GATE1998-2.5

Question

Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$ is 

• A. $2$
• B. $5$
• C. $8$
• D. $3$

Comments

Praveen Saini  sir I made NFA with 5 states in my NFA 2 final states One fo aa other for bb ,still I am gwtting 5 states .can we say both are correct

@arjun sir 

Answer 1

Binary strings whose last two symbols are same .

Regular expression $= (0+1)*(00+11) $

Having $NFA$

Equivalent $DFA$

Total no of states $= 5$ 

Comments

@Arjun Sir, please help me, what is the problem with this diagram. It may be stupid question but I'M stuck.

---

@thepeeyoosh

epsilon will not be a part of this language.

---

is there any systematic to solve these kind of questions some times we may miss out some states while conversion ?

---

It may sound stupid but I am stuck.

In the above min DFA, for q1 and q2- transitions on i/p 0/1 are going to final/non-final states respectively. Also  for q3 and q4- transitions on i/p 0/1 are going to non-final/final states respectively. Then why cant we merge them as per definition of equivalence classes, making min DFA of 3 states(which turned out to be wrong).

Please explain, Whether my understanding of equivalence classes is wrong or what?

---

"for q1 and q2- transitions on i/p 0/1 are going to final/non-final states respectively. Also  for q3 and q4- transitions on i/p 0/1 are going to non-final/final states respectively. Then why cant we merge them"

because q1 is a non-final state and q2 is a final state. they can never be equivalent.

similar with q3 and q4.

---

Sir i made the same dfa but made q0 as final state too thinking that Null is also accepted. Sir how should I decide for epsilon in this as well as similar types of questions??

---

it depend on the language.

set of symbols are {0,1} , last two symbols must be same , last two symbols in any string will be either 00 or 11 .

i.e .. (anything) (00+11)

regular expression =(0+1)^*(00+11)

---

Praveen Saini  sir I made NFA with 5 states in my NFA 2 final states One fo aa other for bb ,still I am gwtting 5 states .can we say both are correct

@arjun sir 

---

I hope  you are right

---

Is 000 belongs to this language?If so it is not accepted

Answer 2

I made a fsm with 5 states .here the strings ending in 00 or 11 are to be accepted..just make 2 separate fsm and join them

Comments

Can you please post a picture how you'd JOIN those 2 FA?

---

Joining of two FA will be same as Praveen sir's answer .

---

nt a gd way of explaining things ....

Answer 3

Please Let me know if this is the right answer as in this case also its 5 states but diagram is different.