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?
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.
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.