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

1. Fill in the blank with an appropriate option.
In automata theory, ___________ is said to be Computationally Universal if can be used to simulate any single taped Turing Machine.
a) Computer’s instruction set
b) A programming language
c) Cellular Automaton
d) All of the mentioned

2. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language
3. In which order are the children of any node ordered?
a) From the left
b) From the right
c) Arbitrarily
d) None of the mentioned
4. Given Checklist:
a) G has no useless symbols
b) G has no unit productions
c) G has no epsilon productions
d) Normal form for production is violated
Is it possible for the grammar G to be in CNF with the following checklisy ?
a) Yes
b) No
5. Which of the following is true for shift reduce parsers?
a) Scans and parses the input in one forward pass over the text, without any backup.
b) A shift command advances in the input stream by one symbol
c) LALR parser
d) All of the mentioned
6. Which of the following is false for B programming language?
a) Typeless
b) Influenced by PL/I
c) Designed by Dennis Ritchie
d) None of the mentioned
7. troff and nroff are _________ in Unix.
a) functions
b) typesetting tools
c) System sofwares
d) None of the mentioned

8. State true or false:
Statement: R->R|T T->e is an ambiguous grammar
a) true
b) false

9. A string is accepted by a PDA when
a) Stack is empty
b) Acceptance state
c) Both (a) and (b)
d) None of the mentioned

10. A push down automata is said to be _________ if it has atmost one transition around all configurations.
a) Finite
b) Non regular
c) Non-deterministic
d) Deterministic

11. A language accepted by Deterministic Push down automata is closed under which of the following?
a) Complement
b) Union
c) Both (a) and (b)
d) None of the mentioned

12. 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
13. From the definition of context free grammars,
G=(V, T, P, S)
What is the solution of VÇT?
a) Null
b) Not Null
c) Cannot be determined, depends on the language
d) None of the mentioned
14. Which among the following is incorrect with reference to a derivation tree?
a) Every vertex has a label which is a terminal or a variable.
b) The root has a label which can be a terminal.
c) The label of the internal vertex is a variable.
d) None of the mentioned
15. Consider the following grammar:
A->e
B->aAbC
B->bAbA
A->bB
The number of productions added on the removal of the nullable in the given grammar:
a) 3
b) 4
c) 2
d) 0