+61480015851
FIT2014: One-Dimensional Go- IT Report Writing Assignment
Download Solution
Order New Solution
Internal Code: MAS1754
The claim you are trying to prove here is the single claim that all three of these inequalities are true, simultaneously. You should not try to construct three separate proofs, one for each inequality (though it’s fine for your proof to have different cases).
For bonus marks
How much can you improve on these upper bounds? In particular, can you reduce the 2.8 to a smaller number? If so, what can you reduce it to?
2.In this question, we represent each 1D-Go position as a string over the alphabet {b,w,u}. The i-th character in the string represents the state of vertex i in the n-vertex path graph, with b, w, u representing Black, White and Uncoloured, respectively. So the three positions given as examples in Tute 1, Q5, are represented by the following strings in turn:
uubbubwwwuu This position is legal.
uubbubwwwbu This position is illegal, and it is not almost legal.
uubbuuwwwbb This position is almost legal (hence illegal).
(a) Build a Finite Automaton that accepts precisely those strings that represent legal positions.
(b) How would you modify your FA so that it accepts precisely those strings that represent almost legal positions?
(No need to draw a new FA. Just describe clearly and precisely the change you need to make.)
(c) How would you modify your FA from (a) so that it accepts precisely those strings that represent positions that are neither legal nor almost legal? (No need to draw a new FA. Just describe clearly and precisely the change you need to make.)
Preparation for 3:
3.For this problem, we represent positions in 1D-Go using Prolog lists, with each member of the list being b,w,u according as the corresponding vertex is Black, White, or Uncoloured, respectively. So the three positions given as examples in Tute 1, Q7, are represented by the following lists in turn:
[u,u,b,b,u,b,w,w,w,u,u] This position is legal.
[u,u,b,b,u,b,w,w,w,b,u] This position is illegal, and it is not almost legal.
[u,u,b,b,u,u,w,w,w,b,b] This position is almost legal (hence illegal).
(a) Modify the program in prob3a.pl to create a Prolog program which implements a Finite Automaton for legal positions in 1D-Go.
(You will probably want to do this using the FA you wrote in Problem 2, provided that one is correct.)
IT Report Writing Assignment:
Task: 1. Recall the exercises on one-dimensional Go in Tute 1, Q7, and Tute 2, Q9. In Tute 2, Q9, we saw that legal and almost-legal positions can be counted using the following scheme.
The claim you are trying to prove here is the single claim that all three of these inequalities are true, simultaneously. You should not try to construct three separate proofs, one for each inequality (though it’s fine for your proof to have different cases).
For bonus marks
How much can you improve on these upper bounds? In particular, can you reduce the 2.8 to a smaller number? If so, what can you reduce it to?
2.In this question, we represent each 1D-Go position as a string over the alphabet {b,w,u}. The i-th character in the string represents the state of vertex i in the n-vertex path graph, with b, w, u representing Black, White and Uncoloured, respectively. So the three positions given as examples in Tute 1, Q5, are represented by the following strings in turn:
uubbubwwwuu This position is legal.
uubbubwwwbu This position is illegal, and it is not almost legal.
uubbuuwwwbb This position is almost legal (hence illegal).
(a) Build a Finite Automaton that accepts precisely those strings that represent legal positions.
(b) How would you modify your FA so that it accepts precisely those strings that represent almost legal positions?
(No need to draw a new FA. Just describe clearly and precisely the change you need to make.)
(c) How would you modify your FA from (a) so that it accepts precisely those strings that represent positions that are neither legal nor almost legal? (No need to draw a new FA. Just describe clearly and precisely the change you need to make.)
Preparation for 3:
3.For this problem, we represent positions in 1D-Go using Prolog lists, with each member of the list being b,w,u according as the corresponding vertex is Black, White, or Uncoloured, respectively. So the three positions given as examples in Tute 1, Q7, are represented by the following lists in turn:
[u,u,b,b,u,b,w,w,w,u,u] This position is legal.
[u,u,b,b,u,b,w,w,w,b,u] This position is illegal, and it is not almost legal.
[u,u,b,b,u,u,w,w,w,b,b] This position is almost legal (hence illegal).
(a) Modify the program in prob3a.pl to create a Prolog program which implements a Finite Automaton for legal positions in 1D-Go.
(You will probably want to do this using the FA you wrote in Problem 2, provided that one is correct.)