>>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.
