Bissoy.com
Doctors Medicines MCQs Q&A

Which of the following statement(s) is/are TRUE? (i) For every NFA with an arbitrary number of final states, there is an equivalent NFA with only one final state. (ii) A language that is accepted by a DFA will also be accepted by some NFA.

Which of the following statement(s) is/are TRUE? (i) For every NFA with an arbitrary number of final states, there is an equivalent NFA with only one final state. (ii) A language that is accepted by a DFA will also be accepted by some NFA. Correct Answer Both (i) and (ii)

The correct answer is option 4.

Concept​:

Option i: For every NFA with an arbitrary number of final states, there is an equivalent NFA with only one final state.

True, Every NFA with more than one final state can be converted into an NFA with a single final state. Add a new state to the NFA and introduce epsilon transitions from every old final state to the new state. Make the new state the final state and all the old final states as nonfinal states.

Option ii: A language that is accepted by a DFA will also be accepted by some NFA.

True, A language that is accepted by a DFA will also be accepted by some NFA because there exist many paths for specific input from the current state to the next state among one path the valid string will go to the final state.

A language accepted by a regular expression is also accepted by some NFA but not necessarily accepted by a DFA.

Hence the correct answer is Both (i) and (ii).

Related Questions

Which of the following options is correct? Statement 1: Initial State of NFA is Initial State of DFA. Statement 2: The final state of DFA will be every combination of final state of NFA.
Let L ⊆ {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states? 
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least?
Consider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is ∑*. II. There exists a regular language A such that for all languages B, A ∩ B is regular. Which one of the following is CORRECT?
If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?
There exists an initial state, 17 transition states, 7 final states and one dumping state, Predict the maximum number of states in its equivalent DFA?
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are
Let be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
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.
Read the passage carefully and choose the best answer to each question out of the four alternatives.
Doing an internship at the University of Lille in France, I almost always found myself stuck whenever I had to speak to non-Indians about India or on anything'Indian'. This was more because of the subtle differences in the way the French understood India in comparison to what I thought was 'Indian'. For instance, when I,or any Indian for that matter, say 'Hindi' is an Indian language, what it means is that it is one of the languages widely spoken in India. This need not be similar tothe understanding that the French would have when they hear of 'Hindi' as an Indian language. Because for them Hindi then becomes the only language spoken inIndia. This is a natural inference that the French, Germans, Italians and many other European nationals would tend to make, because that is generally how it is intheir own respective countries. The risk of such inappropriate generalisations made about 'Indian' is not restricted to language alone but also for India's landscape,cuisine, movies, music, climate, economic development and even political ideologies. The magnitude of diversity of one European country can be easily compared tothat of one of the Indian State, isn't it? Can they imagine that India is one country whose diversity can be equated to that of the entire European continent? Theonus is upon us to go ahead and clarify the nuances in 'Indianness' while we converse. But why should one do so? How does it even matter to clarify? Why do some French people think that Hindi is the only Indian language?