Multiple choice question for engineering
Set 1
1. Which of the following derivations does a top-down parser use while parsing an input string?
a) Leftmost derivation
b) Leftmost derivation in reverse
c) Rightmost derivation
d) Rightmost derivation in reverse
Answer
Answer: a [Reason:] In top down parser takes input from Left to right constructing a leftmost derivation of the sentence.
2. The process of assigning load addresses to the various parts of the program and adjusting the code and data in the program to reflect the assigned addresses is called
a) Assembly
b) Parsing
c) Relocation
d) Symbol resolution
Answer
Answer: c [Reason:] Relocation is the process of replacing symbolic references or names of libraries with actual usable addresses in memory before running a program. Linker performs it during compilation.
3. Which of the following statements is false?
a) Left as well as right most derivations can be in Unambiguous grammar
b) An LL(1) parser is a top-down parser
c) LALR is more powerful than SLR
d) Ambiguous grammar can’t be LR(k)
Answer
Answer: a [Reason:] If a grammar has more than one leftmost (or rightmost) derivation the grammar is ambiguous. Sometimes in unambiguous grammar the rightmost derivation and leftmost derivations may differ.
4. Which of the following grammar rules violate the requirements of an operator grammar?
(i) P -> QR
(ii) P -> QsR
(iii) P -> ε
(iV) P -> QtRr
a) (i) only
b) (i) and (iii) only
c) (ii) and (iii) only
d) (iii) and (iv) only
Answer
Answer: b [Reason:] An operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar.
5. Consider the grammar with the following translation rules and E as the start symbol.
A -> A1 #B {A.value = A1.value * B.value}
| B {A.value = B.value}
B-> B1 & F {B.value = B1.value + C.value}
| C {B.value= C.value }
C -> num {C.value = num.value}
Compute E.value for the root of the parse tree for the expression:2 # 3 & 5 # 6 &4.
a) 200
b) 180
c) 160
d) 40
Answer
Answer: c [Reason:] Higher precedence operator will never produce an expression with operator with lower precedence.&># in terms of precedence order
6. Given the following expression grammar:
E -> E * F | F+E | F
F -> F-F | id
which of the following is true?
a) * has higher precedence than +
b) – has higher precedence than *
c) + and — have same precedence
d) + has higher precedence than *
Answer
Answer: b [Reason:] Precedence is that a higher precedence operator will never produce an expression with operator with lower precedence.
In the given grammar MINUS has higher precedence than ASTERIX.
7. Consider a program P that consists of two source modules M1(contains reference to a function defined in M2) and M2 contained in two different files.
a) Edit time
b) Compile time
c) Link time
d) Load time
Answer
Answer : c [Reason:] Compiler transforms source code into the machine language which is in binary . Kinds of object codes:
i defined symbols, which allow it to be called by other modules,
ii undefined symbols, which call the other modules where these symbols are defined, and
iii symbols which are used internally within object file for relocation.
8. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
a) Removing left recursion only
b) Factoring the grammar alone
c) Factoring & left recursion removal
d) None of the mentioned
Answer
Answer: d [Reason:] Factoring as well as left recursion removal do not suffice to convert an arbitrary CFG to LL(1) grammar.
9. Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states.
a) n1 is necessarily less than n2
b) n1 is necessarily equal to n2
c) n1 is necessarily greater than n2
d) None of the mentioned
Answer
Answer: b [Reason:] SLR parser has less range of context free languages than LALR but still both n1 & n2 are same for SLR & LALR respectively.
10. Match the following.
P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization
a) P-4. Q-1, R-2, S-3
b) P-3, Q-1, R-4, S-2
c) P-3, Q-4, R-1, S-2
d) P-2, Q-1, R-4, S-3
Answer
Answer: b [Reason:] Syntax analysis has Regular expressions . The code optimization goes hand in hand with data flow analysis. Whereas CFG is related to PDA which is related to syntax analysis Register allocation is used in reference with code generation.
Set 2
1. A regular expression enables a quick test to determine objects and text strings with undependable values.
a) True
b) False
Answer
Answer: a [Reason:] Because it checks for all the values and determines whether the output string matches with the given string.
2. RE can be used only for values of type string and number.
a) True
b) False
Answer
Answer: b [Reason:] No not for all values the string and numbers can we use the RE.
3. You can use RE, if you expect the value of a property to change in an unpredictable way each time its run.
a) True
b) False
Answer
Answer: b [Reason:] For every cycle the values does not change unpredictably because the type of grammar that it accepts is defined.
4. All ___________ Are automatically treated as regular expressions.
a) Programmatic description
b) Window
c) Win Object
d) Collection
Answer
Answer: a [Reason:] The programmatic description is genuinely treated as regular expression.
5. If a ‘/’ is used before a character that has no special meaning, ‘/’ is ignored.
a) True
b) False
Answer
Answer: a [Reason:] The backslash carries no significance and it is ignored.
6. The regular expression denote a language comprising all possible strings of even length over the alphabet (0, 1)
a) 1 + 0(1+0)*
b) (0+1) (1+0)*
c) (1+0)
d) (00+0111+10)*
Answer
Answer: d [Reason:] Option A does not consider even length criteria for the question.
Option B it can so happen here that from the former bracket it takes 0 or 1 and takes null from the latter then it forms a string of odd length
Option C it gives either 1 or 0.
Hence Option D is the answer.
7. The RE gives none or many instances of an x or y is
a) (x+y)
b) (x+y)*
c) (x* + y)
d) (xy)*
Answer
Answer: b [Reason:] Whether x or y is denoted by x+y and for zero or more instances it is denoted but (x+y)*.
Set 3
1. The RE in which any number of 0′s is followed by any number of 1′s followed by any number of 2′s is
a) (0+1+2)*
b) 0*1*2*
c) 0* + 1 + 2
d) (0+1)*2*
Answer
Answer: b [Reason:] The order for the desired string is 012 and foe any number of 0s we write 0* for any number of 1s we denote it by 1* and similarly for 2*.Thus 0*1*2*.
2. The regular expression have all strings of 0′s and 1′s with no two consecutive 0′s is :
a) (0+1)
b) (0+1)*
c) (0+∈) (1+10)*
d) (0+1)* 011
Answer
Answer: c [Reason:] From the former bracket we choose 0 or epsilon. Then from the latter part 1 or 10 which can be followed by 1 or 10.
3. The regular expression with all strings of 0′s and 1′s with at least two consecutive 0′s is:
a) 1 + (10)*
b) (0+1)*00(0+1)*
c) (0+1)*011
d) 0*1*2*
Answer
Answer: b [Reason:] The expression (0+1)*00(0+1)* is where either it initially takes 0 or 1 or 00 followed by string of combination of 0 and 1.
4. Which of the following is NOT the set of regular expression R = (ab + abb)* bbab
a) ababbbbab
b) abbbab
c) ababbabbbab
d) abababab
Answer
Answer: a [Reason:] ab followed by abb which is followed by bbab.
5. String generated by
S->aS/bA,
A->d/ccA
a) aabccd
b) adabcca
c) abcca
d) abababd
Answer
Answer: a [Reason:] S->aS (substitute S->aS)
S->aaS (substitute S->bA)
S->aabA (substitute A->ccA)
S->aabccA (substitute A->d)
S->aabccd.
6. Consider the production of the grammar S->AA A->aa A->bb Describe the language specified by the production grammar.
a) L = {aaaa,aabb,bbaa,bbbb}
b) L = {abab,abaa,aaab,baaa}
c) L = {aaab,baba,bbaa,bbbb}
d) L = {aaaa,abab,bbaa,aaab}
Answer
Answer: a [Reason:] S->AA (substitute A->aa)
S->aaaa
S->AA (substitute A->aa )
S->aaA (substitute A->bb)
S->aabb
S->AA (substitute A->bb the A->aa)
S->bbaa
S->AA (substitute A->bb)
S->bbbb.
7. If R is regular language and Q is any language (regular/ non regular), then Pref (Q in R) is _____________
a) Non-regular
b) Equal
c) Infinite
d) Regular
Answer
Answer: d [Reason:] So says the definition of Regular Grammar.
8. The production of the form no terminal → Λ is said to be null production.
a) False
b) True
Answer
Answer: b [Reason:] Here the non terminal that gives null will said to have a null production.
Set 4
1. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
a) 7
b) 10
c) 12
d) 11
Answer
Answer : d [Reason:] : String of length 0 = 1
string of length 1 = 4
string of length 2 = 3
string of length 3 = 3.
2. Which of the following is true?
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned
Answer
Answer : d [Reason:] : None.
3. A language is regular if and only if
a) Accepted by DFA
b) Accepted by PDA
c) Accepted by LBA
d) Accepted by Turing machine
Answer
Answer : a [Reason:] : All of above machine can accept regular language but all string accepted by machine is regular only for DFA.
4. Regular grammar is
a) Context free grammar
b) Non context free grammar
c) English grammar
d) None of the mentioned
Answer
Answer : a [Reason:] : Regular grammar is subset of context free grammar.
5. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
a) L1
c) L1 U L2 = .*
d) L1=L2
Answer
Answer : d [Reason:] : Finite state machine and regular expression have same power to express a language.
6. Which of the following is not a regular expression?
a) [(a+b)*-(aa+bb)]*
b) [(0+1)-(0b+a1)*(a+b)]*
c) (01+11+10)*
d) (1+2+0)*(1+2)*
Answer
Answer : b [Reason:] : Except b all are regular expression*.
7. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
Answer
Answer : a [Reason:] : According to Chomsky hierarchy .
8. Which of the following is true?
a) All subsets of a regular set are always regular
b) All finite subsets of non-regular set are always regular
c) Union of two non regular set of language is not regular
d) Infinite times union of finite set is always regular
Answer
Answer : b [Reason:] : None.
9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
Answer
Answer : d [Reason:] :If L is recursive enumerable and its complement too if and only if L is recursive.
10. Regular expressions are closed under
a) Union
b) Intersection
c) Kleene star
d) All of the mentioned
Answer
Answer : d [Reason:] : According to definition of regular expression.
Set 5
1. Consider the production of the grammar S->AA A->aa A->bb Describe the language specified by the production grammar.
a) L = {aaaa,aabb,bbaa,bbbb}
b) L = {abab,abaa,aaab,baaa}
c) L = {aaab,baba,bbaa,bbbb}
d) L = {aaaa,abab,bbaa,aaab}
Answer
Answer: a [Reason:] The production rules give aaaa or aabb or bbaa or bbbb.
2. Give a production grammar that specified language L = {ai b2i >= 1}
a) {S->aSbb,S->abb}
b) {S->aSb, S->b}
c) {S->aA,S->b,A->b}
d) None of the mentioned
Answer
Answer: a [Reason:] S->aSbb, S->abb give a^I a’s and b^2i b’s.
3. Let R1 and R2 be regular sets defined over alphabet ∑ then
a) R1 UNION R2 is regular
b) R1 INTERSECTION R2 is regular
c) ∑ INTERSECTION R2 IS NOT REGULAR
d) R2* IS NOT REGULAR
Answer
Answer: a [Reason:] Union of 2 regular languages is regular.
4. Which of the following String can be obtained by the language L = {ai b2i / i >=1}
a) aaabbbbbb
b) aabbb
c) abbabbba
d) aaaabbbabb
Answer
Answer: a [Reason:] Above production rule gives suppose if 3 a’s the corresponding b’s are 6 b’s.
5. Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.
a) {S->bS, S->b,S->aA, S->bA, A->aB, B->bB, B->aS, S->a}
b) {S->aS,S->bA,A->bB,B->bBa,B->bB}
c) {S->aaS,S->bbA,A->bB,B->ba}
d) None of the mentioned
Answer
Answer: a [Reason:] The above given condition is satisfied by
S->bS S->B
S->aA s->bA A->aB B->bB
B->aS S->a.
6. The production Grammar is {S->aSbb, S->abb} is
a) type-3 grammar
b) type-2 grammar
c) type-1 grammar
d) type-0 grammar
Answer
Answer: b [Reason:] Type 2 grammar satisfies this production grammar.
7. Regular expression (x/y)(x/y) denotes the set
a) {xy,xy}
b) {xx,xy,yx,yy}
c) {x,y}
d) {x,y,xy}
Answer
Answer: b [Reason:] The expression gives aa or xy or yx or yy.
8. Regular expression x/y denotes the set
a) {x,y}
b) {xy}
c) {x}
d) {y}
Answer
Answer: a [Reason:] x or y is given by the expression.
9. The regular expression denote a language comprising all possible strings of even length over the alphabet (0,1)
a) 1 + 0(1+0)*
b) (0+1)(1+0)*
c) (1+0)
d) (00+0111+10)*
Answer
Answer: d [Reason:] The condition is satisfied by 00 or 0111 or 10 or iterations of these.
10. The regular expressions denote zero or more instances of an x or y is
a) (x+y)
b) (x+y)*
c) (x* + y)
d) (xy)*
Answer
Answer: b [Reason:] It says that either its x or y or iterations of them.
Total Views: 16
