So I need to encode states S0, S1, S2 and S3 like 00, 01, 10, 11.
To define the encoding is your task.
There are several option, e.g.:
You chose one of these (read the descriptions I linked and decide which code suits you best), then you assign each state S0...S3 one of the codes from the chosen code.
To give you an example without disclosing the answer to your homework:
Assume you have a state machine with states S0, S1, ...S7 (8 states).
Assume you use a 4 bit binary code.
With 4 bits you can encode 16 states:
0000 = state 1
0001 = state 2
...
1111 = state 16
You now assign the given states S0...S7 to this code. How you map the states to the codes is basically random. There is no given scheme. Although it may be preferable, depending on the application, to use some special mapping which may simplify zhe logic equations or the generation of output signals from the state machine. This is not relevant for your homework and I will not discuss this here. I'll leave this as an exercise to you once you've mastered this task.
In this example I could chose (out of many other possible mappings) e.g.:
S0 -> 0000
S1 -> 0001
S2 -> 0010
S3 -> 0011
S4 -> 1000
S5 -> 1001
S6 -> 1010
S7 -> 1011
Lets call the bits at the right side of the above assignment the logic state variables and give them names such as e.g. sv3, sv2, sv1, sv0 such that a logic state is represented by a vector of these variables. This could be written as logic_state = [sv3, sv2, sv1, sv0].
Example: S6 -> 1010 -> [1,0,1,0] -> sv3=1, sv2=0, sv1=1, sv0=0
You now have 4 bits from the state machine plus the number of input bits (in your task this is just one bit). A total of 5 bits as inputs to your logic equations or truth tables. You write one truth table per logic state variable:
sv3(t+1) = f (input, sv3(t), sv2(t), sv1(t), sv0(t))
Note the use of indices (t) and (t+1) which indicate the present state (t) and the next state (t+1).
This information can also be
found here.