# Regular expressions and regular languages: GATE CS question with solution

From the GATE Daily set of 26 October 2026, question 8 of 10 (https://gatedaily.in/q/2026-10-26-regex-strings-without-bb/). Difficulty: standard.

### Q.8 · Theory of Computation · Regular expressions and regular languages · MCQ, 1 mark (choose one option)

Let $L$ be the set of all strings over the alphabet $\{a, b\}$, including the empty string $\varepsilon$, that do **not** contain $bb$ as a substring. Which one of the following regular expressions denotes exactly $L$?

(A) $(a + ba)^*(\varepsilon + b)$
(B) $(a + ba)^*$
(C) $(a + ab)^*(\varepsilon + b)$
(D) $(\varepsilon + b)(a + ba)^*$

**Answer:** (A) $(a + ba)^*(\varepsilon + b)$

**Solution.** **Method: describe the structure of the language, then test each option on short witnesses.**

In a string with no $bb$, every $b$ is followed by an $a$ unless it is the last symbol. So the string is a sequence of blocks $a$ or $ba$, optionally followed by one final $b$: $(a + ba)^*(\varepsilon + b)$. Conversely, gluing such blocks never puts two $b$s together, because each $ba$ block ends in $a$.

Test the others with one string each:

| Option | Witness | Why it fails |
|---|---|---|
| (b) | $b$ | in $L$, but every string of (b) is empty or ends in $a$ |
| (c) | $abb$ | generated as $ab \cdot b$, but contains $bb$ |
| (d) | $bba$ | generated as $b \cdot ba$, but contains $bb$ |

**Trap.** Options (c) and (d) look like harmless rearrangements of (a), but moving the optional $b$ to the wrong side of a block lets it touch another $b$. Checking one string per option, especially strings at the boundaries (empty, ending in $b$, starting with $b$), exposes this quickly.

**What was tested:** building a regular expression from a forbidden-substring condition and checking candidates with witness strings in both directions.

**Remember:** To verify a regular expression for a language, look for two kinds of witness: a string in the language the expression misses, and a string the expression generates that is not in the language.

**Why each option:**
- (A) Every b except possibly the last is immediately followed by an a, and a final lone b is allowed.
- (B) Every string here ends in a or is empty, so it misses strings in L that end in b, such as b and ab.
- (C) Generates abb (ab then b), which contains bb, and cannot generate ba, which is in L.
- (D) Generates bba (b then ba), which contains bb, and cannot generate ab, which is in L.