edited by
17,224 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$
edited by

4 Answers

Best answer
60 votes
60 votes

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 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
1 votes
1 votes
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.

Answer:

Related questions

36 votes
36 votes
2 answers
1
37 votes
37 votes
4 answers
3
Kathleen asked Sep 25, 2014
11,109 views
If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is t...
38 votes
38 votes
5 answers
4
Akash Kanase asked Feb 12, 2016
15,596 views
The number of states in the minimum sized DFA that accepts the language defined by the regular expression.$(0+1)^{*} (0+1) (0+1)^{*}$is ________.