MCQ Computer Science

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

1. All the regular languages can have one or more of the following descriptions:
i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
Which of the following are correct?
a) i, ii, iv
b) i, ii, iii
c) i, iv
d) i, ii, iii, iv

Explanation: The class of languages known as the regular language has atleast four different descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions

2. Which of the following options match the given statement:
Statement: The algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time.
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) None of the mentioned

Explanation: The other type of algorithms are probabalistic algorithms, which depending upon the random input, have a chance of producing incorrect results or fail to produce a result.

3. Savitch theorem relates to which of the following:
a) PSPACE=NPSPACE
b) Alternating Turing Machine
c) Time complexity
d) None of the mentioned

Explanation: Some important conclusions of Savitch theorem includes:
a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.
b) NL?L2

4. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process of repeating y 0 or more times before checking that they still belong to the language L or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned

Explanation: The process of repeatation is called pumping and so, pumping is the process we perform before we check whether the pumped string belongs to L or not.

5. There exists a language L. We define a string w such that w?L and w=xyz and |w| >=n for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?
a) n
b) |y|
c) |x|
d) none of the mentioned

Explanation: It is the first conditional statement of the lemma that states that |xy|<=n, i.e. the maximum length of the substring xy in w can be n only.

6. If n objects are distributed over m places, and n < m, then some of the places receive:
a) at least 2 objects
b) at most 2 objects
c) no object
d) none of the mentioned

Explanation: This is one of the alternative formulations of the pigeon hole principle. As n < m, there will exist some place which will not receive any of the object.

7. Suppose a language L1 has 2 states and L2 has 2 states. After using the cross product construction method, we have a machine M that accepts L1 n L2. The total number of states in M:
a) 6
b) 4
c) 2
d) 8

Explanation: M is defined as: (Q, S, d, q0, F)
where Q=Q1*Q2 and F=F1*F2

8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)=_______
a) the language of two one’s and any number of zeroes
b) the language of two zeroes and any number of one’s
c) the language of two zeroes and two one’s
d) none of the mentioned

Explanation: h-1(L) is the language with two 0’s and any number of 1’s=>(1*01*01*).

9. State true or false:
Statement: Regular expression can directly be converted to DFA without intermediate steps.
a) true
b) false

Explanation: There exists subsequent steps like formation of epsilon-NFA and NFA before the formation of corresponding DFA.

10. State true or false:
Statement: If an n-state DFA accepts a string w of length n or more, then there must be a state that appears twice on the path labeled w from the start state to the final state.
a) true
b) false

Explanation: This occurs because there are atleast n+1 states along the path while traversing the string w.

11. Are ambiguous grammar context free?
a) Yes
b) No

Explanation: A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.

12. State true or false:
Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.
a) true
b) false

Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.

13. What the does the given CFG defines?
S->aSbS|bSaS|e and w denotes terminal
a) wwr
b) wSw
c) Equal number of a’s and b’s
d) None of the mentioned

Explanation: Using the derivation approach, we can conclude that the given grammar produces a language with a set of string which have equal number of a’s and b’s.

14. Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S

Explanation: The root is labelled by the start symbol. All the leaves are either labelled by a a terminal or with e.

15. A symbol X is called to be useful if and only if its is:
a) generating
b) reachable
c) both generating and reachable
d) none of the mentioned