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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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

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.

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

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

Explanation: The modified grammar aftyer the removal of nullable can be shown as:

B->aAbC| abC

B->bAbA| bbA| bAb| bb

A->bB