Bissoy.com
Doctors Medicines MCQs Q&A

How many states are there in a minimum state deterministic finite automaton accepting the language L = {w | ∈ (0,1)*, number of 0's is divisible by 2, and number of 1's is divisible by 5, respectively}?

How many states are there in a minimum state deterministic finite automaton accepting the language L = {w | ∈ (0,1)*, number of 0's is divisible by 2, and number of 1's is divisible by 5, respectively}? Correct Answer 10

The correct answer is "option 3".

Key Points

The Finite State Machine(FSM) is a mathematical model of computation.

A finite-state automaton is an abstract machine having 5 tuples, a finite set of states & a set of rules for moving from one state to another.

EXPLANATION:

Given that the language L = {w | ∈ (0,1)* }, the number of 0's is divisible by 2, and the number of 1's is divisible by 5:

Deterministic Finite Automata(DFA) state diagram for the given language L is :

Additional Information

There are two types of finite automata:

1. Deterministic Finite Automata(DFA): In this type of automata, each pair of state & input can have only one next state.

2. Non-Deterministic Finite Automata(NFA): In NFA, each pair of state & input can have many possible next states.

Related Questions

A signal is said to be 1. Deterministic if there is no uncertainty over the signal at any instant of time. 2. Deterministic if it is expressible through a mathematical equation. 3. Random or non-deterministic if there is uncertainty over the signal at the instant of time. 4. Random or non-deterministic if it is not expressible through a mathematical equation. Which of the above statements are correct?
A deterministic finite automaton (DFA) D with alphabet ∑ = {a,b} is given below. Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least?
An Identity Card has the number ABCDEFG, not necessarily in that order, where each letter represents a distinct digit (1, 2, 4, 5, 7, 8, 9 only). The number is divisible by 9. After deleting the first digit from the right, the resulting number is divisible by 6. After deleting two digits from the right of original number, the resulting number is divisible by 5. After deleting three digits from the right of original number, the resulting number is divisible by 4. After deleting four digits from the right of original number, the resulting number is divisible by 3. After deleting five digits from the right of original number, the resulting number is divisible by 2. Which of the following is a possible value for the sum of the middle three digits of the number?
Consider the following deterministic finite state automaton M. S denotes the set of seven bit in which the 1st ,4th and last bits are 1. The number of strings that are accepted by M is
For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.
Read the passage carefully and choose thebest answer to each question out of the four alternativesand click the button corresponding to it. To know language is to be able to speak it; even a childwho does not yet attend school can speak his or herlanguage. In order to speak a language it is important tolisten to it and to read a few pages in it everyday. A childpicks up language and learns to talk just as (s)he learnsto walk. Walking and talking comes naturally to a child asit grows. In our country, a child may grow up speakingmore than one language, if these languages are spoken inthe home and in the neighbourhood. we call this multilingualism. A child speaks a language or languagesmuch before (s)he starts going to school. To know alanguage then is first of all to be able to speak it as easilyand naturally as a tree year old child does. Later on thechild will learn to read and write in that language. In orderto read and write in a language, one has to speak it. But itis possible to speak a language but not able to read orwrite in it. A baby does not speak until it is nine monthsold but it understands a few words at six months of age.It has been listening ever since it was born, and even alittle before that. So the first strategy in speaking alanguage is to listen. It is necessary for one to __________ the language before(s)he writes in that language.
Consider the following Deterministic Finite Automaton M. Let S denote the set of eight-bit strings whose second, third, sixth and seventh bits are 1. The number of strings in S that are accepted by M is
The number of tuples in an extended Non Deterministic Finite Automaton: