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
View Answer
Answer: a
Explanation: We use the method of proof by contradiction in pumping lemma to prove that a language is regular or not.
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer
Answer: b
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.
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.
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer
Answer: a
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.
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.
a) FrGr
b) GrFr
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: b
Explanation: If E= FG, Er=GrFr . Example: (01*)R=(1*)R(0)R
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
View Answer
Answer: a
Explanation: It is possible to parse the expression efficiently, using a technique that takes only O(n) time on a expression of length n3.
Explanation: It is possible to parse the expression efficiently, using a technique that takes only O(n) time on a expression of length n3.
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
View Answer
Answer: d
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.
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.
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
View Answer
Answer: d
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.
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.
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned
View Answer
Answer: b
Explanation: Push down automata accepts context free language.
Explanation: Push down automata accepts context free 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
View Answer
Answer: c
Explanation: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S
Explanation: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010
View Answer
Answer: a
Explanation: It is just required to put the value in the variables in the question and check if it satisfies or not.
Explanation: It is just required to put the value in the variables in the question and check if it satisfies or not.
a) semantic
b) syntactic
c) lexical
d) all of the mentioned
View Answer
Answer: b
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.
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.
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned
View Answer
Answer: b
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.
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.
a) Top down parsers
b) Bottom up parsers
c) Machine code
d) None of the mentioned
View Answer
Answer: b
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.
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.
a) dangling else problem
b) halting problem
c) maze problem
d) none of the mentioned
View Answer
Answer: a
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.
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.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
View Answer
Answer: b
Explanation: Push down automata is for Context free languages and they are termed as Type 2 languages according to Chomsky hierarchy.
Explanation: Push down automata is for Context free languages and they are termed as Type 2 languages according to Chomsky hierarchy.
