>>10470376Use regular expressions to (carefully) uniquely generate all strings that aren't accepted by the DFA

The terms that stop at S are e (the empty string)

... at A are A(BA)* + B(AB)*A

... at B are B(AB)* + A(BA)*B

... at AA are [ A(BA)*A + B(AB)*AA + ( B(AB)*B + A(BA)*BB )(AB)*AA ][ (BA)*BB(AB)*AA ]*

... at BB are [ B(AB)*B + A(BA)*BB + ( A(BA)*A + B(AB)*AA )(BA)*BB ][ (AB)*AA(BA)*BB ]*

... at A_ are [ B(AB)*B + A(BA)*BB + ( A(BA)*A + B(AB)*AA )(BA)*BB ] (AB)*A [ A(BA)*BB(AB)*A ]*

... at B_ are [ A(BA)*A + B(AB)*AA + ( B(AB)*B + A(BA)*BB )(AB)*AA ] (BA)*B [ B(AB)*AA(BA)*B ]*

Converting these to generating functions is pretty easy.

at S ~ 1

at A ~ (t+t^2)/(1-t^2)

at B ~ (t+t^2)/(1-t^2)

at AA ~ [ (t^2 + t^3)/(1-t^2) + (t^2 + t^3)/(1-t^2) * (t^2)/(1-t^2) ] * [ 1/( 1 - (t^4)/( 1-t^2 )^2 ) ]

at BB ~ [ (t^2 + t^3)/(1-t^2) + (t^2 + t^3)/(1-t^2) * (t^2)/(1-t^2) ] * [ 1/( 1 - (t^4)/(1-t^2 )^2 ) ]

at A_ ~ [ (t^2 + t^3)/(1-t^2) + (t^2 + t^3)/(1-t^2) * (t^2)/(1-t^2) ] * (t/(1-t^2)) * [ 1/( 1 - (t^4)/( 1-t^2 )^2 ) ]

at B_ ~ [ (t^2 + t^3)/(1-t^2) + (t^2 + t^3)/(1-t^2) * (t^2)/(1-t^2) ] * (t/(1-t^2)) * [ 1/( 1 - (t^4)/( 1-t^2 )^2 ) ]

Adding all of these terms yields (2t^3 + 2t^2 + 2t + 1))/(1-2t^2)

Which gives (3t + 2)/(1 - 2t^2) - t - 1

If n=0, the coefficient of t^n is 1 (the empty string)

If n=1, the coefficient of t^n is 2

If n>=2 is even, the coefficient of t^n is 2^(n/2 + 1)

If n>=3 is odd, the coefficient of t^n is 3*2^((n-1)/2)

I might be a robot.