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 _________
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
GATE 2024 CS (CS2) Q22– Which one of the following regular expressions is equivalent to the language accepted by…
GATE 2024 CS (CS2) Q41– Let M be the 5-state NFA with -transitions shown: start state 1 with ε to 2 and ε to 4;…
GATE 2024 CS (CS2) Q62– Let L 1 be the language represented by the regular expression b*ab*(ab*ab*)* and L…
GATE 2023 CS Q14– Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the…
GATE 2023 CS Q63– Consider the language L over the alphabet 0, 1, given below: L = \w \0,1\* w does not…
GATE 2022 CS Q12– Which one of the following regular expressions correctly represents the language of the…