**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 6.3k
- Digital Logic 2.4k
- Programming & DS 4.4k
- Algorithms 3.8k
- Theory of Computation 4.8k
- Compiler Design 1.8k
- Databases 3.5k
- CO & Architecture 3k
- Computer Networks 3.5k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 490
- Tier 1 Placement Questions 23
- Job Queries 64
- Projects 17

42,296 questions

48,419 answers

153,540 comments

62,661 users