## Automata Theory Questions and Answers Part-8

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