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

1. Which of the following is called Bar-Hillel lemma?

a) Pumping lemma for regular language

b) Pumping lemma for context free languages

c) Pumping lemma for context sensitive languages

d) None of the mentioned

### View Answer

Explanation: In automata theory, the pumping lemma for context free languages, also kmown as the Bar-Hillel lemma, represents a property of all context free languages.

2. Which of the following does not have left recursions?

a) Chomsky Normal Form

b) Greibach Normal Form

c) Backus Naur Form

d) All of the mentioned

### View Answer

Explanation: The normal form is of the format:

A->aB where the right hand side production tends to begin with a terminal symbo, thus having no left recursions.

3. Left corner parsing methof uses which of the following?

a) Top down parser

b) Bottom up parser

c) TOP down and Bottom up parser

d) None of the mentioned

### View Answer

Explanation: It is a hybrid method which works bottom up along the left edges of each subtree, and top down on the rest of the parse tree.

4. A CFG is not closed under

a) Dot operation

b) Union Operation

c) Concatenation

d) Iteration

### View Answer

Explanation: The closure property of a context free grammar does not include iteration or kleene or star operation.

5. Which of the following version of Unix came up with YACC first?

a) V3

b) V5

c) CB UNIX

d) Unix-RT

### View Answer

Explanation: Yacc appeared in version 3 of unix, though full description was published by 1975.

6. The class of languages not accepted by non deterministic, nonerasing stack automata is _______

a) NSPACE(n2)

b) NL

c) CSL

d) All of the mentioned

### View Answer

Explanation: NSPACE or non deterministic space is the computational resource describing the memory space for a non deterministic turing machine.

7. A context free grammar can be recognized by

a) Push down automata

b) 2 way linearly bounded automata

c) Both (a) and (b)

d) None of the mentioned

### View Answer

Explanation: A linearly bounded automata is a restricted non deterministic turing machine which is capable of accepting ant context free grammar.

8. For a counter automaton, with the symbols A and Z0, the string on the stack is always in the form of __________

a) A

b) AnZ0, n>=0

c) Z0An, n>=0

d) None of the mentioned

### View Answer

Explanation:The possible change in the stack contents is a change in the number of A’s on the stack.

9. Which of the following are the actions that operates on stack top?

a) Pushing

b) Popping

c) Replacing

d) All of the mentioned

### View Answer

Explanation: Push, pop and replace are all the basic and only operations that takes place on stack top.

10. Finite-state acceptors for the nested words can be:

a) nested word automata

b) push down automata

c) ndfa

d) none of the mentioned

### View Answer

Explanation: The linear encodings of languages accepted by finite nested word automata gives the class of ‘visibly pushdown automata’.

11. abb*c denotes which of the following?

a) {abnc|n=0}

b) {abnc|n=1}

c) {anbc|n=0}

d) {abcn|n>0}

### View Answer

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

12. CFGs are more powerful than:

a) DFA

b) NDFA

c) Mealy Machine

d) All of the mentioned

### View Answer

Explanation:

Context-free grammars are strictly more powerful than regular expressions:

1) Any language that can be generated using regular expressions can be generated by a context-free grammar.

2) There are languages that can be generated by a context-free grammar that cannot be generated by any regular expression.

As a corollary, CFGs are strictly more powerful than DFAs and NDFAs.

13. Given Grammar: S->A, A->aA, A->e, B->bA

Which among the following productions are Useless productions?

a) S->A

b) A->aA

c) A->e

d) B->bA

### View Answer

Explanation: Some derivations are not reachable from the starting variable. As B is not reachable from the starting variable, it is a useless symbol and thus, can be eliminated.

14. Simplify the given grammar:

S->aXb

X->aXb | e

a) S->aXb | ab, X-> aXb | ab

b) S->X | ab, X-> aXb | ab

c) S->aXb | ab, X-> S | ab

d) None of the mentioned

### View Answer

Explanation: As X is nullable, we replace every right hand side presence of X with e and produce the simplified result.

15. If C is A-derivable, C->B is a production, and B ¹ A, then B is

a) nullable

b) Non-derivable

c) A-derivable

d) None of the mentioned

### View Answer

Explanation:

If A-> B is a production, B is called A- derivable.

If C is A-derivable, C->B is a production, and B ¹ A, then B is A -derivable.

No other variables are A-derivable.