Equivalence of DFA and NDFA Questions-Answers- Theory of Computation
Q1➡|Equivalence of DFA and NDFA It is less complex to prove the closure properties over regular languages using
i ➥ DFA
ii ➥ PDA
iii ➥ NFA
iv ➥ Can’t be said
Show Answer With Best Explanation
Answer: iii Explanation: Upload Soon
Q2➡|Equivalence of DFA and NDFA Under which of the following operation, NFA is not closed?
i ➥ Union
ii ➥ Kleene
iii ➥Intersection
iv ➥ Not mentioned
Show Answer With Best Explanation
Answer: iv Explanation: NFA is said to be closed under Union, Intersection, Concatenation, Kleene, Negation
Q3➡|Equivalence of DFA and NDFA make an automaton which accepts a given string for all the occurrence of ‘1001’ in it. How many number of transitions would be use such that, the string processing application works?
i ➥ 9
ii ➥ 10
iii ➥ 11
iv ➥ 12
Show Answer With Best Explanation
Answer: i Explanation: Upload Soon
Q4➡|Equivalence of DFA and NDFA Which of the following is an application of Finite Automaton?
i ➥ Text Search
ii ➥ Compiler Design
iii ➥ Grammar Parsers
iv ➥ All of the Above
Show Answer With Best Explanation
Answer: iv Explanation: Upload Soon
Q5➡|Equivalence of DFA and NDFA Which among the following can be an example of application of finite state machine(FSM)?
i ➥ Stack
ii ➥ Communication Link
iii ➥ Adder
iv ➥ None of the mentioned
Show Answer With Best Explanation
Answer: i Explanation: Upload Soon
Q6➡|Equivalence of DFA and NDFA Which of the following do we use to form an NFA from a regular expression?
i ➥ Thompson Construction Method
ii ➥ Scott Construction Method
iii ➥ Power Set Construction Method
iv ➥ Subset Construction Method
Show Answer With Best Explanation
Answer: i Explanation: Upload Soon
Q7➡|Equivalence of DFA and NDFA Which among the following is not an application of Finite-state machine (FSM)?
i ➥ State charts
ii ➥ Lexical Analyser
iii ➥ BOT
iv ➥ Tower of Hanoi Problem.
Show Answer With Best Explanation
Answer: iv Explanation: application of FSM – recognizing the pattern using regular expressions,Lexical Analyser, Computer BOT (used in games), State charts,combination and sequential circuits using Mealy and Moore Machines,text editors,implementation of spell checkers. -Tower of Hanoi Problem is application of Push Down Automata (PDA) Ans- iv
Q8➡|Equivalence of DFA and NDFA L1= {w | w does not contain the string tr } L2= {w | w does contain the string tr} Given ∑= {t, r}, The difference of the minimum number of states required to form L1 and L2?
i ➥ 2
ii ➥ 1
iii ➥ 0
iv ➥ more then 2
Show Answer With Best Explanation
Answer: iii Explanation: Upload Soon
Q9➡|Equivalence of DFA and NDFA Predict the number of transitions required to automate the following language using only 3 states: L= {w | w ends with 00}
i ➥ 4
ii ➥ 3
iii ➥ 2
iv ➥ more then 5
Show Answer With Best Explanation
Answer: ii Explanation: Upload Soon
Q10➡|Equivalence of DFA and NDFA The total number of states to build the given language using DFA: L= {w | w has exactly 2 a’s and at least 2 b’s}
