amazon

shopclues

myntra

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

View Answer

View Answer

Answer: a
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

View Answer

View Answer

Answer: c
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

View Answer

View Answer

Answer: c
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

View Answer

View Answer

Answer: b
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

View Answer

View Answer

Answer: d
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

View Answer

View Answer

Answer: a
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

View Answer

View Answer

Answer: d
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

View Answer

View Answer

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

View Answer

View Answer

Answer: a
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

View Answer

View Answer

Answer: d
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

View Answer

View Answer

Answer: b
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

View Answer

View Answer

Answer: d
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

View Answer

View Answer

Answer: c
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

View Answer

View Answer

Answer: a
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

View Answer

View Answer

Answer: a
Explanation: A language is recursive if there exists a turing machine such that it halts i.e. accepts if the input belongs to the language else rejects. It is better called Turing decidable language.

Check Also

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

1. A DTD is associated with a XML file by means of ___________ a) Function …

Leave a Reply

Your email address will not be published. Required fields are marked *

error: Content is protected !!