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

1.The given regular language corresponds to which of the given regular language

e+1+(1+0)*0+(0+1)*11

a) The language of all strings that end with 11 or 00

b) The language of all strings that end with 0 or 1

c) The language of all strings which does not end with 01

d) None of the mentioned

### View Answer

Explanation: According to the given regular expression, e is accepted by its language and it does not end with 00 or 11 or 0 or 1. Thus option a and b are eliminated. Further, the regular expression is valid for the third option.

a) exponential time

b) linear time

c) logarithmic time

d) all of the mentioned

### View Answer

Explanation: We can eliminate e-transitions from an n state epsilon-NFA to build an ordinary NFA in O(n3) time, without changing the number of states.Next, producing to DFA can take exponential time.

a) Closure property

b) Decision property

c) Closure & Decision property

d) None of the mentioned

### View Answer

Explanation: A decision property of a language class is an algorithm that takes a formal description of a language(e.g., a DFA) and tells whether or not some property holds.

In the given definition, what does S represents?

a) Accepting State

b) Starting Variable

c) Sensitive Grammar

d) None of these

### View Answer

Explanation: G=(V, ?, p, S), here V=Finite set of variables, ?= set of terminals, p= finite productions, S= Starting Variable.

5. Is the given statement correct?

Statement: The mere existence of several derivations is not an issue, its is the existence of several parse trees that ruins a grammar.

a) Yes

b) No

### View Answer

Explanation: It is also true that multiple leftmost or rightmost derivations do cause ambiguity. Unfortunately, it is not possible to remove the ambiguity always.

6. State true or false:

Statement: LALR parsers uses tables rather than mutually recursive functions.

a) true

b) false

### View Answer

Explanation: It is exactly the opposite case where LALR parsers uses mutually recursive functions instead of tables. It is a simplified version of canonical left to right parser.

7. Which of the following are not used to express CFG?

a) BNF

b) EBNF, ABNF

c) Van Wijngaarden form

d) None of the mentioned

### View Answer

Explanation: W grammar or van Wijngaarden form is used to define potentially infinite context free grammars in a finite number of rules. It is an example of larger class of affix grammars. This technique was used to define the P/L Algol 68.

a) Standard Generalized Markup Language

b) Standardized General Markup Language

c) Standard General Markup Language

d) Standard Generalized Markdown Language

### View Answer

Explanation: SGML is an acronym for Standard Generalized Markup Language.

Statement: if R then if T then P else V

a) 2

b) 3

c) 4

d) 1

### View Answer

Explanation: Dangling else problem

if R then (if T then P else V) and if R then (if T then P) else V are the two ways in which the given if else statement can be parsed.

10. NPDA stands for

a) Non-Deterministic Push Down Automata

b) Null-Push Down Automata

c) Nested Push Down Automata

d) All of the mentioned

### View Answer

Explanation: NPDA stands for non-deterministic push down automata whereas DPDA stands for deterministic push down automata.

S->e

S->SS

S->0S1|1S0

State which of the following is true for the given

a) Language of all and only Balanced strings

b) It contains equal number of 0’s and 1’s

c) Ambiguous Grammar

d) All of the mentioned

### View Answer

Explanation: A string is said to be balanced if it consist of equal number of 0’s and 1’s.

a) process the whole string

b) end in final state

c) end with an empty stack

d) all of the mentioned

### View Answer

Explanation: The empty stack in the end is our requirement relative to finite state automatons.

13. 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

### View Answer

Explanation: 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

a) -> m a i n

-> | epsilon

-> A | B | … | Z | a | b … | z

b) –> m a i n

–>

–> A | B | … | Z | a | b … | z

c) –> m a i n

–> | epsilon

–> A | B | … | Z | a | b … | z

d) None of the mentioned

### View Answer

Explanation: None.

15. Given grammar G:

S->aS|A|C

A->a

B->aa

C->aCb

Find the set of variables thet can produce strings only with the set of terminals.

a) {C}

b) {A,B}

c) {A,B,S}

d) None of the mentioned

### View Answer

Explanation: First step: Make a set of variables that directly end up with a terminal

Second step: Modify the set with variables that produce the elements of above

generated set.

The rest variables are termed as useless.