Breaking News
Home / MCQ Computer Science / Automata Theory Multiple Choice Quaestion & Answers (MCQs) Set-49

# 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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