# MCQ IN COMPUTER SCIENCE & ENGINEERING

## COMPUTER SCIENCE AND ENGINEERING

### THEORY OF COMPUTATION

 Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
The subset construction shows that every NFA accepts a
 A String B Function C Regular language D Context-free language
Explanation:

Detailed explanation-1: -For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language. Explanation: Therefore it is possible to convert an existing NFA into a DFA for the purpose of implementing a simpler machine.

Detailed explanation-2: -A DFA can be constructed from an NFA through a general process called “subset construction.” In this process, all sets of states generated by an NFA for any input are considered as states for the DFA. Subset construction is a process for converting any NFA into a DFA and thus is applicable to string matching.

Detailed explanation-3: -What is the relation between NFA-accepted languages and DFA accepted languages? Explanation: The no of languages accepted by NFA and DFA is equal.

Detailed explanation-4: -Explanation: The conversion of a non-deterministic automata into a deterministic one is a process we call subset construction or power set construction.

Detailed explanation-5: -You can construct such DFA by using Thompson or Glushkov construction (among others) to construct an NFA, and then convert it to a DFA. If a language is produced by a DFA, it is regular, and can be described by a regular expression.

There is 1 question to complete.