MCQ Computer Science

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

1. State true or false:
Statement: We cannot use Ogden’s lemma when pumping lemma fails.
a) true
b) false

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.

2. Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will halt at depth n.
a) top-down parser
b) bottom-up parser
c) multitape turing machine
d) none of the mentioned

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

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

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

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.

6. Choose the correct option:
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

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

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?
b) two storage tapes
c) Both (a) and (b)
d) None of the mentioned

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.

9. Which of the following topics cannot be covered using JFLAPS?
a) L-System
b) Unrestricted Grammar
c) Regular Expression
d) None of the mentioned

Explanation: Topics like regular expressions, context free languages and unrestricted grammar including parsers like LL,SLR parsers can be covered using JFLAPS.

10. For the following language, an enumerator will print:
L={anbn|n>=0}
a) anbn
b) {ab, a2b2, a3b3, …}
c) {e, ab, a2b2, a3b3, …}
d) None of the mentioned

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.

11. Which among are not the results of computational theory?
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

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

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.

13. Decidable can be taken as a synonym to:
a) recursive
b) non recursive
c) recognizable
d) none of the mentioned

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.

14. PCP stands for?
a) Post Correspondence Problem
b) Post Corresponding Problem
c) Pre Correspondence problem
d) None of the mentioned

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