in Theory of Computation edited by
17,162 views
39 votes
39 votes

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 

  1. $2$
  2. $5$
  3. $8$
  4. $3$
in Theory of Computation edited by
17.2k views

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 

0
0
Yes. we are getting 5 states. Can anyone tell which is the correct answer?
0
0
Just apply Myhill Nerode theorem, you will get 5 equivalence classes, so minimal dfa must contain 5 states.
0
0

4 Answers

60 votes
60 votes
Best answer

Binary strings whose last two symbols are same .

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

Having $\textsf{NFA}$

 

Equivalent $\textsf{DFA}$

Total no of states $= 5$ 

Correct Answer: $B$

edited by

4 Comments

  

I can't find any bug in this DFA, please see this - 

where is the error ???

1
1
@mrinmoy bro its not correct because your dfa not accepting aaa,bbb,.... in which last two terms are same
3
3

oh yes, thanks

0
0
4 votes
4 votes
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

3 Comments

Can you please post a picture how you'd JOIN those 2 FA?
0
0
Joining of two FA will be same as Praveen sir's answer .
1
1
nt a gd way of explaining things ....
1
1
1 vote
1 vote
Finding number of states using Myhill Nerode:

We have 7 possibilities for a string in $\Sigma ^{*}$. They are the strings whose last 2 symbols are  00, 01, 10, 11, 1, 0, $\epsilon$. Among them 00 and 11 belong to final state and other belong to Non final.

Let us find out who are distinguishable from each other

00 distinguishable from 11 by 1

00 distinguishable from 10 by $\epsilon$

00 distinguishable from 01 by $\epsilon$

00 distinguishable from 1 by $\epsilon$

00 distinguishable from 0 by $\epsilon$

00 distinguishable from $\epsilon$ by $\epsilon$

11 distinguishable from 10 by $\epsilon$

11 distinguishable from 01 by $\epsilon$

11 distinguishable from 1 by $\epsilon$

11 distinguishable from 0 by $\epsilon$

11 distinguishable from $\epsilon$ by $\epsilon$

01 distinguishable from 10 by 1

01 distinguishable from 1 by nothing so they are equivalent. Hence 01$\equiv$1.

01 distinguishable from 0 by 1

01 distinguishable from  $\epsilon$ by 1

10 distinguishable from 1 by 1

10 distinguishable from 0 by nothing so they are equivalent.Hence 10$\equiv$0.

So we have 5 equivalence classes. {00}, {11}, {01,1}, {10,0}, {$\epsilon$}.

Hence the number of states in minimal DFA is 5.
0 votes
0 votes

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

by

3 Comments

It is an NFA since Transition(q0,a)={q0,q1}
0
0
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
0
0
Convert it to DFA and you will get the same DFA as described in the best answer.
1
1
Answer:

Related questions