MCQ Computer Science

# Automata Theory Multiple Choice Question & Answers (MCQs) set-6

1. Which kind of proof is used to prove the regularity of a language?
a) Proof by contradiction
b) Direct proof
c) Proof by induction
d) None of the mentioned

Explanation: We use the method of proof by contradiction in pumping lemma to prove that a language is regular or not.

2. The language of balanced paranthesis is
a) regular
b) non regular
c) may be regular
d) none of the mentioned

Explanation: Given n, there is a string of balanced parentheses that begins with more than p left parentheses, so that y will contain entirely of left parentheses. By repeating y, we can produce a string that does not contain the same number of left and right parentheses, and so they cannot be balanced.

3. If L1′ and L2′ are regular languages, then L1.L2 will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned

Explanation: Regular language is closed under complement operation. Thus, if L1′ and L2′ are regular so are L1 and L2. And if L1 and L2 are regular so is L1.L2.

4. If E= FG, Er=?
a) FrGr
b) GrFr
c) Both (a) and (b)
d) None of the mentioned

Explanation: If E= FG, Er=GrFr . Example: (01*)R=(1*)R(0)R

5. Conversion of regular expression to e-NFA takes ___________ time.
a) linear
b) exponential
c) logarithmic
d) none of the mentioned

Explanation: It is possible to parse the expression efficiently, using a technique that takes only O(n) time on a expression of length n3.

6. Which of the following problems do not belong to decision properties?
a) Given two languages, are there strings that are in both
b) Is the language a subset of another regular language
c) Is the language same as another regular language
d) None of the mentioned

Explanation: To give a solution to the mentioned problems, we require decision properties and for some, we need additional tools like minimized automaton and Pumping lemma.

7. For S->0S1|e for ?={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned

Explanation: L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.

8. The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned

Explanation: Push down automata accepts context free language.

9. Which among the following is the correct grammar for the given language?
L={x?{0,1}*|number of zeroes in x¹number of one’s in x}
a) S-> 0|SS|1SS|SS1|S1S
b) S-> 1|0S|0SS|SS0|S0S
c) S-> 0|0S|1SS|SS1|S1S
d) None of the mentioned

Explanation: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S

10. L={0i1j2k | j>i+k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010

Explanation: It is just required to put the value in the variables in the question and check if it satisfies or not.

11. If w belongs to L(G), for some CFG, then w has a parse tree, which tell us the ________ structure of w.
a) semantic
b) syntactic
c) lexical
d) all of the mentioned

Explanation: A parse tree or concrete syntactic tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context free grammar.

12. Which of the following parser reaches the root symbol of the tree at last?
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned

Explanation: Bottom up parser starts from the bottom with the string and comes up to the start symbolusing a parse tree or a derivation tree.

13. The YACC takes C code as input and outputs_________
a) Top down parsers
b) Bottom up parsers
c) Machine code
d) None of the mentioned

Explanation: The YACC takes C code as input and produces shift reduce parsers in C,also known as Bottom up parsers which execute C snippets with the associated rule.

14. Which of the following is an real-world programming language ambiguity?
a) dangling else problem
b) halting problem
c) maze problem
d) none of the mentioned

Explanation: Dangling else problem: In many languages,the else in an if-then-else statement is optional, which results into nested conditionals being ambiguous, at least in terms of the CFG.

15. Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0