Well what if we say that government is the means by which a people organize their business and a state is that entity which maintains a monopoly on the legitimate use of force?
We can have a government because we can set expectations and behavior. Only when we have police and a state apparatus do we then become a society whose mode of governance is via the state.