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
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.
Explanation: We use the concept of dependency graph inorder to check, whether any of the variable is reachable from the starting variable or not.
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
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.
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
Answer: c
Explanation: Conversely, every context frr grammar can be converted into Chomsky Normal form and to other forms.
Explanation: Conversely, every context frr grammar can be converted into Chomsky Normal form and to other forms.
a) {aibici|i>=0}
b) {0i1i|i>=0}
c) {ss|s?{a,b}*}
d) None of the mentioned
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.
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.
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
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.
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.
State true or false:
a) true
b) false
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).
Explanation: Inorder to describe formally what a Turing machine does, we need to develop a notation for configurations or Instantaneous descriptions(ID).
a) Copying a string
b) Deleting a symbol
c) Accepting a pal
d) Inserting a symbol
View Answer
Answer: d
Explanation: Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.
Explanation: Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.
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
Answer: a
Explanation: None.
Explanation: None.
a) Probabalistic turing machine
b) Alternative turing machine
c) Quantum turing machine
d) None of the mentioned
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.
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.
a) APTIME
b) AP
c) Quantom complexity class
d) None of the mentioned
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.
Explanation: An alternative characterization of PSPACE is a set of problems decidable by a turing machine in polynomial time, sometimes called, APTIME or AP.
a) Algebric
b) Enumerative
c) Analytic
d) Extremal
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.
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.
a) Union
b) Concatenation
c) Reversal
d) Complement
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.
Explanation: It is unknown about the closure property-complement for the complexity class NP. The question is so called NP versus co-NP problem.
a) EXPSPACE
b) DLOGTIME
c) EXPTIME-complete
d) All of the mentioned
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.
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.
a) yes
b) no
View Answer
Answer: a
Explanation: Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.
Explanation: Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.
a) decidable
b) undecidable
c) sometimes decidable
d) none of the mentioned
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.
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.
