Question

Give a regular expression for the language L1 of strings over alphabet Σ = {a, b, c} that have a pair of identical symbols separated by a substring whose length is a multiple of 3. For example, abcba, bb, cbabcb ∈ L1 but ε, a, bcbcab /∈ L1. Note that cbabcb is in the language two different ways. Briefly justify your answer.

Answer 1

Step-by-step explanation:

(a(aaa+aab+aac+aba+abb+abc+aca+acb+acc+baa+bab+bac+bba+bbb+bbc+bca+bcb+bcc+caa+cab+cac+cba+cbb+cbc+cca+ccb+ccc)^{*}a)\,\,+\,\,(b(aaa+aab+aac+aba+abb+abc+aca+acb+acc+baa+bab+bac+bba+bbb+bbc+bca+bcb+bcc+caa+cab+cac+cba+cbb+cbc+cca+ccb+ccc)^{*}b)\,\,+\,\,(c(aaa+aab+aac+aba+abb+abc+aca+acb+acc+baa+bab+bac+bba+bbb+bbc+bca+bcb+bcc+caa+cab+cac+cba+cbb+cbc+cca+ccb+ccc)^{*}c)

The strings generated are as follows:

'a' separated from​​ 'a' by any string which is a multiple of 3

or

'b' separated from​​ 'b' by any string which is a multiple of 3

or

'c' separated from​​ 'c' by any string which is a multiple of 3.