UGC (Computer science)net based solved multiple questions
Compiler
1. If language L={0,1}*,then reversed language L^R
Ans. {0,1}*
2. Recursive descent Parsers are a type of
Ans. LL parsers
3. If L1 be the class of languages accepted by finite state machines and L2 be the class of languages represented by regular expressions then,
Ans. L1=L2
4. Which of the following is a type of Top -down parsing?
Ans. Predictive parsing
5. Yacc is a
Ans. Parser generator
6. Which among the following is true of LL(1) grammar?
Ans. Not ambiguous
7. A grammar with the property that no production right side has 2 adjacent non-terminals is called
Ans. Operator grammar
8. If r and s are regular expressions denoting languages L(r) and L(s),then (r)/(s)is a regular expression denoting
Ans. L(r) U L(s)
9. The automation accepting the regular expression of any number of a's is
Ans. a*
10. Which among the following is false
a. No LR(1) grammar is ambiguous.
b. Every LL(1) grammar is an LR(1)grammar.
c. The regular expressions (a/b)* and (a*/b*)* are equivalent
d. Not all grammars can be converted to an equivalent operator grammar.
Ans. D
11. Which among the following is an NP - Complete problem?
3SAT Problem +Travelling Salesman +Graph 3 coloring
12. The solution to the count-to infinity problem in which a router never advertises the cost of a destination to its neighbour N, if N is the next hop to that destination, is called
Ans. Split- horizon
13. A complier which runs on one machine and produces target code for another is called a
Ans. Cross compiler
14. Which among the following types of languages are accepted both by Finite and Pushdown automata?
Ans. Regular
15. Consider the following two languages over {a,b}
L1 - The set of strings beginning and ending with an a
L2 - the set of strings with the same number of a's and b$
which of the following is true about L1 and L2?
Ans. L1 is regular and L2 is context free but not regular.
16. Classify into one of the alternatives the grammar denoted by the productions
S---->aB, S---->bA, A--->a, A--->aS ,A--->bAA ,B--->b , B---->nS ,B---->aBB, AB---->BA
Ans. Context sensitive grammar
17. Context sensitive grammar can be recognized by a
Ans. Linearly bounded memory machine
18. YACC is a program in UNIX used for
Ans. Automatic parser generation
19. A parsing algorithm used in top down parsing is
Ans. LL
20. DAG used in a complier for
Ans. Parsing
21. Which of the following is true about a cross compiler?
It is written in the machine code of one processor and produces code for another processor
22. Which of the following phases of a compiler is not in the backend?
a. Syntax analysis
b. Intermediate code generation
c. Code generation
d. Code optimization
Ans. a
23. For a given grammar, which of among following parsing tables are likely to have the most number of states?
a. SLR b. LALR c.LR(0) d. LR(1)
Ans. LR(1)
24. Which among the following is not used for intermediate code generation?
Ans. Parse trees
25. Which of the following identifiers used in LEX contains the sequence of characters forming a token?
a. yylval b. yyerror c. yytext d. yystack
Ans. c
26. Which of the following operations is context free languages not closed under
Ans. Intersection
27. Consider the following grammar
S---->(S) S ---->x
Which of the following statements is (are)true?
i. The grammar is ambiguous
ii. The grammar is suitable for top- down parsing
iii. The grammar is suitable for bottom - up parsing
Ans. iii
28. Which of the following are not regular?
a. Strings of even number of a's
b. Strings of a's whose length is a prime number.
c. Set of all palindromes made up of a's and b's.
d. Strings of a's whose length is a perfect square.
Ans. b,c and d
29. Consider the language L1=null set and L2={1} which one of the following represents L1*UL2*L1*
Ans. 1*
30. Given the following two languages
L1={a^nb^n|n>=0,n#100}
L2= {w subset {a,b,c}*|na(w)=nb(w)=nc(w)}
which of the following options is correct?
Ans. Both L1 and L2 are context free language.
31. Let G =(V,T,S,P)be a context -free grammar such that every one of its productions is of the form A---->v, with |v|=K>1.The derivation tree for any W subset L(g)has a height such that
Ans. logk|W|<=h<=Klogk|W|
32. Consider the following statements related to compiler construction
a. Lexical analysis is specified by context free grammars and implemented by pushdown automata
b. Syntax analysis is specified by regular expressions and implemented by finite- state machine.
Ans. Neither a or b
33. 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 ---------
Ans. Relocation
34. Which of the following derivations does a top-down parser use while parsing an input string? The input string is scanned from left to right.
Ans. left most derivation
35. Given the following statements
S1. If L is a regular language then the language {uv|u belongs to L,v belongs to L^R}is also regular.
S2. L={ww^R}is regular language
Ans. S1 is correct and S2 is not correct
36. The context free grammar for the language
L={a^nb^m|n<=m+3,n>=0,m>=0} is
Ans. S--->aaaA|aaA|aA|lamda, A--->aAb|B, B--->Bb|lamda
37. Given the following statements
S1.- SLR uses follow information to guide reductions. In case of LR and LALR parsers, the look -aheads are associated with the items and they make use of the left context available to the parser.
S2. - LR grammar is a larger sub class of context free grammar as compared to that SLR and LALR grammars.
Ans. both S1 and S2 are correct
38. The context free grammar given by
S---->XYX
X--->aX|bX|lamda
Y--->bbb
generates the language which is defined by regular expression:
(a+b)*(bbb)(a+b)*
39. Given the following two languages
L1 = {a^n b a^n| n>0}
L2 ={a^n b a^n b^n+1|n>0}
Which of the following is correct?
Ans. L1 is context free grammar and L2 is not context free grammar
40. There are exactly --------- different finite automata with three states x, y and z over the alphabet {a,b}where x is always the start state.
Ans. 5832
41. Which of the following regular expressions, each describing a lanugage of binary numbers that represents non-negative decimal values, does not include even values?
a. 0*1+0*1* b. 0*1*+1* c. 0*1*0*1+ d. 0+1*0*1*
where {+,*}are quantification characters.
Ans. c
42. Which of the following statements is/are TRUE?
a. The grammar S-->SS |a is ambiguous.(Where S is the start symbol)
b. The grammar S--->0S1|01S|absilon is ambiguous.
c. The grammar
S---->T/U
T--->xSy|xy|absilon
U--->yT
generates a language consisting of the string yxxyy
Ans.
43. Which of the following statement is false? (question paper Jan 2018)
Ans. The families of recursively enumerable and recursive languages are closed under reversal
44. Which of the following pairs have different expressive power?
Ans. Single -tape-turing machine and multi-dimensional turing machine.
45. Given the following two statements
1. L={w|na(w)=nb(w)}is deterministic context free language but not linear.
2. L={a^nb^n}U{a^nb^2n}is linear, but not deterministic context free language.
Ans. 1 is true,2 is not true
46. Consider the following statements related to compiler construction
a. Lexical analysis is specified by context free grammars and implemented by pushdown automata.
b. Syntax Analysis is specified by regular expression and implemented by finite-state machine.
Which of the statement(s) is/are correct?
Ans. neither a nor b
