1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Please focus on one question only. $\endgroup$
    – Nathaniel
    Commented Apr 5, 2022 at 16:28

2 Answers 2

2
$\begingroup$

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)^*$$

$\endgroup$
0
$\begingroup$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.