Part -1:
Problem 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.
lB,1 = 0
lU,1 = 1
αB,1 = 1
lB,n+1 = lB,n + lU,n
lU,n+1 = 2lB,n + lU,n + 2αB,n
αB,n+1 = AB,n + αB,n
Total number of legal positions on n-vertex path = 2lB,n + 2lU,n.
Note that we have used symmetry (Tute 2, Q9(c)) to get a simpler set of equations than the ones we first derived in Q9(b).
We will now use these equations to prove upper bounds for the quantities lB,n, lU,n, αB,n, and hence for the total number of positions.
Note that all these quantities have the trivial upper bound 3n, since each vertex of the n-vertex path can be in one of three states (B/W/U), giving 3m possible positions altogether, which includes all legal and illegal positions. We will do better than this.
Prove by induction on n that, for all n ≥ 1, the quantities lB,n, lU,n, αB,n satisfy
lB,n ≤ 1.8 × 2.8n-1,
lU,n ≤ 1.82 × 2.8n-1,
aB,n ≤ 2.8n-1.
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?
Problem 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 Problem 3
Prolog is a useful language as it is easy to use it to implement finite automata (deterministic or nondeterministic). Consider the following Nondeterministic Finite Automaton.
The program in the file prob3a.pl can used to check whether a word is accepted in the above Nondeterministic Finite Automaton.
To check whether a word is accepted you must represent the word as a list of characters. For example, to test whether the words abb and b are accepted by the automaton, you can interact with Prolog as follows.
| ?-accept([a, b, b]). true
| ?-accept([b]). true
| ?-
Problem 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.)
For example, checking whether the above three strings are legal should give the following results in Prolog.
| ?-accept([u,u,b,b,u,b,w,w,w,u,u]).
true
| ?-accept([u,u,b,b,u,b,w,w,w,b,u]).
false
| ?-accept([u,u,b,b,u,u,w,w,w,b,b]).
false
| ?-
(b) [Before starting on this part, copy your prob3a.pl to a new file, prob3b.pl .]
Each position in 1D-Go may be regarded as a sequence of tokens, where each token is one of the following.
Token Interpretation
Token Interpretation
free White chain White chain that has at least one uncoloured neighbour
free Black chain Black chain that has at least one uncoloured neighbour
captured White chain White chain with no uncoloured neighbour
captured Black chain Black chain with no uncoloured neighbour
gap sequence of Uncoloured vertices between chains
Convert your FA from Problem 3(a) above (now copied into prob3b.pl) to a lexical analyser for 1D- Go positions. This lexical analyser should detect each lexeme in the input, output it on a separate line, and state on that line what the corresponding token is. It should give the answer true in all cases, so all states will be Final states. (In a more complete implementation, the lexical analyzer would use the presence of any captured chains to detect illegality, and would report at the end on whether the position is legal or not. This is not too difficult, but we will not require it in this assignment.)
For example, your program should enable the following interaction (where the positions used are the three we have been using as examples throughout).
| ?-accept([u,u,b,b,u,b,w,w,w,u,u]). uu gap
bb free Black chain u gap
b free Black chain www free White chain uu gap
true
| ?-accept([u,u,b,b,u,b,w,w,w,b,u]). uu gap
bb free Black chain u gap
b free Black chain
www captured White chain b free Black chain
u gap true
| ?-accept([u,u,b,b,u,u,w,w,w,b,b]). uu gap
bb free Black chain uu gap
www free White chain
bb captured Black chain true
| ?-
To do this, you should first modify the "path(S, [H|T])" rule in your file so that it writes out each character as it is processed, using "write(. . . )", as follows:
path(S, [H|T]) :- arc(S, H, N), write(H), path(N, T).
Then you need to modify some of the transitions so that, instead of just being facts, they become rules that cause appropriate output to occur. You will find it convenient to use write(. . . ), which can write any string you give it1, and nl, which causes Prolog to start a new line. Similar modifications will need to be made to the Final states.
Problem 4.
This problem uses the following CFG for the language of legal positions in 1D-Go.
S → P (1)
S → Q (2)
P → U (3)
P → UB (4)
P → UBS (5)
P → UW (6)
P → UWS (7)
Q → BP (8)
Q → WP (9)
U → uU (10)
U → u (11)
B → bB (12)
B → b (13)
W → wW (14)
W → w (15)
The non-terminal symbols have the following interpretations.
- Symbol S is the Start symbol, as usual.
- Symbol P is used to represent a position starting with u. The first chain of such a position will therefore be free (i.e., alive, i.e., uncaptured), since it will have an uncoloured vertex on its left. That chain can then be followed by any legal position at all, hence the rules P → UBS and P → UWS. Alternatively, that first chain could also be the last one, hence the rules P → UB and P → UW .
- Symbol Q represents a position that starts with a chain. For that chain to remain alive, the rest of the position must be a legal position that starts with u, hence the rules Q → BP and Q → WP .
- Symbol U represents any sequence of Uncoloured vertices, B represents any sequence of Black vertices, and W represents any sequence of White vertices.
In this problem, you will design and implement (in Prolog) a PDA for legal 1D-Go positions. To do this, you will modify a Prolog implementation of a simpler PDA which is provided in the file prob4b.pl. This PDA accepts the language {anbn : n ≥ 0}, and is the first PDA you met in Lecture 11. Note that you will only need to modify the definitions of the predicates final(...) and trans(...), which are near the end of the file. You need to change them so that they specify the correct final state and transitions for the PDA you construct below.
(a) Convert the above CFG for 1D-Go to a Pushdown Automaton that recognises the language of legal 1D-Go positions. To do this, use the method described in Lecture 11 for converting CFGs to 1but use single forward-quotes at the start and end of the string; if you use double-quotes at each end, you will be given a list of ASCII values PDAs.
(b) Implement, in Prolog, your PDA from part (a) for the language of legal 1D-Go positions (with positions represented as lists, as above). Do this by appropriately modifying the Prolog PDA in prob4b.pl, as discussed above.
Problem 5.
Legal positions in 1D-Go can be scored as follows.
A gap is a sequence of uncoloured vertices bounded on each side by a coloured stone or an end of the path graph. Note that a gap may have two, one, or no bounding stones, depending on where it appears in the position. The only way it can have no bounding stones is if it spans the entire path graph, so that every vertex in the path graph is uncoloured. If the gap has just one bounding stone, then it must sit at one end of the path graph.
A gap is owned by Black if all of its bounding stones are Black. Similarly, a gap is owned by White if all of its bounding stones are White. A gap is neutral if it is neither owned by Black nor owned by White. So, if a gap has a Black stone on one side and a White stone on the other, then it is neutral. The only other kind of neutral gap is when the entire path of n vertices is uncoloured, so that the entire path is a neutral gap.
The score of a position is given by (number of vertices owned by Black) - (number of vertices owned by White)
If the score is positive, then we say that Black wins; if the score is negative, then White wins; if it is zero, then the position is a tie.
For example, consider the 11-vertex positions below, represented as strings in our usual way. (The first of these has been used as an example several times previously.) Below each string, we indicate who owns each uncoloured vertex: B for Black, W for White, and n for neutral.
uubbubwwwuu Three gaps. Score = 3 - 2 = 1. Black wins.
BB..B....WW
uubuwuuuuuw Three gaps. Score = 2 - 5 = -3. White wins.
BB.n.WWWWW.
uubuwuuwuub Four gaps. Score = 2 - 2 = 0. Tie.
BB.n.WW.nn.
uuuuuuuuuub One gap. Score = 10 - 0 = 10. Black wins.
BBBBBBBBBB.
uuuuuuuuuuu One gap. Score = 0 - 0 = 0. Tie.
nnnnnnnnnnn
Your task:
Using the Pumping Lemma for regular languages, prove that the language of positions that Black wins is not regular.
For bonus marks:
Prove or disprove: the language of positions that Black wins is context-free.
Problem 6.
In this question, the Turing machine you build in Tuatara must have q1 as its Start State and q2 as its Accept State.
Build a Turing machine which takes, as input, a legal 1D-Go position (represented as a string over the alphabet {b,w,u} in the usual way) and computes the number of neutral points in that position.
n
The output must consist solely of a string of n xs, i.e., ¸xxxxs • x¸, where n is the number of neutral points; as usual, the rest of the tape must be blank.
If the input string has no neutral points, then the output is the empty string. (In other words, when the computation finishes, the tape should be entirely blank.)
For example, the five positions used to illustrate scoring in the previous question should yield the output strings shown in the right-hand column of the following table.
position # neutral points Turing machine output string
uubbubwwwuu 0 (empty string)
uubuwuuuuuw 1 x
uubuwuuwuub 3 xxx
uuuuuuuuuub 0 (empty string)
uuuuuuuuuuu 11 xxxxxxxxxxx
You do not need to check that the input position is legal; just assume that it is.
Your work on Tute 5, Q6, should help you get started on this Problem.
Part -2:
1. Let ODD-ODD be the language of strings, over the alphabet {a,b}, that contain an odd number of a's and an odd number of b's. Let ODD-ODD be its complement.
Prove that PALINDROMES ⊆ ODD-ODD.
2. Prove the following statement, by mathematical induction:
(*) The sum of the first k odd numbers equals k2.
(a) First, give a simple expression for the k-th odd number.
(b) Inductive basis: now prove the statement (∗) for k = 1.
Assume the statement (*) true for a specific value k. This is our Inductive Hypothesis.
(c) Express the sum of the first k + 1 odd numbers . . .
1 + 3 + • • • + ((k + 1)-th odd number)
. . . in terms of the sum of the first k odd numbers, plus something else.
(d) Use the inductive hypothesis to replace the sum of the first k odd num- bers by something else.
(e) Now simplify your expression. What do you notice?
(f) When drawing your final conclusion, don't forget to briefly state that you are using the Principle of Mathematical Induction!
3. (a) Prove, by induction on n, that for all n ≥ 3,
n! ≤ (n - 1)n.
(b) Can you use a similar proof to show that n! ≤ (n - 2)n? What assumptions do you need to make about n? How far can you push this: what if 2 is replaced by a larger number? What is the best upper bound of the form f (n)n that you can find, where f (n) is some function of n?
4. Three boys, Adam, Brian and Claude, are caught, suspected of breaking a glass window. When the boys were questioned by police:
Adam said: ‘Brian did it; Claude is innocent'. Brian said: ‘If Adam is guilty then so is Claude'. Claude said: ‘I didn't do it; one of the others did'.
The police believed that all the boys were telling the truth, and there- fore concluded that Brian broke the window and the others didn't.
Using the following propositions express the statements of the boys and the police conclusion in propositional logic.
A: Adam broke the window.
B: Brian broke the window.
C: Claude broke the window.
Assuming that all the boys were telling the truth, was the police conclusion logically valid?
5. Distributive Law for propositional logic:
(a) Prove that
P ∨ (Q ∧ R) is logically equivalent to (P ∨ Q) ∧ (P ∨ R).
(b) Prove that
P ∧ (Q ∨ R) is logically equivalent to (P ∧ Q) ∨ (P ∧ R),
using part (a) and a rule named after a friend of Charles Babbage.
6. Prove that
(P1 ∧....∧ Pn) ⇒ C is logically equivalent to ¬P1 ∨ • • • ∨ ¬Pn ∨ C
7. One-dimensional Go.
This question uses some concepts from the ancient east Asian board game known as Go in the West, W´eiq´i in China, Go or Igo in Japan, and Baduk in Korea. This game is over 2,000 years old, and is generally regarded as harder than Chess. Indeed, until very recently, computer programs for Go could not de- feat human professionals (in contrast to Chess, where the best computer players have been stronger than human world champions since the late 1990s).
That changed dramatically earlier this year, with stunning performances by the program AlphaGo, created by Google DeepMind. (This company began as a start-up in London in 2010 and was acquired by Google in 2014.) In January, it defeated the European champion Fan Hui in every game of a five-game match: https://www.nature.com/news/google-ai-algorithm-masters-ancient-game- of-go-1.19234. Then in March it defeated Lee Sedol of Korea, generally re- garded as the best player in the world in recent times: https://gogameguru. com/tag/deepmind-alphago-lee-sedol/. The final score in that five-game match was 4-1 in favour of AlphaGo.
Go is played on a graph, usually a square lattice (grid) of 19 × 19 vertices.
But we will use much simpler graphs in this question, namely path graphs with n vertices and n - 1 edges, where n ≥ 1. For example, with n = 11 we get the following path graph with 11 vertices and 10 edges.
. . . . . . . . . . .
1 2 3 4 5 6 7 8 9 10 11
A position consists of a placement of black and white stones on some of the vertices of the graph. Each vertex may have a black stone, or a white stone (but not both), or be uncoloured (i.e., vacant). A position is legal if every vertex with a stone can be linked to an uncoloured vertex by a path consisting entirely of vertices with stones of that same colour (except for the uncoloured vertex at the end).
For example, the following position is legal, since each of its three "chains" of consecutive vertices of the same colour either starts or ends with an uncoloured vertex.
. . • • . • ο ο ο . .
But the following position is illegal, since it has a chain of white vertices with black vertices at each end. (The position has four chains altogether, and three are ok. But it only takes one without an uncoloured neighbour to make the position illegal.)
. . • • . • ο ο ο . .
We number the vertices on the path graph from 1 to n, from left to right. We say that a position on this path graph is almost legal if vertex n is coloured (i.e., has a stone) and its chain is not next to an uncoloured vertex, but every other chain is next to an uncoloured vertex. In other words, it is illegal, but the only chain making it illegal is the chain containing vertex n; all other chains are ok. The two positions given above are not almost legal: the first is legal (so it isn't almost legal), while the second is illegal but the illegality is not due to the last vertex (which in this case is uncoloured). The following position is almost legal. All its chains are ok except the last one on the right.
. . • • . • ο ο ο . .
Let VB,n, VW,n, VU,n, LB,n, LW,n, LU,n, AB,n, AW,n be the following propo- sitions about a position on the n-vertex path graph.
VB,n Vertex n is Black.
VW,n Vertex n is White.
VU,n Vertex n is Uncoloured.
LB,n The position is legal, and vertex n is Black.
LW,n The position is legal, and vertex n is White.
LU,n The position is legal, and vertex n is Uncoloured. AB,n The position is almost legal, and vertex n is Black. AW,n The position is almost legal, and vertex n is White.
(a) Use the propositions LB,n, LW,n, LU,n (together with appropriate connec- tives) to write a logical expression for the proposition that the position is legal.
Now consider how legality and almost-legality on the n-vertex path graph are affected by extending the path to vertex n + 1.
(b) If LB,n is true, what possible states (Black/White/Uncoloured) can vertex n + 1 be in, if we want the position to be legal on the n + 1-vertex path as well? Do the same for LW,n and LU,n.
(c) If AB,n is true, what possible states can vertex n + 1 be in, if we want the position to be legal on the n + 1-vertex path?
Do the same for AW,n.
Why is there no line for AU,n in the table?
(d) Construct a logical expression for LB,n+1 using some of the propositions V,n+1, L,n, A,n in the above table. (In other words, you can only use the L-propositions and A-propositions for the n-vertex path graph, and the V - propositions for vertex n + 1.)
Do the same for LW,n+1, LU,n+1, AB,n+1, AW,n+1.
8. Using the function symbol father, the predicate taller, and the constant symbols claire and max, convert the following sentences to First Order Logic. Assume that taller(X,Y) means X is taller than Y and the universe of discourse is "all people".
i. Max's father is taller than Max but not taller than Claire's father.
ii. Someone is taller than Claire's father.
iii. Everyone is taller than someone else.
iv. Everyone who is taller than Claire is taller than Max.
9. The following problem comes from W. Clocksin, Clause and Effect: Prolog Programming for the Working Programmer, Springer, 1997.
Suppose the following are defined:
male(bertram).
male(percival).
female(lucinda).
female(camilla).
dancePair(X, Y) :-
male(X), female(Y).
What happens for the following goals? Indicate what the first answer is (if any), and what the subsequent answers are (if any) on backtracking.
i. ?- dancePair(percival, X).
ii. ?- dancePair(apollo, daphne).
iii. ?- dancePair(camilla, X).
iv. ?- dancePair(X, lucinda).
v. ?- dancePair(X, Y).
10. Arithmetic in Prolog.
Prolog's arithmetic capabilities include the following.
- Operators: X + Y, -X, X-Y, X*Y, X/Y, X mod Y, . . .
- Functions: abs(X), max(X, Y), sin(X), . . .
- Relations: X=Y, X < Y, X > Y, X >= Y, X =< Y, X \ = Y, X == Y,
. . .
- is - which we read as "evaluates arithmetic expression". For example:
| ?- X is 2*3 + 4. X = 10 ?
true
(a) Explore how these constructs work in Prolog. E.g., do some simple cal- culations; try using variables on either or both sides of is; try to identify the difference between X=Y and X==Y. Ask about anything that puzzles you, or look it up in Clocksin & Mellish.
(b) Consider the following code.
factorial(0, F) :-
F is 1. factorial(N, F) :-
N > 0,
N1 is N-1,
factorial(N1, F1), F is N*F1.
Try it out and see if it computes the factorial function correctly. Also, try queries factorial(3,f) and factorial(N,6) and explain what you observe.
Explain in detail what happens, step-by-step, when computing 4! using this Prolog code.
11. Lists in Prolog.
A list t1, . . . , tn can be represented as:
[t1, . . . , tn]
For example:
This is also represented as:
[a,b,c,d]
[a | [b,c,d] ]
Here, a is the head of the list, while [b,c,d] is the tail. The empty list is [ ] . Define a predicate size(L,N) in Prolog which correctly determines the size
N of a list L.
Firstly, spend a few minutes thinking about how to do this from scratch. Then, take the following steps.
(a) It is a fact that the size of the empty list is zero. Write this as a Prolog fact.
Now, suppose your list is nonempty. How can you get a smaller list from it?
How is the size of the original list related to the size of the smaller list?
If your list is nonempty, then it is of the form [H|T]. So, start writing a rule whose left side is size([H|T], N) .
(b) What do you want on the right-hand side of this rule? You'll need an- other term for size, but with what list? You can also use some of the arithmetic capabilities (see previous question).
Once you have finished your definition of size and got it working, compare its behaviour with Prolog's inbuilt length function, to test it.
(c) Does this kind of testing prove that your program works?
(d) Prove by mathematical induction that your program correctly calculates the length of a list.
Supplementary exercises
12. Ingrid, Ann and Karen are considering going to a party. Ingrid says that she will go if Karen goes but Ann does not. Ann says she will go if both Ingrid and Karen go. Karen says she will go if and only if an even number of them go.
Using the following propositions express the statements made by Ingrid, Ann and Karen.
I: Ingrid will go to the party.
A: Ann will go to the party.
K: Karen will go to the party.
Assuming everyone is telling the truth, is it logically valid to conclude that Ann and Karen will go to the party but Ingrid will not? If Ann was lying, then is it logically valid to conclude that Karen and Ingrid will go to the party but Ann will not?
13. A vertex cover in a graph tt is a set VC of vertices such that every edge of tt is incident with some vertex in VC.
A clique in a graph is a set of vertices that are pairwise adjacent. (I.e., every pair of vertices in the clique is linked by an edge.)
The complement of a graph tt, written G, is defined as follows. It has the same vertex set of G, and its edge set consists of every pair of vertices that are not adjacent in G.
Suppose we have a graph, and that chosen is a unary predicate that takes a vertex of our graph as its argument. This predicate therefore defines a subset of the vertex set of the graph (the "chosen vertices"). Suppose also that we have the following predicates, with the indicated meanings.
vertex(X) X is a vertex in our graph
edge(X,Y) there is an edge between vertices X and Y
(a) Write a statement in predicate logic, using the predicates vertex, edge and chosen, to say that the chosen vertices form a vertex cover.
(b) Write a statement in predicate logic, using the same predicates, to say that the chosen vertices form a clique.
(c) Prove that, for any k, the number of vertex covers of size k in tt equals the number of cliques of size n - k in G.
(d) Give the relationship between the size of the smallest vertex cover in G and the size of the largest clique in G.
14. The following Java function gcd computes the greatest common divisor of two integers.
public static int gcd(int x, int y)
{
if (x < y)
return gcd(y,x);
if (y == 1) return 1;
if (x == y) return x;
return gcd(x-y,y);
}
i. Convert the function gcd into a Prolog program.
ii. Describe the goals which need to be satisfied to find the greatest common divisor of 6 and 15.
iii. How could you use the function mod to improve your Prolog program.
iv. If your program does not handle negative integers, then extend your pro- gram to handle them.
15. Recall (or look up) the famous Towers of Hanoi problem. Write a Prolog predicate, move(N,X,Y,Z), which writes the sequence of moves needed to move a pile of N discs, initially on peg X, over to peg Z, where peg Y is treated as the spare peg and X, Y, Z ∈ {1, 2, 3}.
You'll need to use the built-in function write.