PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q1(c)

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: Regular Expressions & Equivalence with Finite Automata

Question

Write regular expression that can generates the string that contains at least one a and two b's over .

Solution

Position-Based Regular Expression Construction: We seek a regular expression over for all strings containing at least one '' and at least two ''s in any relative order.

Let . A string containing at least two ''s has the structure:

To guarantee at least one '', the symbol '' must appear either before the first '', between the two ''s, or after the second ''.

  1. '' appears before the first '':
  1. '' appears between the two ''s:
  1. '' appears after the second '':

Combining these three mutually exhaustive placements:

Alternatively, viewing the two ''s and one '' as three required markers in any permutation:

Answer:

The regular expression is , capturing all strings containing at least one and at least two 's in any arrangement.

All past exam questions for Theory of Computation