# Construct a regular expression for a specified language

Let $$\Sigma = \{a, b\}$$ I need to find a regular expression for this language:

• The language where the number of $$a$$'s and $$b$$'s is equal and for every prefix of a word the absolute value of the difference between the number of $$a$$'s and $$b$$'s isn't greater than 2

But I can't seem to find an expression for this language. From what I understand for each $$w\in L_2$$, $$\#_a(w)= \#_b(w)$$ and for every prefix $$p$$ such that $$w=pu$$, $$|\#_a(p)- \#_b(p)| \leq 2$$, so I need to somehow enforce that for every $$a$$ there will be a $$b$$ and that the difference between them will never exceed $$2$$, yet I don't think I know how. Can I make the expression include conditions? i.e if $$|\#_a(p)- \#_b(p)| = 1$$ can I only accept substrings such that $$|\#_a(p)- \#_b(p)| \leq 2$$ would be kept?

• Please focus on one question only. Apr 5, 2022 at 16:28

I think the regular expression is easier to find using a DFA, but an explaination may be possible without (although the reasonning is the same).

First, note that a word of this language (let's note it $$L$$) is necessarily of even length. We will then consider pairs of consecutive letters in a word $$w\in L$$:

• if the word $$w = uv$$ with $$u = ab$$ or $$u = ba$$, then it is clear that $$v\in L$$;
• if $$u = aa$$, then necessarily the first letter of $$v$$ is a $$b$$. Consider $$v = b\alpha v'$$, with $$\alpha\in \{a, b\}$$:
• if $$\alpha = b$$, then $$v' \in L$$ and we are back to square one;
• else, $$\alpha = a$$, and we can apply the reasonning we did for $$v$$ to $$v'$$;
• it is the same thing for $$u = bb$$.

A corresponding regular expression could then be:

$$(ab + ba + aa(ba)^*bb + bb(ab)^*aa)^*$$

So I might've come up with the answer looking at Brian M. Scott answer to a similar question

if I build the regular expression $$(aabb + bbaa)^*$$ The parity between $$a$$'s and $$b$$'s is always kept, easily proven using induction (using the same outline as in the cited answer above), and for every substring, $$p$$, $$|\#_a(p) - \#_b(p)| \le 2$$, because for every substring, $$x \in \{aabbaabb, aabbbbaa, bbaaaabb, bbaabbaa\}$$, $$|\#_a(x) - \#_b(x)| \le 2$$

• $ab$ is a word of the initial language, but not of your regular expression. Apr 5, 2022 at 17:00
• @Nathaniel yeah I saw it just after I posted the answer, though I think I might be in the right direction Apr 5, 2022 at 17:05