MCQ Computer Science

Automata Theory Multiple Choice Quaestion & Answers (MCQs) Set-49

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.

2. Complete the following statement:
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.

3. Statement: If L id R.E., Lc needs to be R.E. Is it correct?
a) Yes
b) No
c) Maybe
d) Cannot predict

View Answer

Answer: b
Explanation: Any recursive ennumerable language is not closed under complementation.

4. The problems which have no algorithm, regardless of whether or not they are accepted by a turing machine that fails to halts on some input are referred as:
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.

5. Which of the following is not an example of electronic mark up?
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.

6. Which of the operations are eligible in PDA?
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.

7. State true or false:
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.

8. Which of the following are non essential while simplifying a grammar?
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.

9. Given a Grammar G:
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

10. In which of the following, does the CNF conversion find its use?
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.

11. The standard version of CYK algorithm operates only on context free grammars in the following form:
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.

12. What is the pumping length of string of length x?
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.

13. Which of the following belong to the steps to prove emptiness?
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?

14. Turing machine can be represented using the following tools:
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.

15. State true or false:
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.

Related Articles

Leave a Reply

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

Back to top button