GATE CSE
First time here? Checkout the FAQ!
x
0 votes
131 views

asked in Theory of Computation by Active (1.4k points)   | 131 views

2 Answers

+2 votes

Set of binary strings which is divisible by n can be formed by DFA having n states.

So, 8 states. But we can minimize it to 4 states.

answered by Loyal (4.1k points)  
edited by
0 votes

min. four state is required

answered by Active (1.3k points)  
edited by
how 8....??
@rajeshwar yadav can u provide me detailed steps on how to got this minimized dfa..!!

as i'm getting 5 states...
construct the dfa for (0+1)*ooo

any string gengerated by this regular expression is divisible by 8


Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3118 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,969 questions
32,072 answers
74,565 comments
30,147 users