1. Are Multitape and Multitrack turing machines same?
a) Yes
b) No
c) Somewhat yes
d) Cannot tell
View Answer
Answer: a
Explanation: Multitrack turing machines are special types of Multitape turing machines. In a standard n-tape Turing machine, n heads move independently along n-tracks.
Explanation: Multitrack turing machines are special types of Multitape turing machines. In a standard n-tape Turing machine, n heads move independently along n-tracks.
Statement : A language is turing recognizable if an only if ___________
a) an enumerator enumerates it
b) it is finite
c) both (a) and (b)
d) none of the mentioned
View Answer
Answer: a
Explanation: If an Enumerator E enumerates a language L, there is a turing machine M that recognizes language L. Also, If a turing machine M recognizes a language L, there is an enumerator for L.
Explanation: If an Enumerator E enumerates a language L, there is a turing machine M that recognizes language L. Also, If a turing machine M recognizes a language L, there is an enumerator for L.
a) Yes
b) No
c) Maybe
d) Cannot predict
View Answer
Answer: b
Explanation: Any recursive ennumerable language is not closed under complementation.
Explanation: Any recursive ennumerable language is not closed under complementation.
a) Decidable
b) Undecidable
c) Computable
d) None of the mentioned
View Answer
Answer: b
Explanation: The problems that can be solved by a turing machine can divided into two classes:
a) Those that have an algorithm
b) Intractable problems: Those that are only solved by a turing machine that may run forever on inputs they do not accept.
Explanation: The problems that can be solved by a turing machine can divided into two classes:
a) Those that have an algorithm
b) Intractable problems: Those that are only solved by a turing machine that may run forever on inputs they do not accept.
a) HTML
b) LaTeX
c) PostScript
d) None of the mentioned
View Answer
Answer: d
Explanation: There are three categories of electronic markup: presentational, procedural, and descriptive markup. Examples are XML, HTML, LaTeX, etc.
Explanation: There are three categories of electronic markup: presentational, procedural, and descriptive markup. Examples are XML, HTML, LaTeX, etc.
a) Push
b) Delete
c) Insert
d) Pop
View Answer
Answer: a, d
Explanation: Push and pop are the operations we perform to operate a stack. A stack follows the LIFO principle, which states its rule as: Last In First Out.
Explanation: Push and pop are the operations we perform to operate a stack. A stack follows the LIFO principle, which states its rule as: Last In First Out.
Statement: Counter Automaton can exist for the language L={0i1i|i>=0}
a) true
b) false
View Answer
Answer: a
Explanation: The PDA works as follows. Instead of saving excess 0’s or 1’s on the stack, we save *’s and use two different states to indicate which symbol there is currently a surplus of. The state q0 is the initial state and the only accepting state.
Explanation: The PDA works as follows. Instead of saving excess 0’s or 1’s on the stack, we save *’s and use two different states to indicate which symbol there is currently a surplus of. The state q0 is the initial state and the only accepting state.
a) Removal of useless symbols
b) Removal of unit productions
c) Removal of null production
d) None of the mentioned
View Answer
Answer: d
Explanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:
a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.
Explanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:
a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.
S->aA
A->a
A->B
B->A
B->bb
Which among the following will be the simplified grammar?
a) S->aA|aB, A->a, B->bb
b) S->aA|aB, A->B, B->bb
c) S->aA|aB, A->a, B->A
d) None of the emntioned
View Answer
Answer: a
Explanation: Step 1: Substitute A->B
Step 2: Remove B->B
Step 3: Substitute B->A
Step 4: Remove Repeated productions
Explanation: Step 1: Substitute A->B
Step 2: Remove B->B
Step 3: Substitute B->A
Step 4: Remove Repeated productions
a) CYK Algorithm
b) Bottom up parsing
c) Preprocessing step in some algorithms
d) All of the mentioned
View Answer
Answer: d
Explanation: Besides the theoretical significance of CNF, it conversion scheme is helpful in algorithms as a preprocessing step, CYK algorithms and the bottom up parsing of context free grammars.
Explanation: Besides the theoretical significance of CNF, it conversion scheme is helpful in algorithms as a preprocessing step, CYK algorithms and the bottom up parsing of context free grammars.
a) Greibach Normal form
b) Chomsky Normal form
c) Backus Naur form
d) All of the mentioned
View Answer
Answer: b
Explanation: It requires the presence of a context free grammar into Chomsky Normal form to operate. However, every context free grammar can be converted into CNF for keeping the sense of grammar equivalent.
Explanation: It requires the presence of a context free grammar into Chomsky Normal form to operate. However, every context free grammar can be converted into CNF for keeping the sense of grammar equivalent.
a) x+1
b) x
c) x-1
d) x2
View Answer
Answer: a
Explanation: There exists a property of all strings in the language that are of length p, where p is the constant-called the pumping length .For a finite language L, p is equal to the maximum string length in L plus 1.
Explanation: There exists a property of all strings in the language that are of length p, where p is the constant-called the pumping length .For a finite language L, p is equal to the maximum string length in L plus 1.
a) Remove useless variable
b) Check if a start variable S is useless
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: The empty-language question can be stated as: For context free grammar G find if L(G) =f?
Explanation: The empty-language question can be stated as: For context free grammar G find if L(G) =f?
a) Transition graph
b) Transition table
c) Queue and Input tape
d) All of the mentioned
View Answer
Answer: d
Explanation: We can represent a turing machine, graphically, tabularly and diagramatically.
Explanation: We can represent a turing machine, graphically, tabularly and diagramatically.
Statement: RASP is to RAM like UTM is to turing machine.
a) true
b) false
View Answer
Answer: a
Explanation: The Rasp is a random access machine model that, unlike the RAM has its program in its registers together with its input. The registers are unbounded(infinite in capacity); whether the number of registers is finite is model-specific.
Explanation: The Rasp is a random access machine model that, unlike the RAM has its program in its registers together with its input. The registers are unbounded(infinite in capacity); whether the number of registers is finite is model-specific.
