1. State true or false:
Statement: We cannot use Ogden’s lemma when pumping lemma fails.
a) true
b) false
View Answer
Explanation: Although the pumping lemma provides some information about v and x that are pumped, it says little about the location of these substrings in the string t. It can be used whenever the pumping lemma fails. Example: {apbqcrds|p=0 or q=r=s}, etc.
a) top-down parser
b) bottom-up parser
c) multitape turing machine
d) none of the mentioned
View Answer
Explanation: Given a grammar in GNF and a derivable string in the grammar with the length n, any top-down parser will halt at depth n. As the parameter ‘depth’ is mentioned, we will use a top-down parser. Example-LL parser.
3. The intersection of context free language and regular language is _________
a) regular language
b) context free language
c) context sensitive language
d) non of the mentioned
View Answer
Explanation: If a language L1 is regular and L2 is a context free language, then L1 intersection L2 will result into a context free language.
4. ‘a’ in a-machine is :
a) Alan
b) arbitrary
c) automatic
d) None of the mentioned
View Answer
Explanation: The turing machine was invented by Alan turing in 1936. He named it as a-machine(automatic machine).
5. The value of n if turing machine is defined using n-tuples:
a) 6
b) 7
c) 8
d) 5
View Answer
Explanation:
The 7-tuple definition of turing machine: (Q, S, G, d, q0, B, F)
where Q= The finite set of states of finite control
S= The finite set of input symbols
G= The complete set of tape symbols
d= The transition function
q0= The start state, a member of Q, in which the finite control is found initially.
B= The blank symbol
F= The set of final or accepting states, a subset of Q.
Statement: If L1 and L2 are recursively ennumerable languages over S, then the following is/are recursively ennumerable.
a) L1 U L2
b) L2 n L2
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: Both the union and intersection operations preserve the property of recursive ennumerablity(Theorem).
7. A multi track turing machine can described as a 6-tuple (Q, X, S, d, q0, F) where X represents:
a) input alphabet
b) tape alphabet
c) shift symbols
d) none of the mentioned
View Answer
Explanation: The 6-tuple (Q, X, S, d, q0, F) can be explained as:
Q represents finite set of states,
X represents the tape alphabet,
S represents the input alphabet
d represents the relation on states and the symbols
q0 represents the initial state
F represents the set of final states.
8. Which of the following is true for two stack turing machines?
a) one read only input
b) two storage tapes
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: Two-stack Turing machines have a read-only input and two storage tapes. If a head moves left on either tape a blank is printed on that tape, but one symbol from a “library” can be printed.
a) L-System
b) Unrestricted Grammar
c) Regular Expression
d) None of the mentioned
View Answer
Explanation: Topics like regular expressions, context free languages and unrestricted grammar including parsers like LL,SLR parsers can be covered using JFLAPS.
L={anbn|n>=0}
a) anbn
b) {ab, a2b2, a3b3, …}
c) {e, ab, a2b2, a3b3, …}
d) None of the mentioned
View Answer
Explanation: An enumerator is a turing machine with an output printer. It can use an printer as an output device to print output strings. As n also holds the value , epsilon will also be a part of the output set.
a) In general, it is impossible to predict that what a Turing-complete program will do over an arbitrarily long time.
b) It is impossible to determine for every input, whether the program will eventually stop or continue forever.
c) It is not possible to determine whether a program will return true or false.
d) None of the mentioned
View Answer
Explanation: All of the following mentioned are the conclusions of automata theory or computability theory.
12. Which of the following are undecidable problems?
a) Determining whether two grammars generate the same language
b) Determining whether a grammar is ambiguous
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: In contrast we can put up an algorithm for checking whether two FA’s are equivalent and this program can be implemented as a program.
a) recursive
b) non recursive
c) recognizable
d) none of the mentioned
View Answer
Explanation: We can refer to languages as ‘recursive’ and problems as ‘decidable’. If a language is not recursive , then we call the problem expressed by that language undecidable.
a) Post Correspondence Problem
b) Post Corresponding Problem
c) Pre Correspondence problem
d) None of the mentioned
View Answer
Explanation: PCP or Post Correspondence problem is an undecidable decision problem.
15. For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?
a) tree graphs
b) bipartite graphs
c) both (a) and (b)
d) none of the mentioned
View Answer
Explanation: For bipartite graphs, Konigs theorem allows the bipartite vertex problem to be solved in polynomial time.
