1. Which of the following option is correct?
a) NFA is slower to process and its representation uses more memory than DFA
b) DFA is faster to process and its representation uses less memory than NFA
c) NFA is slower to process and its representation uses less memory than DFA
d) DFA is slower to process and its representation uses less memory than NFA
Explanation: NFA, while computing strings, take parallel paths, make different copies of input and goes along different paths in order to search for the result. This creates the difference in processing speed of DFA and NFA.
2. Subset Construction method refers to:
a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) ε-NFA to NFA
Explanation: The conversion of a non-deterministic automata into a deterministic one is a process we call subset construction or power set construction.
3. Given Language:
Ln= {xϵ {0,1} * | |x|≥n, nth symbol from the right in x is 1}
How many state are required to execute L3 using NFA?
a) 16
b) 15
c) 8
d) 7
Explanation: The finite automaton for the given language is made and thus, the answer can be obtained.
4. Which of the following does the given NFA represent?
a) {11, 101} * {01}
b) {110, 01} * {11}
c) {11, 110} * {0}
d) {00, 110} * {1}
Explanation: The given diagram can be analysed and thus the option can be seeked.
5. The number of transitions required to convert the following into equivalents DFA:
a) 2
b) 3
c) 1
d) 0
Explanation:
6. If L is a regular language, Lc and Lr both will be:
a) Accepted by NFA
b) Rejected by NFA
c) One of them will be accepted
d) Cannot be said
Explanation: If L is a regular Language, Lc and Lr both are regular even.
7. In NFA, this very state is like dead-end non final state:
a) ACCEPT
b) REJECT
c) DISTINCT
d) START
Explanation: REJECT state will be like a halting state which rejects a particular invalid input.
8. We can represent one language in more one FSMs, true or false?
a) TRUE
b) FALSE
c) May be true
d) Cannot be said
Explanation: We can represent one language in more one FSMs, example for a same language we have a DFA and an equivalent NFA.
9. The production of form non-terminal -> ε is called:
a) Sigma Production
b) Null Production
c) Epsilon Production
d) All of the mentioned
Explanation: The production of form non-terminal ->ε is call null production.
10. Which of the following is a regular language?
a) String whose length is a sequence of prime numbers
b) String with substring wwr in between
c) Palindrome string
d) String with even number of Zero’s
Explanation: DFSM’s for the first three option is not possible; hence they aren’t regular.