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

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
3. Savitch theorem relates to which of the following:
a) PSPACE=NPSPACE
b) Alternating Turing Machine
c) Time complexity
d) None of the mentioned
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

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

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
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
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

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

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

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

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
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
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
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