GATE 2024 CS1 Q.61: solution and answer

Official answer: 44Source: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

1. Count all strings over $\{0,1\}$ of length $0$ to $5$: $2^0+2^1+\cdots +2^5=2^6-1=63$.

2. Strings in $r=0^{\ast }+1^{\ast }$ are $\epsilon$ together with the all-0 strings and all-1 strings. Each length $1$ to $5$ gives $2$ such strings, so $|r|=1+2\times 5=11$.

3. Strings in $01^{\ast }$ of length at most $5$ are $0,01,011,0111,01111$, one per length, so $5$ strings. Strings in $10^{\ast }$ are $1,10,100,1000,10000$, also $5$ strings.

4. The two parts of $s$ start with different symbols, so they share no string and $|s|=5+5=10$.

5. Overlap of $s$ with $r$: a string of $s$ lies in $r$ only if it uses a single symbol. In $01^{\ast }$ that is only $0$, and in $10^{\ast }$ only $1$. Every other string of $s$ contains both $0$ and $1$. So $|r\cap s|=2$.

6. $|r\cup s|=11+10-2=19$.

7. Strings of length at most $5$ in neither $r$ nor $s$: $63-19=44$.