**This Might help ...**

**
**

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+13 votes

A minimum state deterministic finite automaton accepting the language

$L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$ has

- $15$ states
- $11$ states
- $10$ states
- $9$ states

+18 votes

Best answer

Answer will be (**A**) $15$ states.

We need a separate state for #$0 = 0, 1, 2$ and #$1 = 0, 1, 2, 3, 4$ giving total minimum number of states $= 3 * 5 = 15. $

This is a direct consequence of Myhill-Nerode theorem.

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

0

@Arjun Sir, So this is a cross product between 2 DFAs "number of 0 ...." and "number of 1 ...."

My question is..... Do we always get minimal DFA after cross product or we need to check if it can be minimized?

My question is..... Do we always get minimal DFA after cross product or we need to check if it can be minimized?

0

Yes,

-> divisible by 2 and 4 is clear and direct.. 4 is direct multiple.

-> divisible by 3 and 4 is direct.... they are relatively prime to each other

But if question will be like divisible by 12 and 8... Whats the answer here?

Do we need to check if it can be minimized or answer is 12*8?

-> divisible by 2 and 4 is clear and direct.. 4 is direct multiple.

-> divisible by 3 and 4 is direct.... they are relatively prime to each other

But if question will be like divisible by 12 and 8... Whats the answer here?

Do we need to check if it can be minimized or answer is 12*8?

0

@sid1221 if,L={w∣w∈{0,1}^{∗}, number of 0s and 1s in w are **divisible by 2 and 4**, respectively} Can you show how can we create the finite state machine accepting it in 4 states as per the method of lcm(2,4) ??

- 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