Multiple choice question for engineering
Set 1
1. The context free languages are closed under:
a) Intersection
b) Complement
c) Kleene
d) None of the mentioned
Answer
Answer: c [Reason:] Context free languages are closed under the following operation: union, kleene and concatenation. For regular languages, we can add intersection and complement to the list.
2. Given Grammar G1:
S->aSb
S->e
Grammar G2:
R->cRd
R->e
If L(G)=L(G1) U L(G2), the number of productions the new starting variable would have:
a) 2
b) 3
c) 4
d) 1
Answer
Answer: a [Reason:]
T->S|R
S->aSb
S->e
R->cRd
R->e
3. Context free languages are not closed under:
a) Intersection
b) Intersection with Regular Language
c) Complement
d) All of the mentioned
Answer
Answer: d [Reason:] It is a theorem which states that, Context free languages are not closed under operations like intersection and complement.
4. Which of the following is incorrect?
There exists algorithms to decide if:
a) String w is in CFL L
b) CFL L is empty
c) CFL L is infinite
d) All of the mentioned
Answer
Answer: d [Reason:] These properties are termed as decision properties of a CFL and include a set of problems like infiniteness problem, emptiness problem and membership problem.
5. If the start symbol is one of those symbols which produce no terminal through any sequence, the CFL is said to be
a) nullable
b) empty
c) eliminated
d) none of the mentioned
Answer
Answer: b [Reason:] In the process of removing useless symbols, if the starting symbol is also a part, the CFL can be then termed as empty; otherwise not.
6. Using the pumping constant n, If there is a string in the language of length between _____ and ____ then the language is infite else not.
a) n, 2n-1
b) 2n, n
c) n+1, 3n+6
d) 0, n+1
Answer
Answer: a [Reason:] If there is a string in the language of length between n and 2n-1 then the language is infite else not. The idea is essentially the same for regular languages.
7. Which of the following is/are CFL not closed under?
a) Reverse
b) Homomorphism
c) Inverse Homomorphism
d) All of the mentioned
Answer
Answer: d [Reason:] CFL is closed under union, kleene and concatenation along with the properties reversal,homomorphism and inverse homomorphism but not difference and intersection.
8. If L1 and L2 are context free languages, L1-L2 are context free:
a) always
b) sometimes
c) never
d) none of the mentioned
Answer
Answer: c [Reason:] Context free languages are not closed under difference, intersection and complement operations.
9. A___________ is context free grammar with atmost one non terminal in the right handside of the production.
a) linear grammar
b) linear bounded grammar
c) regular grammar
d) none of the mentioned
Answer
Answer: a [Reason:] A simple linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules
S → aSb
S → ε
10. There is a linear grammar that generates a context free grammar
a) always
b) never
c) sometimes
d) none of the mentioned
Answer
Answer: c [Reason:] Linear grammar is a subset of context free grammar which has atmost one non terminal symbol in the right hand side of the production.Thus, there exists some languages which are generated by Linear grammars.
Set 2
1. The following format of grammatical notation is accepted by which of the following:
AB->CD
A->BC or
A->B or
A->a
where A, B, C, D are non terminal symbols and a is a terminal symbol.
a) Greibach Normal Form
b) Chomsky Nrmal Form
c) Kuroda Normal Form
d) None of the mentioned
Answer
Answer: c [Reason:] Linearly Bounded grammar or Kuroda Normal Form allows the following format of grammatical analysis:
AB->CD
A->BC or
A->B or
A->a
2. Every Kuroda Normal form grammar generates ___________
a) Context free grammar
b) Context sensitive grammar
c) Unrestricted grammar
d) None of the mentioned
Answer
Answer: b [Reason:] Every context sensitive grammar which does not produce an empty string can be generated by a grammar in Kuroda Normal form.
3. Which of the following can generate Unrestricted grammars?
a) Pentonnen Normal form
b) Floyd Normal form
c) Greibach Normal form
d) None of the mentioned
Answer
Answer: a [Reason:] Pentonnen Normal form(for Unrestricted grammars) is a special case where there is a slight modification in the format of Kuroda Normal form.
AB->AD
A->BC
A->a
4. Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will halt at depth n.
a) top-down parser
b) bottom-up parser
c) multitape turing machine
d) none of the mentioned
Answer
Answer: a [Reason:] Given a grammar in GNF and a derivable string in the grammar with the length n, any top-down parser will halt at depth n. As the parameter ‘depth’ is mentioned, we will use a top-down parser. Example-LL parser.
5. Which of the following grammars is similar to Floyd Normal form?
a) Backus Naur Form
b) Kuroda Normal Form
c) Greibach Normal Form
d) Chomsky Normal Form
Answer
Answer: a [Reason:] Donald Knuth implied a BNF” syntax in which all definitions have such a form may be said to be in ”Floyd Normal Form”.
A->B|C
A->BC
A->a
6. Which among the following can parse a context free grammar?
a) top down parser
b) bottom up parser
c) CYK algorithm
d) all of the mentioned
Answer
Answer: d [Reason:] We use certain algorithms to parse a context free grammar which include the most popular CYK algorithm which employs the concept of bottom up parsing and dynamic parsing.
7. The standard version of CYK algorithm operates only on context free grammars in the following form:
a) Greibach Normal form
b) Chomsky Normal form
c) Backus Naur form
d) All of the mentioned
Answer
Answer: b [Reason:] It requires the presence of a context free grammar into Chomsky Normal form to operate. However, every context free grammar can be converted into CNF for keeping the sense of grammar equivalent.
8. The __________ running time of CYK is O(n3 .|G|)
where n is the length of the parse string and |G| is the size of the context free grammar G.
a) worst
b) best
c) average
d) none of the mentioned
Answer
Answer: a [Reason:] This is the worst case running time of CYK and and this makes it one of the most efficient algorithms for recognizing general context free languages in practice.
9. Which of the following is true for Valiants algorithm?
a) an extension of CYK
b) deals with efficient multiplication algorithms
c) matrices with 0-1 entries
d) all of the mentioned
Answer
Answer: d [Reason:] Valiants algorithm is actually an extention of CYK which even computes the same parsing table yet he showed another method can be utilized fro performing this operation.
10. Which among the following is a correct option in format for representing symbol and expression in Backus normal form?
a) <symbol> ->expression
b) <symbol>::=_expression_
c) <symbol>=<expression>
d) all of the mentioned
Answer
Answer: b [Reason:] <symbol>::=_expression_ is the correct representation where <symbol> is a non terminal, and expression consist of one or more sequence of symbols, more sequence are separated by |, indicating a choice.
Set 3
1. The format: A->aB refers to which of the following?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) None of the mentioned
Answer
Answer: b [Reason:] A context free grammar is in Greibach Normal Form if the right hand sides of all the production rules start with a terminal, optionally followed by some variables.
2. Which of the following does not have left recursions?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) All of the mentioned
Answer
Answer: b [Reason:] The normal form is of the format:
A->aB where the right hand side production tends to begin with a terminal symbo, thus having no left recursions.
3. Every grammar in Chomsky Normal Form is:
a) regular
b) context sensitive
c) context free
d) all of the mentioned
Answer
Answer: c [Reason:] Conversely, every context frr grammar can be converted into Chomsky Normal form and to other forms.
4. Which of the production rule can be accepted by Chomsky grammar?
a) A->BC
b) A->a
c) S->e
d) All of the mentioned
Answer
Answer: d [Reason:] in CNF, the production rules are of the form:
A->BC
A-> a
S->e
5. Given grammar G:
(1)S->AS
(2)S->AAS
(3)A->SA
(4)A->aa
Which of the following productions denies the format of Chomsky Normal Form?
a) 2,4
b) 1,3
c) 1, 2, 3, 4
d) 2, 3, 4
Answer
Answer: a [Reason:] The correct format: A->BC, A->a, X->e.
6. Which of the following grammars are in Chomsky Normal Form:
a) S->AB|BC|CD, A->0, B->1, C->2, D->3
b) S->AB, S->BCA|0|1|2|3
c) S->ABa, A->aab, B->Ac
d) All of the mentioned
Answer
Answer: a [Reason:] We can eliminate the options on the basis of the format we are aware of: A->BC, B->b and so on.
7. With reference to the process of conversion of a context free grammar to CNF, the number of variables to be introduced for the terminals are:
S->ABa
A->aab
B->Ac
a) 3
b) 4
c) 2
d) 5
Answer
Answer: a [Reason:] According to the number of terminals present in the grammar, we need the corresponding that number of terminal variables while conversion.
8. In which of the following, does the CNF conversion find its use?
a) CYK Algorithm
b) Bottom up parsing
c) Preprocessing step in some algorithms
d) All of the mentioned
Answer
Answer: d [Reason:] Besides the theoretical significance of CNF, it conversion scheme is helpful in algorithms as a preprocessing step, CYK algorithms and the bottom up parsing of context free grammars.
9. Let G be a grammar. When the production in G satisfy certain restrictions, then G is said to be in ___________.
a) restricted form
b) parsed form
c) normal form
d) all of the mentioned
Answer
Answer: c [Reason:] When the production in G satisfy certain restrictions, then G is said to be in ‘normal form’.
10. Let G be a grammar: S->AB|e, A->a, B->b
Is the given grammar in CNF?
a) Yes
b) No
Answer
Answer: a [Reason:] e is allowed in CNF only if the starting variable does not occur on the right hand side of the derivation.
Set 4
1. Which among the following is smallest for n=50
a) 2n2
b) n2+3n+7
c) n3
d) 2n
Answer
Answer: b [Reason:]
2n2=5000
n2+3n+7=2567
n3=125000
2n=1.13*1015
2. The space complexity of a turing machine is undefined if:
a) It is a multitape turing machine
b) If no string of length n causes T to use infinite number of tape squares
c) If some input of length n causes T to loop forever
d) None of the mentioned
Answer
Answer: c [Reason:] If there exists an input string of length n that causes T to use an infinite number of tape squares, the space complexity of the turing machine is undefined.
3. In order to reduce the run time of a turing machine:
a) we can reduce the number of tapes
b) we can increase the number of tapes
c) use infinite tapes
d) none of the mentioned
Answer
Answer: One way to reduce the run time can be to increase the number of tapes. Sometimes, using two tapes can be used to avoid back and forth motions altogether.
4. Which of the following are basic complexity classes for a function f:N->N?
a) Ntime(f)
b) Nspace(f)
c) Space(f)
d) All of the mentioned
Answer
Answer: d [Reason:] Ntime(f): is a set of languages that can be accepted by a NTM T with non deterministic time complexity function t <=f. In all four cases, the machines are allowed to be multitape TM’s.
5. A function f is called __________ if there exists a TM T so that for any n and any input string of length n, T halts in exactly f(n) moves.
a) Step function
b) Step counting function
c) Inplace functions
d) None of the mentioned
Answer
Answer: b [Reason:] If f is a step counting function, T is a TM halting in f(n) moves where n is the length of input string.
6. Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)
a) O(nf)
b) O(n+f)
c) O(n2f2)
d) None of the mentioned
Answer
Answer: c [Reason:] Using the encoding function, it is possible to show that if the function f is a step counting function, then the function Cn2(f(n))2 is the total number of moves required.
7. Which among the following is false?
If f=O(h) and g=O(k) for f,g,h,k:N->N, then
a) f+g = O(h+k)
b) fg = O(hk)
c) fg=O(hk)
d) None of the mentioned
Answer
Answer: c [Reason:] f,g,h,k are partial functions and each is defined at all but a finite number of points.
8. Which of the following is not correct for ZPP?
a) zero error probabalistic polynomial time
b) it runs in non-polynomial time
c) it returns an answer yes, no or do not know
d) none of the mentioned
Answer
Answer: b [Reason:] ZPP is zero error probabalistic polynomial time complexity class which run in polynomial time, returns an answer: yes, no or do not know.
9. ZPP is based on ________
a) Probabalistic turing machine
b) Alternative turing machine
c) Quantum turing machine
d) None of the mentioned
Answer
Answer: a [Reason:] A probabalistic turing machine is a non deterministic turing machine which randomly chooses between the available transitions at each point according to some probability distribution.
10. ZPP is exactly equal to the ____________of the classes RP and co-RP.
a) Union
b) Intersection
c) Concatenation
d) Difference
Answer
Answer: b [Reason:] To prove the following statement, we need to take in note that every problem in RP and co-RP has a Las-Vegas algorithm.
11. Suppose we have a las vegas algorithm C to prove ZPP is contained in RP and co-RP. Run C for double its expected running time.
By Markov’s inequality, the chance that it will answer before we stop is:
a) 1/2
b) 1/4
c) 1/3
d) none of the mentioned
Answer
Answer: a [Reason:] This means the chance we’ll give the wrong answer on a YES instance, by stopping and yielding NO, is only 1/2, fitting the definition of an RP algorithm.
12. State true or false:
Statement: ZPP is closed under complement function.
a) true
b) false
Answer
Answer: a [Reason:] ZPP is said to be closed under complement function i.e. ZPP=co-ZPP.
Set 5
1. The most suitable data structure used to represent the derivations in compiler:
a) Queue
b) Linked List
c) Tree
d) Hash Tables
Answer
Answer: c [Reason:] The tree, known as “Parse tree” when used in a compiler, is the data structure of choice to represent the source program.
2. Which of the following statement is false in context of tree terminology?
a) Root with no children is called a leaf
b) A node can have three children
c) Root has no parent
d) Trees are collection of nodes, with a parent child relationship
Answer
Answer: a [Reason:] A node has atmost one parent, drawn above the node, and zero or more children drawn below. Lines connect parents to children. There is one node, one root, that has no parent; this node appears to be at the top of the tree. Nodes with no children are called leaves. Nodes that are not leaves are called interior nodes.
3. In which order are the children of any node ordered?
a) From the left
b) From the right
c) Arbitrarily
d) None of the mentioned
Answer
Answer: a [Reason:] The children of a node are ordered from the left and drawn so. If N is to the left of node M, then all the descendents of N are considered to be to the left of all the descendents of M.
4. Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S
Answer
Answer: d [Reason:] The root is labelled by the start symbol. All the leaves are either labelled by a a terminal or with e.
5. For the expression E*(E) where * and brackets are the operation, number of nodes in the respective parse tree are:
a) 6
b) 7
c) 5
d) 2
Answer
Answer: b [Reason:] 
6. The number of leaves in a parse tree with expression E*(E) where * and () are operators
a) 5
b) 2
c) 4
d) 3
Answer
Answer: a [Reason:]
7. Which of the following does the given parse tree correspond to?
a) P->1100
b) P->0110
c) P->1100ε
d) P->0101
Answer
Answer: b [Reason:] The following is a parse tree for the production 0110 over {0,1}*.
8. A grammar with more than one parse tree is called:
a) Unambiguous
b) Ambiguous
c) Regular
d) None of the mentioned
Answer
Answer: b [Reason:] A context free grammar G is ambiguous if there is at least one string in L(G) having two or more distinct derivation trees or equivalently, two or more distinct leftmost derivations.
9. __________ is the acyclic graphical representation of a grammar.
a) Binary tree
b) Oct tree
c) Parse tree
d) None of the mentioned
Answer
Answer: c [Reason:] In order to graphically represent a derivation of a grammar we need to use parse trees.
10. Grammar is checked by which component of compiler
a) Scanner
b) Parser
c) Semantic Analyzer
d) None of the mentioned
Answer
Answer: Parser or syntax analyzer is the one responsible for checking the grammar and reporting errors. In this phase, parse tree is generated and syntax is analyzed.
Total Views: 23
