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 

---

Yes. we are getting 5 states. Can anyone tell which is the correct answer?

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$ 

Correct Answer: $B$

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

---

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

Method 1: Write the language in ascending order of size (enumeration of kleene closure) but don't miss out/include any term according to condtion given in question. Once you are done with the language, draw DFA for accepting smallest string and while making transitions from each state just think what each state has seen and make appropriate transitions.

Method 2 : NFA -> DFA -> minimize it

Method 1 is easy once you practice it.

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.

Comments

It is an NFA since Transition(q0,a)={q0,q1}

---

What if I remove transition a on state q0 then doesn't it not become a valid DFA?

Or else Convert this NFA to DFA

---

Convert it to DFA and you will get the same DFA as described in the best answer.