The GATE Grind

GATE 2024 CS (CS1) – Question 61

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Numerical answer

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: 44

Explanation

Strings over $\{0,1\}$ of length $\le5$: $1+2+4+8+16+32=63$ (including $\varepsilon$ of length 0).

**$r=0^*+1^*$:** $\varepsilon$ plus $0^k$ and $1^k$ for $k=1..5$: $1+2\cdot5=11$ strings.

**$s=01^*+10^*$:** strings $01^k$ and $10^k$.
- Length 1 ($k=0$): `0` and `1`, both already in $r$.
- Length $L=2..5$: $01^{L-1}$ and $10^{L-1}$ contain both symbols, so are not in $r$: $2\times4=8$ new strings.

$|r\cup s|=11+8=19$. Strings in neither: $63-19=\mathbf{44}$.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →