Breaking News
Home / MCQ Computer Science / Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-40

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

1. The use of variable dependency graph is in:
a) Removal of useless variables
b) Removal of null productions
c) Removal of unit productions
d) None of the mentioned

Explanation: We use the concept of dependency graph inorder to check, whether any of the variable is reachable from the starting variable or not.

2. Given Grammar G:
S->aA
A->a| A
B->B
The number of productions to be removed immediately as Unit productions:
a) 0
b) 1
c) 2
d) 3

Explanation: The productions in the format A-> A are removed immediately as they produce self and that is not a terminal or will not lead to a string. Hence, it is removed immediately.

3. Every grammar in Chomsky Normal Form is:
a) regular
b) context sensitive
c) context free
d) all of the mentioned

Explanation: Conversely, every context frr grammar can be converted into Chomsky Normal form and to other forms.
4. Which of the following gives a positive result to the pumping lemma restrictions and requirements?
a) {aibici|i>=0}
b) {0i1i|i>=0}
c) {ss|s?{a,b}*}
d) None of the mentioned

Explanation: A positive result to the pumping lemma shows that the language is a CFL and ist contradiction or negative result shows that the given language is not a Context Free language.
5. Which of the problems were not answered when the turing machine was invented?
a) Does a machine exists that can determine whether any arbitrary machine on its tape is circular.
b) Does a machine exists that can determine whether any arbitrary machine on its tape is ever prints a symbol
c) Hilbert Entscheidungs problem
d) None of the mentioned

Explanation: Invention of turing machine answered a lot of questions which included problems like decision problem, etc.) . Alan was able to prove the properties of computation using such model.
6. Statement: Instantaneous descriptions can be designed for a Turing machine.
State true or false:
a) true
b) false

Explanation: Inorder to describe formally what a Turing machine does, we need to develop a notation for configurations or Instantaneous descriptions(ID).
7. Which of the functions can a turing machine not perform?
a) Copying a string
b) Deleting a symbol
c) Accepting a pal
d) Inserting a symbol

Explanation: Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.
8. 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?
a) 0
b) 1
c) 2
d) Cannot be said

Explanation: None.
9. ZPP is based on ________
a) Probabalistic turing machine
b) Alternative turing machine
c) Quantum turing machine
d) None of the mentioned

Explanation: A probabalistic turing machine is a non deterministic turing machine which randomly chooses between the available transitions at each point according to some probability distribution.
10. Which of the following PSPACE can be characterized into?
a) APTIME
b) AP
c) Quantom complexity class
d) None of the mentioned

Explanation: An alternative characterization of PSPACE is a set of problems decidable by a turing machine in polynomial time, sometimes called, APTIME or AP.
11. Fibonacci number falls in the category of _________ combinatorics.
a) Algebric
b) Enumerative
c) Analytic
d) Extremal

Explanation: Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. Fibonacci series is a basic example of Enumerative Combinatorics.
12. Which of the following does not belong to the closure properties of NP class?
a) Union
b) Concatenation
c) Reversal
d) Complement

Explanation: It is unknown about the closure property-complement for the complexity class NP. The question is so called NP versus co-NP problem.
13. In the above problem, if the input is binary, the class the problem belongs?
a) EXPSPACE
b) DLOGTIME
c) EXPTIME-complete
d) All of the mentioned

Explanation: It is the set of all decision problems that have exponential run time i.e. solvable by deterministic turing machine in O(2p(n)) time, where p(n) is a polynomial function of n.
14. Can a Modified PCP problem be reduced to PCP?
a) yes
b) no

Explanation: Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.
15. Recursive languages are also known as:
a) decidable
b) undecidable
c) sometimes decidable
d) none of the mentioned