250+ TOP MCQs on Regular Languages and D-PDA and Answers

Automata Theory Multiple Choice Questions on “Regular Languages and D-PDA”.

1. Which of the following is analogous to the following?
:NFA and NPDA
a) Regular language and Context Free language
b) Regular language and Context Sensitive language
c) Context free language and Context Sensitive language
d) None of the mentioned

Answer: a
Clarification: All regular languages can be accepted by a non deterministic finite automata and all context free languages can be accepted by a non deterministic push down automata.

2. Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no symbols can be repeated.
a) 120
b) 625
c) 360
d) 36

Answer: b
Clarification: Using the permutation rule, we can calculate that there will be total of 625 permutations on 5 elements taking 4 as the length.

3. Which of the following relates to Chomsky hierarchy?
a) Regular<CFL<CSL<Unrestricted
b) CFL<CSL<Unrestricted<Regular
c) CSL<Unrestricted<CF<Regular
d) None of the mentioned

Answer: a
Clarification: The chomsky hierarchy lays down the following order: Regular<CFL<CSL<Unrestricted

4. A language is accepted by a push down automata if it is:
a) regular
b) context free
c) both (a) and (b)
d) none of the mentioned

Answer: c
Clarification: All the regular languages are the subset to context free languages and thus can be accepted using push down automata.

5. Which of the following is an incorrect regular expression identity?
a) R+f=R
b) eR=e
c) Rf=f
d) None of the mentioned

Answer: b
Clarification: e is the identity for concatenation. Thus, eR=R.

6. Which of the following strings do not belong the given regular expression?
(a)*(a+cba)
a) aa
b) aaa
c) acba
d) acbacba

Answer: d
Clarification: The string acbacba is unacceptable by the regular expression (a)*(a+cba).

7. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.
a) (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b) (bbbb+aaaa)*
c) ((a+b)(a+b)(a+b)(a+b))*
d) None of the mentioned

Answer: c
Clarification: Other mentioned options do not many of the combinations while option c seems most reliable.

8. Which of the following strings is not generated by the given grammar:
S->SaSbS|e
a) aabb
b) abab
c) abaabb
d) None of the mentioned

Answer: d
Clarification: All the given options are generated by the given grammar. Using the methods of left and right derivations, it is simpler to look for string which a grammar can generate.

9. abb*c denotes which of the following?
a) {abnc|n=0}
b) {abnc|n=1}
c) {anbc|n=0}
d) {abcn|n>0}

Answer: b
Clarification: Here, the first mentioned b is fixed while the other can be zero or can be repeated any number of time.

10. The following denotion belongs to which type of language:
G=(V, T, P, S)
a) Regular grammar
b) Context free grammar
c) Context Sensitive grammar
d) All of the mentioned

Answer: b
Clarification: Ant formal grammar is represented using a 4-tuple definition where V= finite set of variables, T= set of terminal characters, P=set of productions and S= Starting Variable with certain conditions based on the type of formal grammar.

250+ TOP MCQs on Multitape Turing Machines and Answers

Automata Theory Multiple Choice Questions on “Multitape Turing Machines”.

1. A turing machine with several tapes in known as:
a) Multi-tape turing machine
b) Poly-tape turing maching
c) Universal turing machine
d) All of the mentioned

Answer: a
Clarification: A multitape turing machine is an ordinary turing machine with multiple tapes. Each tape has its own head to control the read and write.

2. A multitape turing machine is ________ powerful than a single tape turing machine.
a) more
b) less
c) equal
d) none of the mentioned

Answer: a
Clarification: The multitape turing machine model seems much powerful than the single tape model, but any multi tape machine, no matter how many tapes, can be simulated by single taped TM.

3. In what ratio, more computation time is needed to simulate multitape turing machines using single tape turing machines?
a) doubly
b) triple
c) quadratically
d) none of the mentioned

Answer: c
Clarification: Thus, multitape turing machines cannot calculate any more functions than single tape machines.

4. Which of the following is true for two stack turing machines?
a) one read only input
b) two storage tapes
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: 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.

5. Which of the following is not a Non deterministic turing machine?
a) Alternating Turing machine
b) Probabalistic Turing machine
c) Read-only turing machine
d) None of the mentioned

Answer: c
Clarification: A read only turing machine or 2 way deterministic finite automaton is a class of model of computability that behaves like a turing machine, and can move in both directions across input, except cannot write to its input tape.

6. Which of the turing machines have existential and universal states?
a) Alternating Turing machine
b) Probalistic Turing machine
c) Read-only turing machine
d) None of the mentioned

Answer: a
Clarification: ATM is divide into two sets: an existential state is accepting if some transitions leads to an accepting state; an universal state is accepting if every transition leads to an accepting state.

7. Which of the following is false for Quantum Turing machine?
a) Abstract machine
b) Any quantum algorithm can be expressed formally as a particular quantum turing machine
c) Gives a solution to ‘Is a universal quantum computer sufficient’
d) None of the mentioned

Answer: c
Clarification: ‘Is a universal quantum computer sufficient’ is one of the unsolved problem from physics.

8. A deterministic turing machine is:
a) ambiguous turing machine
b) unambiguous turing machine
c) non-deterministic
d) none of the mentioned

Answer: b
Clarification: A deterministic turing machine is unambiguous and for every input, there is exactly one operation possible. It is a subset of non-deterministic Turing machines.

9. Which of the following is true about Turing’s a-machine?
a) a stands for automatic
b) left ended, right end-infinite
c) finite number of tape symbols were allowed
d) all of the mentioned

Answer: d
Clarification: Turings a- machine or automatic machine was left ended,right end infinite.Any of finite number of tape symbols were allowed and the 5 tuples were not in order.

10. Which of the following is a multi tape turing machine?
a) Post turing Machine
b) Wang-B Machine
c) Oblivious turing Machine
d) All of the mentioned

Answer: c
Clarification: An oblivious turing machine where movements of various heads are fixed functions of time, independent of the input. Pippenger and Fischer showed that any computation that can be performed by a multi-tape Turing machine in n steps can be performed by an oblivious two-tape Turing machine in O(n log n) steps.