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} |
| i ➥ 13 |
| ii ➥ 12 |
| iii ➥ 11 |
| iv ➥ 10 |
Show Answer With Best Explanation
Answer: iv
Explanation: Upload Soon
| Q11➡ |Equivalence of DFA and NDFA |
| i ➥ |
| ii ➥ |
| iii ➥ |
| iv ➥ |
Show Answer With Best Explanation
Answer: i
Explanation: Upload Soon
| You should also practice on below topics Regular Language Mode Deterministic Finite Automaton (DFA), Non-Deterministic Finite Automaton (NDFA), Equivalence of DFA and NDFA, Regular Languages, Regular Grammars, Regular Expressions, |