InterviewSolution
Saved Bookmarks
InterviewSolution
This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.
| 51. |
A Push Down Automata is if there is at most one transition applicable to each configuration?(a) Deterministic(b) Non deterministic(c) Finite(d) Non finite |
|
Answer» Right answer is (a) Deterministic The explanation: In every situation, only one transition is available as continuation then the result is deterministic push down automata. |
|
| 52. |
A regular language corresponds to __________(a) An alphabet(b) Set of strings over an alphabet(c) A DFA only(d) A DFA or an NFA |
|
Answer» Right answer is (b) Set of strings over an alphabet To explain: A regular grammar takes in all strings over an alphabet. |
|
| 53. |
All __________ are automatically treated as regular expressions.(a) Programmatic description(b) Window(c) Win Object(d) Collection |
|
Answer» Correct option is (a) Programmatic description Easy explanation: It is seen that programmatic description are treated as regular expression. |
|
| 54. |
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» The correct choice is (b) [(0+1)-(0b+a1)*(a+b)]* Best explanation: Except [(0+1)-(0b+a1)*(a+b)]* all are regular expression. |
|
| 55. |
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» The correct answer is (a) Accepted by DFA To explain: All of above machine can accept regular language but all string accepted by machine is regular only for DFA. |
|
| 56. |
The regular expression denotes 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» The correct answer is (d) (00+0111+10)* To elaborate: Option 1 + 0(1+0)* → It does not consider even length criteria for the question. Option (0+1) (1+0)* → 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 (1+0) → It gives either 1 or 0. Hence Option (00+0111+10)* is the answer. |
|
| 57. |
The regular languages are not closed under ___________(a) Concatenation(b) Union(c) Kleene star(d) Complement |
|
Answer» Correct choice is (d) Complement Easiest explanation: Explanation: RE are closed under Union (cf. picture) Intersection Concatenation Negation Kleene closure. |
|
| 58. |
The regular expression denote a language comprising all possible strings of even length over the alphabet (0,1) is?(a) 1 + 0(1+0)*(b) (0+1)(1+0)*(c) (1+0)(d) (00+0111+10)* |
|
Answer» Correct choice is (d) (00+0111+10)* The best I can explain: The condition is satisfied by 00 or 0111 or 10 or iterations of these. |
|
| 59. |
Choose the correct statement.(a) CFG is not LR(b) Ambiguous Grammar can never be LR(c) CFG is not LR & Ambiguous Grammar can never be LR(d) None of the mentioned |
|
Answer» The correct answer is (c) CFG is not LR & Ambiguous Grammar can never be LR Easy explanation: Mentioned reason is true. |
|
| 60. |
What is the function of the syntax phase?(a) recognize the language and to cal the appropriate action routines that will generate the intermediate form or matrix for these constructs(b) Build a literal table and an identifier table(c) Build a uniform symbol table(d) Parse the source program into the basic elements or tokens of the language |
|
Answer» Correct answer is (a) recognize the language and to cal the appropriate action routines that will generate the intermediate form or matrix for these constructs Easiest explanation: In this phase symbol table is created by the compiler which contains the list of lexemes or tokens. |
|
| 61. |
Find the wrong statement?(a) The language accepted by finite automata are the languages denoted by regular expression(b) Every DFA has a regular expression denoting its language(c) For a regular expression r, there does not exists NDFA with L® ant transit that accept(d) None of the mentioned |
|
Answer» Correct option is (c) For a regular expression r, there does not exists NDFA with L® ant transit that accept To explain I would say: The vice versa is true. |
|
| 62. |
Which of the following statement is true?(a) Every language that is defined by regular expression can also be defined by finite automata(b) Every language defined by finite automata can also be defined by regular expression(c) We can convert regular expressions into finite automata(d) All of the mentioned |
|
Answer» Right option is (d) All of the mentioned For explanation I would say: All these statements are true w.r.t regular expression. |
|
| 63. |
Conversion of a DFA to an NFA __________(a) Is impossible(b) Requires the subset construction(c) Is Chancy(d) Is nondeterministic |
|
Answer» The correct option is (b) Requires the subset construction To explain I would say: In order to convert NDFA to DFA we work with sets of state where each state in the DFA corresponds to a set of NFA states. |
|
| 64. |
Assume statements S1 and S2 defined as: S1: L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turing machines is countable. Which of the following is true?(a) S1 is correct and S2 is not correct(b) Both S1 and S2 are correct(c) Both S1 and S2 are not correct(d) S1 is not correct and S2 is correct |
|
Answer» Right choice is (b) Both S1 and S2 are correct For explanation: The assumptions of statement S1 and S2 are correct. |
|
| 65. |
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 resolute |
|
Answer» Correct option is (c) Relocation To explain: 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. |
|
| 66. |
By whom is the symbol table created?(a) Compiler(b) Interpreter(c) Assembler(d) None of the mentioned |
|
Answer» Correct answer is (a) Compiler The explanation is: Symbol table is created by the compiler which contains the list of lexemes or tokens. |
|
| 67. |
What is another name for Lexical Analyser?(a) Linear Phase(b) Linear Analysis(c) Scanning(d) All of the mentioned |
|
Answer» Correct option is (d) All of the mentioned To elaborate: Lexical Analyzer is also called “Linear Phase” or “Linear Analysis” or “Scanning“. |
|
| 68. |
Regular expression is __________(a) Type 0 language(b) Type 1 language(c) Type 2 language(d) Type 3 language |
|
Answer» The correct answer is (a) Type 0 language Explanation: According to the Chomsky hierarchy. |
|
| 69. |
The grammar S → aSa | bS | c is?(a) LL(1) but not LR(1)(b) LR(1) but not LR(1)(c) Both LL(1) but not LR(1) & LR(1) but not LR(1)(d) None of the mentioned |
|
Answer» Correct option is (c) Both LL(1) but not LR(1) & LR(1) but not LR(1) Explanation: First(aSa) = a First(bS) = b First(c) = c LR parsers are more powerful than LL (1) parsers and LR (1). |
|
| 70. |
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» Right option is (a) R1 UNION R2 is regular The explanation is: Union of 2 regular languages is regular. |
|
| 71. |
Automaton accepting the regular expression of any number of a’ s is ___________(a) a*(b) ab*(c) (a/b)*(d) a*b*c |
|
Answer» Correct choice is (a) a* The explanation is: It gives any number of a’s. |
|
| 72. |
The set of all strings over ∑ = {a,b} in which strings consisting a’s and b’s and ending with in bb is?(a) ab(b) a*bbb(c) (a+b)* bb(d) All of the mentioned |
|
Answer» Correct choice is (c) (a+b)* bb For explanation: Only this expression ends with bb only. |
|
| 73. |
Given the following statements: (i) Recursive enumerable sets are closed under complementation. (ii) Recursive sets are closed under complements. Which is/are the correct statements?(a) I only(b) II only(c) Both I and II(d) Neither I nor II |
|
Answer» Correct answer is (b) II only The explanation is: Recursive languages are closed under the following operations. The Kleene star L * of L The concatenation L * o P of L and P The union L U P The intersection L ∩ P. |
|
| 74. |
Which behaviour of a NFA can be stimulated by DFA?(a) Always(b) Sometimes(c) Never(d) Depends on NFA |
|
Answer» Correct choice is (a) Always For explanation: It can be done through power set construction. |
|
| 75. |
Which of the following statement is correct?(a) A Context free language can be accepted by a deterministic PDA(b) union of 2 CFLs is context free(c) The intersection of two CFLs is context free(d) The complement of CFLs is context free |
|
Answer» Correct option is (b) union of 2 CFLs is context free For explanation: Context-free languages are closed under the following operations. The Kleene star, the concatenation, the union and the intersection. |
|
| 76. |
The context free grammar is ambiguous if ______________(a) The grammar contains non-terminals(b) Produces more than one parse tree(c) Production has two non-terminals side by side(d) None of the mentioned |
|
Answer» The correct choice is (b) Produces more than one parse tree The explanation: Since more than one parse tree is generated hence one than option is available .Therefore it’s ambiguous. |
|
| 77. |
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» Right option is (a) Leftmost derivation The best explanation: In top down parser takes input from Left to right constructing leftmost derivation of the sentence. |
|
| 78. |
Pee Hole optimization __________(a) Loop Optimization(b) Local Optimization(c) Constant folding(d) Data Flow analysis |
|
Answer» Right option is (c) Constant folding Easy explanation: More loops are added. |
|
| 79. |
If string s is accepted by this DFA, which of these strings cannot be suffix of s?(a) 111001(b) 111111(c) 111000(d) 101010 |
|
Answer» The correct answer is (a) 111001 For explanation I would say: 111001 cannot be the suffix of any string accepted by this DFA. Suppose s=w111001. No matter what state the DFA reaches after reading w, it will go to state D after reading “111”, then go to state B after reading “00” and finally reaches state C after reading “1”. |
|
| 80. |
Find the pair of regular expressions that are equivalent.(a) (0+1)* and (0*+1*)*(b) (0+1)* and (0+1*)*(c) (0+10)* and (0*+10)*(d) All of the mentioned |
|
Answer» Right option is (d) All of the mentioned Easy explanation: All generate all strings of 0’s and 1’s thus are these pairs are equivalent. |
|
| 81. |
The set of all strings over ∑ ={a,b} in which a single a is followed by any number of b’s a single b followed by any number of a’s is?(a) ab* + ba*(b) ab*ba*(c) a*b + b*a(d) None of the mentioned |
|
Answer» Right option is (a) ab* + ba* Easiest explanation: ab*+ba* is the expression in which a single a is followed by any number of b’s a single b followed by any number of a’s. |
|
| 82. |
Recursively enumerable languages are not closed under ______________(a) Union(b) Intersection(c) Complementation(d) Concatenation |
|
Answer» Right choice is (c) Complementation To explain: Recursive languages are closed under the following operations. The Kleene star L * of L the concatenation L * o P of L and P the union L U P the intersection L ∩ P. |
|
| 83. |
What can be said about a regular language L over {a} whose minimal finite state automaton has two states?(a) L must be {an| n is odd}(b) L must be {an| n is even}(c) L must be {an| n is even}(d) Either L must be {an | n is odd}, or L must be {an | n is even} |
|
Answer» Correct option is (d) Either L must be {an | n is odd}, or L must be {an | n is even} Easy explanation: There are two states. When first state is final, it accepts even no. of a’s. When second state is final, it accepts odd no. of a’s. |
|
| 84. |
The grammar G: S → SS | a | b is ambiguous. Check all and only the strings that have exactly two leftmost derivations in G.(a) bbb(b) ab(c) All of the mentioned(d) None of the mentioned |
|
Answer» Correct choice is (c) All of the mentioned To elaborate: S => a. A string of length 2 has only one derivation, e.g., S => SS => aS => ab. |
|
| 85. |
What is the similarity between LR, LALR and SLR?(a) Use same algorithm, but different parsing table(b) Same parsing table, but different algorithm(c) Their Parsing tables and algorithm are similar but uses top down approach(d) Both Parsing tables and algorithm are different |
|
Answer» Right choice is (a) Use same algorithm, but different parsing table To explain I would say: The common grounds of these 3 parser is the algorithm but parsing table is different. |
|
| 86. |
W hat is the complement of the language accepted by the NFA shown below?(a) A,B(b) B(c) C(d) D,C |
|
Answer» The correct option is (b) B The explanation is: The given alphabet contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’. |
|
| 87. |
AB+(A+B)’ is equivalent to __________(a) A?B(b) A+B(c) (A+B)A(d) (A+B)B |
|
Answer» Right choice is (a) A?B The best explanation: It is equivalent to A? B. |
|
| 88. |
The language accepted by this DFA is?(a) b*ab*ab*ab*(b) (a+b)*(c) b*a(a+b)*(d) b*ab*ab* |
|
Answer» Correct answer is (c) b*a(a+b)* Best explanation: Initially circle s around b so b* then a then followed by (a+b)*. |
|
| 89. |
If P & R are regular and also given that if PQ=R, then?(a) Q has to be regular(b) Q cannot be regular(c) Q need not be regular(d) Q has to be a CFL |
|
Answer» The correct choice is (c) Q need not be regular Easiest explanation: If two regular languages when combined do not always produce a regular language. |
|
| 90. |
How many minimum states are required to find whether a string has odd number of 0’s or not?(a) 1(b) 2(c) 3(d) 4 |
|
Answer» Right answer is (b) 2 Easy explanation: 2 minimum states are required to find whether a string has odd number of 0’s or not. |
|
| 91. |
L1 is accepted by the NFA, obtained by changing the accepting state of M to a non-accepting state and vice versa. Which of the following statements is true?(a) L1 = {0, 1}* – L(b) L1 = {0, 1}* – L(c) L1 ⊆ L(d) L1=L |
|
Answer» Correct answer is (b) L1 = {0, 1}* – L For explanation I would say: Either it takes 0 or 1 or iterations of it or none.compilers-questions-answers-Obtaining the regular Expression from the Finite autom |
|
| 92. |
Which of the following statement is true for Moore Machine?(a) Output depends on present state(b) Output depends on present input(c) Output depends on present state and present input(d) Output depends on present state and past input |
|
Answer» Correct choice is (a) Output depends on present state The best I can explain: The definition states that moore machines output is determined by the current state only. |
|
| 93. |
The number of states in DFA that accepts the language L(M) ∩ L(N) is _________(a) 0(b) 1(c) 2(d) 3 |
|
Answer» Correct choice is (b) 1 Easiest explanation: In DFA M: all strings must end with ‘a’. In DFA N: all strings must end with ‘b’. So the intersection is empty. For an empty language, only one state is needed. |
|
| 94. |
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least?(a) N^2(b) 2^N(c) 2N(d) N! |
|
Answer» Correct option is (c) 2N For explanation I would say: If the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs. |
|
| 95. |
Which is the application of NFA?(a) A regular language is produced by union of two regular languages(b) The concatenation of two regular languages is regular(c) The Kleene closure of a regular language is regular(d) All of the mentioned |
|
Answer» Right answer is (d) All of the mentioned Easiest explanation: As per its definition. |
|
| 96. |
Which of the following is incorrect for the actions of A LR-Parser I) shift s ii) reduce A->ß iii) Accept iv) reject?(a) Only I)(b) I) and ii)(c) I), ii) and iii)(d) I), ii) , iii) and iv) |
|
Answer» Right choice is (c) I), ii) and iii) Explanation: Only reject out of the following is a correct LR parser action. |
|
| 97. |
Which one of the following is TRUE?(a) The language L={a^n b^n |n>0 } is regular(b) The language L={a^n |n is prime } is regular(c) The language L={w|w has 3k+1 b’s for some k } is regular(d) None of the mentioned |
|
Answer» Correct choice is (c) The language L={w|w has 3k+1 b’s for some k } is regular The explanation is: Only for this option we can build a FA. |
|
| 98. |
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» Correct option is (b) All finite subsets of non-regular set are always regular To elaborate: None. |
|
| 99. |
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» Correct option is (d) All of the mentioned Easy explanation: None. |
|
| 100. |
Which of the following conversion is not possible (algorithmically)?(a) Regular grammar to CFG(b) NDFA to DFA(c) NDPDA to DPDA(d) NDTM to DTM |
|
Answer» Right choice is (c) NDPDA to DPDA The explanation is: Not every NDPDA has an equivalent deterministic PDA. |
|