Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-45

1. What does NP stands for in complexity classes theory?
a) Non polynomial
b) Non-deterministic polynomial
c) Both (a) and (b)
d) None of the mentioned

Explanation: NP is said to be one of the most fundamental complexity classes. NP is an acronym for Non deterministic polynomial time.

2. A ___________ is a multi tape turing machine whose input tape is read only.
a) Counter Machine
b) Multi-stack
c) Alternating Turing machine
d) None of the mentioned

Explanation: Counter machines are offline(a multitape turing machine whose input is read only) whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a blank symbol B.

3. Which of the following can generate Unrestricted grammars?
a) Pentonnen Normal form
b) Floyd Normal form
c) Greibach Normal form
d) None of the mentioned

Explanation: Pentonnen Normal form(for Unrestricted grammars) is a special case where there is a slight modification in the format of Kuroda Normal form.
A->BC
A->a
4. Which of the following parameters cannot be used to restrict a turing machine?
a) tape alphabets
b) number of tapes
c) number of states
d) none of these

Explanation: Another procedure to restrict a turing machine is to limit the size of tape alphabet or reduce the number of states. If the tape alphabets, number of tapes or number of states are limited, then there is only a finite number of different turing machine, so the restricted model is more powerful than the original one.
5. Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method

Explanation: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.
6. Unix sort command uses _________ as its sorting technique.
a) Quick Sort
b) Bucket Sort
d) Merge Sort

Explanation: Quicksort is the method of choice in many applications( Unix sort command) with O(nlogn) in worst case.
7. Hamilton Circuit problem is a special case of ____________
a) travelling salesman problem
b) halting problem
c) hitting set
d) none of the mentioned

Explanation: Hamilton circuit problem is a special case of travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).
8. The pumping lemma is often used to prove that a language is:
a) Context free
b) Not context free
c) Regular
d) None of the mentioned

Explanation: The pumping lemma is often used to prove that a given language L is non-context-free, by showing that arbitrarily long strings s are in L that cannot be “pumped” without producing strings outside L.
9. Which of the games fill under the category of Turing-complete?
a) Minecraft
b) Minesweeper
c) Dwarf Fortress
d) All of the mentioned

Explanation: Many games fall under the category og turing complete:
a) Minecraft
b) Minesweeper
c) Dwarf Fortress
d) Conway’s Game of Life
e) Pokemon Yellow, etc.
10. Which of the following is true for The Halting problem?
a) It is recursively ennumerable
b) It is undecidable
c) Both (a) and (b)
d) None of the mentioned

Explanation: Halting problem: Does a given Turing machine M halt on a given input w?
11. A formal language is recursive if :
a) a total turing machine exists
b) a turing machine that halts for every input
c) turing machine rejects if the input does not belong to the language
d) all of the mentioned

Explanation: A formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.
12. Which of the production rule can be accepted by Chomsky grammar?
a) A->BC
b) A->a
c) S->e
d) All of the mentioned

Explanation: in CNF, the production rules are of the form:
A->BC
A-> a
S->e
13. Given grammar:
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit productions?
a) A
b) bb
c) aA
d) A| bb

Explanation: The simplified grammar can be presented as follows:
S->aA| aB
A->a
B-> bb
14. For each production in P of the form:
A-> x1x2x3…xn
put into P’ that production as well as all those generated by replacing null variables with e in all possible combinations. If all x(i) are nullable,
a) A->e is put into P’
b) A->e is not put into P’
c) e is a member of G’
d) None of the mentioned

Explanation: It is an exception that A->e is not put into P’ if all x(i) are nullable variables.
15. Simplify the given grammar:
A-> a| aaA| abBc
B-> abba| b
a) A-> a| aaA| ababbAc| abbc
b) A-> a| aaA| ababbAc| abbc, B-> abba|b
c) A-> a| aaA| abbc, B->abba
d) None of the mentioned