CMI 2020

Question 1
Which of the following languages over the alphabet {0, 1} are not recognized by de-terministic finite state automata (DFA) with three states?
Words which do not have 11 as a contiguous subword
Binary representations of multiples of three
Words that have 11 as a suffix
Words that do not contain 101 as a contiguous subword
Question 1 Explanation: 
Question 2
Consider the following regular expressions over alphabet {a, b}, where the notation (a + b)+ means (a + b)(a + b)* :
r1 = (a + b)+ a (a + b)*
r2 = (a + b)*b (a + b)+
Let L1 and L2 be the languages defined by r1 and r2, respectively. Which of the following regular expressions define L1 ∩ L2?
(a + b)+ a (a + b)*b (a + b)+
(a + b)* a b (a + b)*
(a + b)*b (a + b)* a (a + b)*
(a + b)* a (a + b)*b (a + b)*
Question 2 Explanation: 
L1 is the set of all words of length n ≥ 2 containing an a at one of the positions 2, · · · , n. L2 is the set of all words of length n ≥ 2 containing a b in one of the positions 1, · · · , n − 1. The intersection L1 ∩ L2 is the set of all words containing a b at one of the positions 1, . . . , n − 1 and an a at one of the positions 2, . . . , n. This is given by the expression in (c).
Option (a) is incorrect since it accepts only words of length at least 4.
Option (b) is incorrect since it accepts ab, which is not in L1 ∩ L2.
Option (d) is incorrect once again as it accepts ab.
Question 3
Some children are given boxes containing sweets. Harish is happy if he gets either gems or toffees. Rekha is happy if she gets both bubble gums and peppermints. Some of the boxes are special, which means that if the box contains either gems or toffees, then it also contains bubble gums and peppermints. If Harish and Rekha are given boxes that are not special, which of the following can we infer?
Harish is happy
No bubble gums in Rekha’s box
No toffees in Harish’s box
There are peppermints in Rekha’s box
Question 3 Explanation: 
Let t denote that a box has toffees, g denote that it has gems, b denote the presence of bubble gums and p the presence of peppermints. If a box is special, it satisfies (g ∨ t) ⇒ (b ∧ p). A non-special box satisfies (g ∨ t) ∧ (¬b ∨ ¬p). Since g ∨ t holds, Harish is happy and (a) can be inferred. Since it is possible
Question 4
In a class, every student likes exactly one novelist and one musician. If two students like the same novelist, they also like the same musician. The class can be divided into novelist groups, each group consisting of all students who like one novelist. Similarly, musician groups can be formed. So each student belongs to one musician group and one novelist group. Which of the following is a valid conclusion?
There are more musician groups than novelist groups
There are at least as many novelist groups as musician groups
For every musician group, there is a bigger novelist group
For every novelist group, there is a musician group of the same size
Question 4 Explanation: 
Each novelist group is a subset of some musician group. So the number of novelist groups are at least as large as the number of music groups, which is option (b). Options (a), (c) and (d) are all violated in a scenario where there are two students s1 and s2, two novelists n1 and n2, and one musician m, with s1 liking n1 and m, and s2 liking n2 and m.
There are 4 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact to get access