Back to the 2026 paper

Module 1: Introduction, Lexical Analysis

20262m

The regular expression (a∣b)∗(a \mid b)^* represents:
(i) Strings containing only aa
(ii) Strings containing only bb
(iii) All strings over {a,b}\{a, b\}, including ε\varepsilon
(iv) Strings beginning with abab

Worked SolutionAI Assisted

Answer: (iii) All strings over {a,b}\{a, b\}, including ε\varepsilon

Explanation

  • (a∣b)(a \mid b) matches exactly one symbol: either aa or bb.
  • The Kleene star ∗^* allows zero or more repetitions of that choice.

So the language is {ε,a,b,aa,ab,ba,bb,aaa,… }\{\varepsilon, a, b, aa, ab, ba, bb, aaa, \dots\}, i.e. every string over the alphabet {a,b}\{a,b\}, with ε\varepsilon (zero repetitions) included.

Why the other options fail:

  • (i), (ii): they allow only one of the two symbols.
  • (iv): it forces the string to start with abab, but (a∣b)∗(a\mid b)^* also accepts bb, ε\varepsilon, etc.

(iii)\boxed{\text{(iii)}}

Similar questions

Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.