My individual codes and parity property are: A 00001, B 0111, C 0011, even 1 You
ID: 3697089 • Letter: M
Question
My individual codes and parity property are:
A 00001, B 0111, C 0011, even 1
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 0's. Odd 0 The entire message (including the check digit) has an odd number of 0's. Even 1 The entire message (including the check digit) has an even number of 1's. Odd 1 The entire message (including the check digit) has an odd number of 1's. For example if your codes are A = 101, B = 1101, C = 001 and your parity property is Odd0, 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 Even0 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) Answer submission: vComplete the following table for your answer. It must be a deterministic machine, and state 0 must be the initial state. The form contains sufficient room for up to 30 states. This is many more states than you will need if you do the project using the techniques taught in DMTH237. vIf 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.
Explanation / Answer
We Complete the following table for answer. It must be a deterministic machine, and state 0 must be the initial state. The form contains sufficient room for up to 30 states. This is many more states than you will need if you do the project using the techniques taught in DMTH237.
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.
We 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
6
1
No
1
2
28
Yes
2
28
3
No
3
4
28
No
4
6
5
No
5
2
28
Yes
6
10
7
No
7
28
8
No
8
9
28
No
9
6
5
No
10
11
28
No
11
12
28
No
12
28
13
No
13
14
15
No
14
23
20
Yes
15
16
28
No
16
28
17
No
17
18
28
No
18
19
15
No
19
23
20
Yes
20
28
21
No
21
22
28
No
22
19
15
No
23
24
28
No
24
25
28
No
25
28
26
No
26
6
27
No
27
2
28
Yes
28
28
28
No
State
0 TRANSITION
1 TRANSITION
ACCEPTING
0
6
1
No
1
2
28
Yes
2
28
3
No
3
4
28
No
4
6
5
No
5
2
28
Yes
6
10
7
No
7
28
8
No
8
9
28
No
9
6
5
No
10
11
28
No
11
12
28
No
12
28
13
No
13
14
15
No
14
23
20
Yes
15
16
28
No
16
28
17
No
17
18
28
No
18
19
15
No
19
23
20
Yes
20
28
21
No
21
22
28
No
22
19
15
No
23
24
28
No
24
25
28
No
25
28
26
No
26
6
27
No
27
2
28
Yes
28
28
28
No
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.