regex

Match a sequence of two distinct characters where the disparity in count is not greater than 3

The problem

You are provided two things: A bag filled with balls of two types, labeled as A and B, and a two-pan balance scale. Each ball is sequentially taken out and placed on the corresponding pan. The game is won if all the balls are taken from the bag while ensuring that there is never a difference greater than 3 in the number of balls on the scale at any point.

Given a sequence of As and Bs, is it possible to determine whether it is a winning game using regex alone?

Credits

This question derives from Regex can't have diference greater than 3, which was closed due to the OP's undesire to clarify the problem. Regardless, the problem was interesting; I was encouraged to post this question thanks to @Mark.

Solution

  • Build the DFA.

    Denote states by numbers.
    Starting state is 1.
    All except 8 are accepting states.

    DFA generated with https://ivanzuzak.info/noam/webapps/fsm_simulator/

    Transitions:

    (1,A)->2    (1,B)->5
(2,A)->3    (2,B)->1
(3,A)->4    (3,B)->2
(4,A)->8    (4,B)->3
(5,A)->1    (5,B)->6
(6,A)->5    (6,B)->7
(7,A)->6    (7,B)->8
(8,A)->8    (8,B)->8

    Giving:

    1 = e + 2B + 5A
2 = 1A + 3B
3 = 2A + 4B
4 = 3A
5 = 1B + 6A
6 = 5B + 7A
7 = 6B
8 = 4A + 7B + 8A + 8B

    Then applying Arden's Theorem to solve for 1+2+3+4+5+6+7 gives:

    ^(
  ((A(A(AB)*B)*B)|(B(B(BA)*A)*A))*
|(((A(A(AB)*B)*B)|(B(B(BA)*A)*A))*A(A(AB)*B)*)
|(((A(A(AB)*B)*B)|(B(B(BA)*A)*A))*A(A(AB)*B)*A(AB)*)
|(((A(A(AB)*B)*B)|(B(B(BA)*A)*A))*A(A(AB)*B)*A(AB)*A)
|(((A(A(AB)*B)*B)|(B(B(BA)*A)*A))*B(B(BA)*A)*)
|(((A(A(AB)*B)*B)|(B(B(BA)*A)*A))*B(B(BA)*A)*B(BA)*)
|(((A(A(AB)*B)*B)|(B(B(BA)*A)*A))*B(B(BA)*A)*B(BA)*B)
)$

    which becomes a bit more legible after simplification:

    ^
(
 (A(A(AB)*B)*B)
|(B(B(BA)*A)*A)
)*
(
 (A(A(AB)*B)*(A(AB)*A?)?)
|(B(B(BA)*A)*(B(BA)*B?)?)
)?
$

    Adapting the test from the other answer: https://regex101.com/r/DsYrzp/5