Finite State Acceptor

My individual codes and parity property is:

A	B	C	PARITY
00000	0100	0001	Even 1

You have been assigned your own individual codes for the letters A, B, C and also a parity property. You can obtain your codes and parity property by following the FSA codes and party property link below.

You are the central hub for a communication system. Messages come to you as sequences of As, Bs and Cs but coded in binary. Each such binary message is to be followed by a check digit. This is a final 0 or 1 so that the entire binary message satisfies your parity property.

The parity properties are:

Even 0	The entire message (including the check digit) has an even number of 0s.
Odd 0	The entire message (including the check digit) has an odd number of 0s.
Even 1	The entire message (including the check digit) has an even number of 1s.
Odd 1	The entire message (including the check digit) has an odd number of 1s.

For example if your codes are A = 101, B = 1101, C = 001 and your parity property is Odd 0, the message ABAC would get encoded as 10111011010011. The final character is the check digit. It is a 1 because we want an odd number of 0s. So 10111011010011 is valid, but 10111011010010 and 10111011011100 are not.

Make sure you correctly understand this example before you go further. ABAC is 1011101101001. It has 5 0s, so it already has an odd number of 0s. We have to add a check digit to keep this number odd, so the check digit in this case is 1. If the parity property had been Even 0 the check digit would have been 0.

Your task is to design a binary finite state automaton (FSA) to accept all strings that represent valid messages (for your particular codes and parity property) and reject all others. This FSA must be DETERMINISTIC, REDUCED and must be in STANDARD FORM.

This project is machine marked. You can submit your attempts as many times as you like and your submission will be marked immediately. You will obtain one of 4 responses:

Your machine does not work. It does not process the string ... correctly. The string that your machine processes incorrectly may assist you in understanding why your machine does not work. 0 marks

Your machine processes all strings correctly, but is not in reduced form. This means that your machine accepts precisely those messages that are valid, but has states which are equivalent. 5 marks

Your machine processes all strings correctly. It is reduced but is not in standard form. This means that your machine accepts precisely those messages that are valid, has the right number of states, but they are not named in the correct order for standard form. 6 marks

Your machine processes all strings correctly, and is in reduced standard form. Your machine is completely correct. 8 marks

You should submit an answer once you think you have found a deterministic machine for your particular codes and parity property. If it is right, you will be told that it works but is not in reduced form. You can then reduce it, and check that you are still right so far. Once it is correctly reduced, you can then put it in standard form if necessary and submit that answer hopefully finding that it is completely correct.

Submit your answers using the submission link below (when it has become available).

*The late penalty will reduce the mark for that submission by 1 mark for each day or part thereof after the deadline. Your best score counts. So, if you have a score of 6 out of 8 before the deadline, you can still improve that score to 7 out of 8 during the 24 hours after the deadline by making a submission that is completely correct. Incorrect submissions after the deadline will not lower any score you have already obtained.

If you do not use a state, leave the entries blank. Type the number for the state for each transition. Check the tick box if the state is accepting. Leave it unchecked if it is not.

Note that while this form accepts machines with implicit black holes also known as dumping states (simply leave the transition blank) to help you with testing, a machine in reduced standard form must show any required black hole explicitly as one of the numbered states. This means that a machine with implicit black holes can get at most 6 of the 8 marks.

STATE	0 TRANSITION	1 TRANSITION	ACCEPTING
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29