MCQ Computer Science

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

View Answer

Answer: d
Explanation: Computationally Universal or Turing Complete is a set of data manipulation rules if it can be used to simulate a single-taped turing machine.
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

View Answer

Answer: c
Explanation: Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has the production rule where the production is context dependent i.e. aAb->agb.

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

View Answer

Answer: a
Explanation: The children of a node are ordered from the left and drawn so. If N is to the left of node M, then all the descendents of N are considered to be to the left of all the descendents of M.

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

View Answer

Answer: b
Explanation: The grammar is not in CNF if it violates the normal form of the productions which is strictly restricted.

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

View Answer

Answer: d
Explanation: The mentioned are the correct and proper functions of a shift reduce parsers. The parsing methods are most commonly used for parsing programming languages, etc.

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

View Answer

Answer: d
Explanation: B was programming language designed by Dennis Ritchie and Ken Thompson for recursive, non numeric, system and language softwares. It was a typeless language, everything is a word.

7. troff and nroff are _________ in Unix.
a) functions
b) typesetting tools
c) System sofwares
d) None of the mentioned

View Answer

Answer: b
Explanation: Early examples of computer markup languages can be found in typesetting tools like troff and nroff in Unix.

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

View Answer

Answer: a
Explanation: The production can be either itself or an empty string. Thus the empty string has more than one leftmost derivations, depending on how many times R->R is being used.

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

View Answer

Answer: c
Explanation: When we reach the acceptance state and find the stack to be empty, we say, the string has been accepted by the push down automata.

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

View Answer

Answer: d
Explanation: DPDA or Deterministic Push down automata has atmost one transition applicable to each configuration.

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

View Answer

Answer: a
Explanation: Deterministic Context free languages(one accepted by PDA by final state), are drastically different from the context free languages. For example they are closed under complementation and not union.

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

View Answer

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

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

View Answer

Answer: a
Explanation: V is the set of non terminal symbols while T is the st of terminal symbols, their intersection would always be null.

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

View Answer

Answer: b
Explanation: The root or interms of the grammar, starting variable can not be a terminal.

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

View Answer

Answer: b
Explanation: The modified grammar aftyer the removal of nullable can be shown as:
B->aAbC| abC
B->bAbA| bbA| bAb| bb
A->bB

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button