Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  A minimum state deterministic finite automato... Start Learning for Free
A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has
  • a)
    15 states
  • b)
    11 states
  • c)
    10 states
  • d)
    9 states
Correct answer is option 'A'. Can you explain this answer?
Verified Answer
A minimum state deterministic finite automaton accepting the language ...
Here a string w of 0's and 1's should have the property that, the no of 0's in the string w should be divisible by 3 (N(0) % 3 =0), and the number of 1's the string w should be divisible by 5 (N(1) % 5 =0).
Having said that, the Language will contain the strings such as : {ε , 000, 11111, 00011111, 00111101 , 11111000, 10101011 , 00000011111,....and so on}
So, strings accepted by the automaton have to be of length 0, 3, 5, 8, 11, 13, 14, 16....and so on, i.e. equation for length will be 3x + 5y (where x,y>=0) Modulo 3 gives remainder as (0, 1, 2) , and Modulo 5 gives remainder as (0, 1, 2, 3, 4).
Hence 3 * 5 sates, i.e. there will be 15 states in the automaton to represent this. Please comment below if you find anything wrong in the above post.
View all questions of this test
Most Upvoted Answer
A minimum state deterministic finite automaton accepting the language ...
To construct a minimum state deterministic finite automaton (DFA) accepting the language L = {w | w ∈ {0,1}*, the number of 0s and 1s in w are divisible by 3 and 5, respectively}, we need to consider the divisibility of the number of 0s and 1s by 3 and 5, respectively.

Since the language L requires both the number of 0s and 1s to be divisible by 3 and 5, respectively, we need to design the DFA in such a way that it keeps track of the number of 0s and 1s modulo 3 and 5, respectively.

Let's divide the problem into two parts: tracking the number of 0s and 1s modulo 3 and modulo 5.

Tracking the Number of 0s Modulo 3:
- Let's consider the DFA states based on the remainder of the number of 0s divided by 3.
- We can have a total of 3 states: 0, 1, and 2.
- Initially, the DFA is in state 0, as no 0s have been encountered yet.
- Upon encountering a 0, the DFA remains in the same state, as the remainder is unchanged.
- Upon encountering a 1, the DFA transitions to the next state, as the remainder increases by 1.
- After three transitions, the DFA should return to state 0, as the remainder should be divisible by 3.

Tracking the Number of 1s Modulo 5:
- Let's consider the DFA states based on the remainder of the number of 1s divided by 5.
- We can have a total of 5 states: 0, 1, 2, 3, and 4.
- Initially, the DFA is in state 0, as no 1s have been encountered yet.
- Upon encountering a 1, the DFA transitions to the next state, as the remainder increases by 1.
- After five transitions, the DFA should return to state 0, as the remainder should be divisible by 5.

Combining the DFA for the Number of 0s and 1s:
- Now, we need to combine the two DFAs.
- We can create a new DFA with 3 * 5 = 15 states to represent all possible combinations of the remainders of the number of 0s and 1s modulo 3 and 5, respectively.
- The initial state of the DFA is the combination of state 0 for the number of 0s modulo 3 and state 0 for the number of 1s modulo 5.
- For each input symbol (0 or 1), the DFA transitions to the next state based on the current state and the input symbol.
- After analyzing each input symbol, if the DFA is in the state representing the combination of 0 for the number of 0s modulo 3 and 0 for the number of 1s modulo 5, the input string is accepted.

Therefore, the minimum state deterministic finite automaton accepting the language L requires 15 states.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer?
Question Description
A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer?.
Solutions for A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer?, a detailed solution for A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer? has been provided alongside types of A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} hasa)15 statesb)11 statesc)10 statesd)9 statesCorrect answer is option 'A'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev