## CMI 2019

Question 1 |

Let L
he language L

_{1}={a^{n}b^{m}| m,n >=0 and m>=n} and L_{2}={a^{n}b^{m}| m,n >=0 and m_{1}U L

_{2}is:

Regular, but not context free | |

Context free, but not regular | |

Both regular and context free | |

Neither regular nor context free |

Question 1 Explanation:

Question 2 |

Let A be an NFA with n states. Which of the following is necessarily true?

The shortest word in L(A) has length at most n-1. | |

The shortest word in L(A) has length at least n. | |

The shortest word not in L(A) has length at most n-1. | |

The shortest word not in L(A) has length at least n. |

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?

D | |

H | |

I | |

M |

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?

5 ^{2} | |

2 ^{5} | |

2 ^{25} |

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 2

^{5}possible arrangements. Thus there are 2^{25}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 2^{25}
There are 4 questions to complete.