## CMI 2019

 Question 1
Let L1={anbm | m,n >=0 and m>=n} and L2={anbm | m,n >=0 and m he language L1 U L2 is:
 A Regular, but not context free B Context free, but not regular C Both regular and context free D Neither regular nor context free
Theory-of-Computation       Context-Free-Language
Question 1 Explanation: Question 2
Let A be an NFA with n states. Which of the following is necessarily true?
 A The shortest word in L(A) has length at most n-1. B The shortest word in L(A) has length at least n. C The shortest word not in L(A) has length at most n-1. D The shortest word not in L(A) has length at least n.
Theory-of-Computation       NFA
Question 2 Explanation:
Assume that L(A) is non-empty. If A accepts a word of length >= n, there is an accepting run of A that has at least one loop. If we cut out all the loops in this run, we get an accepting run (on some other word) that visits each of the n states at most once, and hence there are at most n-1 transitions, meaning there is a word in L(A) of length at most n-1. Thus the shortest word in L(A) has length at most n-1.
 Question 3
Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, in terms of value, of the root node A? A D B H C I D M
Engineering-Mathematics       Graph-Theory
Question 3 Explanation:
The predecessor of A is the rightmost node in the left subtree of A.
 Question 4
There are five buckets, each of which can be open or closed. An arrangement is a specification of which buckets are open and which are closed. Every person likes some of the arrangements and dislikes the rest. You host a party, and amazingly, no two people on the guest list have the same likes and dislikes. What is the maximum number of guests possible?
 A 52 B C 25 D 225
Aptitude       Numerical
Question 4 Explanation:
Let us say a person's profile is a function from the set of all arrangements to {0,1} (indicating whether a particular arrangement is liked by that person or not). There are 25 possible arrangements. Thus there are 225 possible profiles. Two people with the same profile have the same likes and dislikes, and thus, no two guests have the same profile. Thus the maximum number of guests possible is 225
There are 4 questions to complete.

Register Now