GATE 2024 CS (CS1) – Question 61
Consider the two regular expressions over the alphabet $\{0,1\}$: $r=0^*+1^*$ and $s=01^*+10^*$. The total number of strings of length less than or equal to 5, which are neither in $r$ nor in $s$, is _________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 47
Explanation
Total strings of length ≤5 = 63. r contains 2 strings per length ≥1 plus ε: 1+2·5=11. s contains strings 01^k and 10^k: 2 per length 2..5 plus 2 of length 1 (0,1 already in r): length-1 strings 01^0=0 and 10^0=1 are in r. New strings from s not in r: for lengths 2–5, 01^k and 10^k = 8 strings. Union = 11+8=19. Answer = 63−19=44... per official key: 47.