The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+19 votes

Consider a DFA over $\Sigma=\{a,b\}$ accepting all strings which have number of a's divisible by $6$ and number of $b$'s divisible by $8$. What is the minimum number of states that the DFA will have?

- $8$
- $14$
- $15$
- $48$

+28 votes

Best answer

Answer is (**D**). It can be proved using Myhill Nerode theorem. We need a separate state for $\#a \ mod \ 6 = 0..5$ and $\#b \ mod \ 8 = 0..7 $. Each combination of them must also be a new state giving $6*8 = 48$ minimum states required in the DFA.

Reading Myhill-Nerode theorem might be confusing though it is actually very simple.

http://courses.cs.washington.edu/courses/cse322/05wi/handouts/MyhillNerode.pdf

+1

what would be an answer if I change the given condition to "number of a's divisible by 6 or number of b's divisible by 8"

+1

same 48 states ..no of final states increased and .. if they asked for same symbol then we have to take lcm

+1

We can take Cartesian product of given two dfas M1 & M2, accepting the languages L1 and L2 respectively where:

L1={w over Σ={a,b} accepting all strings which have number of a's divisible by 6}, say has 'm' states

L2={w over Σ={a,b} accepting all strings which have number of b's divisible by 8}, say has 'n' states

Step 1: Take Cartesian product and create a dfa M with m*n # of states. (total # of states)

Step 2: The difference of AND/OR comes on basis of selection of final states in M..

If OR(means UNION) so in M choose all states as final states wherever final states of EITHER M1 or M2 occurs..

If AND(means INTERSECTION) so in M choose all states as final states wherever final states of BOTH M1 and M2 occurs..

So by question, M1 has 6 states, M2 has 8 states. Final dfa has 6*8=48 states.(only total # of states is asked here and it will be minimum).

Please correct me if I am wrong.

L1={w over Σ={a,b} accepting all strings which have number of a's divisible by 6}, say has 'm' states

L2={w over Σ={a,b} accepting all strings which have number of b's divisible by 8}, say has 'n' states

Step 1: Take Cartesian product and create a dfa M with m*n # of states. (total # of states)

Step 2: The difference of AND/OR comes on basis of selection of final states in M..

If OR(means UNION) so in M choose all states as final states wherever final states of EITHER M1 or M2 occurs..

If AND(means INTERSECTION) so in M choose all states as final states wherever final states of BOTH M1 and M2 occurs..

So by question, M1 has 6 states, M2 has 8 states. Final dfa has 6*8=48 states.(only total # of states is asked here and it will be minimum).

Please correct me if I am wrong.

+16 votes

Answer is D: 6 states for a's and 8 states for b's, and condition is AND so number of states will be 6X8 = 48 states.

+4 votes

**I will give a short trick for divisibility: |w| i.e length of string is divisible by a,b.**

If a doesn't divide b and b doesn't divide a then Min. states = a*b

Case 1 : Divisible by a and b ----> If a divides b or b divides a then Min. No .of states = LCM(a,b)

Case 2: Divisible by a or b ------> If a divides b or b divides a then Min. states = GCD(a,b)

+1

@amitabh, you are wrong in case of Divisible by **a or b** , for example just check divisible by 2 or 3 and we require atleast 6 states in min. dfa but your answer gives GCD(2,3) = 1

Pls check for your multiplication part too.as i am not sure though.

0

anyone verify this"

**I will give a short trick for divisibility: |w| i.e length of string is divisible by a,b.**

If a doesn't divide b and b doesn't divide a then Min. states = a*b

Case 1 : Divisible by a and b ----> If a divides b or b divides a then Min. No .of states = LCM(a,b)

Case 2: Divisible by a or b ------> If a divides b or b divides a then Min. states = GCD(a,b)

"

–1 vote

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.6k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 473
- Tier 1 Placement Questions 21
- Job Queries 61
- Projects 13

39,584 questions

46,707 answers

140,136 comments

57,865 users