Help building Digital Logic Circuit (from truth table and state diagram)
I entered your truth table into Logisim's combinational analysis window and got this.  Is that what you're looking for?


As far as having two bits of state, it doesn't really matter so long as the outcome is the same.  I just used S0 and S1 for the old state and BCar and CCar for the Input.  New0 and New1 are the new output state.