Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Computing Theory
COSC 1107/1105 Final Exercise (Practice version Answers) 1 Assessment details 1. Consider the grammar derivations below. S ⇒ aSb⇒ aaSbb⇒ aacSdbb⇒ aacdbb S ⇒ A⇒ xAy ⇒ xxAyy ⇒ xxB@yy ⇒ xxxB@yy ⇒ xxxx@yy S ⇒ A⇒ @C ⇒ @Cy ⇒ @Cyy ⇒ @yyy (a) From the above derivations, construct rules that must exist in any context-free grammar G for which these derivations are correct. Answer: From the first derivation we can see that the rules must include S → aSb, S → cSd and S → λ. From the second derivation we can add the rules S → A, A → xAy, A → B@, B → xB and B → x. From the third derivation we can add the rules A → @C, C → Cy and C → y. As this covers all the derivation steps in all three derivations above, we get the rules below. S → aSb | cSd | A | λ A→ xAy | B@ | @C B → xB | x C → Cy | y (b) Assuming that these are all the rules in G, give L(G) in set notation. Answer: L(G) = {wxi@yj(bd(w))R | i 6= j, i, j ≥ 0, w ∈ {a, c}∗} ∪ {λ} where bd(w) is w with all a’s replaced by b’s and all c’c replaced by d’s, and wR is the reverse of w. This may seem a little complicated but consider a string like aabax@yycdcc. If we replaced all d’s in the grammar with c’s and b’s with a’s, then the language would be {wxi@yjwR|i 6= j, i, j ≥ 0, w1 ∈ {a, c}∗}. So all we need to do to get the language of the original grammar is replace the a’s and c’s in wR with b’s and d’s respectively. Another point to note is that this language is not the same as the one below. {w1xi@yjw2 | i 6= j, i, j ≥ 0, w1 ∈ {a, c}∗, w2 ∈ {b, d}∗, |w1| = |w2|} Note that this latter language contains strings such as aabxx@yddd, which cannot be derived by the grammar. where na(w) is the number of a’s in w, and similarly for b, c and d. (c) Is there a regular grammar for L(G)? Explain your answer. Answer: There is no regular grammar for L(G). This language is context-free but not regular because there is a need to count the number of x’s and y’s to make sure that they are different, as well as counting the number of a’s or c’s and making sure there is an equal number of b’s or d’s. (d) Construct a context-free grammar for the language below. L = {xi w1@w2 yj | i 6= 2j, i, j ≥ 0, |w1| = |w2|, w1 ∈ {a, c}∗, w2 ∈ {b, d}∗} Answer: It is best to split this up into two cases and then combine the two grammars. So let L = L1 ∪ L2 where L1 = {xi w1@w2 yj | i < 2j, i, j ≥ 0, |w1| = |w2|, w1 ∈ {a, c}∗, w2 ∈ {b, d}∗} and L2 = {xi w1@w2 yj | i > 2j, i, j ≥ 0, |w1| = |w2|, w1 ∈ {a, c}∗, w2 ∈ {b, d}∗} For a constraint like i < 2j it can be helpful to use a table like the one below. i j 2j 0 1 2 1 1 2 2 2 4 3 2 4 4 3 6 5 3 6 So for L1 we get G1 below. S → xxSy | XA A→ Ay | By X → x | λ B → aBb | aBd | cBb | cBd | @ For L2 with the constraint i > 2j the corresponding table is below. i j 2j 1 0 0 3 1 2 5 2 4 7 3 6 This leads us to the grammar G2 below. S → xxSy | C C → Cy | Dy D → aDb| | aDd | cDb | cDd | @ We can then combine these together for a grammar G for L = L1 ∪ L2. S → T | U T → xxTy | XA A→ Ay | By X → x | λ B → aBb| | aBd | cBb | cBd | @ U → xxUy | C C → Cy | Dy D → aDb | aDd | cDb | cDd | @ There are ways this could be simplified, but that is not required. Constructing the grammar this way gives confidence in its correctness, which is less obvious otherwise. 2 2. Drogo the Dreary, a distant relative of Thorin Oakenshield, has written the following discussion of intractability. There are 5 incorrect statements in the paragraph below. Identify all 5 incorrect statements and justify each of your answers. “There are a number of problems which can be solved in principle, but in practice can be very difficult to solve. These problems are often referred to as NP-complete problems, and include the Travelling Salesperson problem, 3-SAT, factorisation and vertex cover. These problems are certainly intractable, i.e. all algorithms for these problems have exponential running times. This means that they can be solved for small instances, but the rate of growth of their complexity is so fast that they cannot be solved in practice for any reasonable size. For example, the best known algorithm for the Travelling Salesperson problem can take up to 2n10 +7n2 operations for a graph of size n. This means it is in the class O(n10) and is thus intractable. Fortunately it is possible to use approximation and heuristic algorithms to find some kind of solutions to these problems, either by removing the guarantee that an optimal solution will be found, or by removing the constraint that the running time will be polynomial or less (or removing both). There are also some similar problems, such as the Hamiltonian circuit problem, which are known to be simpler to solve than the Travelling Salesperson problem and are tractable. The name NP-complete problems comes from the property that such problems have run in at most polynomial-time on a nondeterministic Turing machine.” Answer: (a) Factorisation is probably intractable, but it is not known to be NP-complete. So it is incorrect to list it as an NP-complete problem. (b) NP-complete problems are almost certainly intractable, but it is incorrect to say that these are certainly intractable. (c) The best known algorithm for the Travelling Salesperson problem is exponential, and so the statement of the running time here is certainly incorrect. (d) Algorithms with a running time of O(n10) are in the polynomial class, and hence are con- sidered tractable. (e) The Hamiltonian Circuit problem is NP-complete, as is the Travelling Salesperson problem. So these are either both intractable or both tractable, i.e. in the same complexity class. 3. The generalised Platypus game with Gandalf the White is played as follows (we will abbreviate the name of this to GPGGW). There are three machines, with two being the usual platypus machines (as in the generalised Platypus game from Assignment 2), with the third machine being Gandalf the White (which we will abbreviate to GW ), which has the transition table as below. For simplicity we assume all three machines have the same alphabet Σ. The tape is infinite in both directions, and is initially blank. q0 blank blank R q1 q0 X X R q1 q1 blank blank L q0 q1 X X L q0 where X denotes any non-blank symbol in Σ. (a) Show that the halting problem for the GPGGW is undecidable. You may use any reduction you like. Note that you may assume that the generalised Platypus problem from Assignment 2 is undecidable if you would find that helpful. 3 Answer: The simplest proof of this will be to reduce the generalised Platypus problem from Assignment 2 (which you can assume is undecidable) to this problem. The key obser- vation is that the Gandalf the White machine never changes any cell on the tape, and never terminates. This means that the generalised Platypus game with Gandalf the White halts iff the generalised Platypus game (from Assignment 2) halts. In terms of machines, consider the diagram below. Note that the machine the GPGGW only needs the machines M1 and M2 as input. It is also possible to use a reduction from the blank tape problem to the GPGGW problem as follows. Let M be the machine we want to analyse for the blank tape problem. Then M will halt on the blank tape iff the generalised Platypus problem with Gandalf the White halts for M and GW . In terms of machines, consider the diagram below. (b) Suppose the GPGGW is played on a Turing machine with a finite tape (making the halting problem decidable), and also that there is a decidable problem A for which there is a reduction from A to the GPGGW. This information could be used as an argument that the GPGGW is NP-complete, provided that some further information is known. What further information is needed? Explain your answer. 4 Answer: To show that a problem is NP-complete, we need to show that the problem is in NP, and that the problem is NP-hard, i.e. that there is a polynomial-time reduction to it from every other problem in NP. The simplest way to show the latter property is to find a polynomial-time reduction from a known NP-complete problem to it. So given the information above, we also need to know the following. i. That GPGGW is in NP. ii. That the problem A is NP-complete. iii. That the reduction from A to the GPGGW is polynomial-time. (c) Freddo the optimistic Frog likes playing Platypus tournaments. He particularly likes the 3- player version, for which a tournament of n machines will require n(n+1)(n+2)/6 matches. He ran a tournament for 100 machines which took 42.42 seconds on the family desktop computer. Encouraged with his success, he attempts to run a tournament with 10,000 machines, but when it was discovered the computer took well over a day without coming close to finishing, he was given a strict limit of 8 hours for all such tournament play (so that tournaments could be run at night when all the other frogs were asleep). What is the largest tournament size that Freddo can play within this limit? Show your working. We will call this number n1. Answer: A tournament of 100 machines will require 100×101×102/6 = 171, 100 matches. Doing this in 42.42 seconds means that this takes 0.000247059 seconds per match. An 8-hour limit gives Freddo 8 × 60 × 60 = 28, 800 seconds, and hence 8 × 60 × 60/(0.000247059) = 116, 571, 345 matches. When n = 886, the numebr of matches is 116, 310, 536, and for n = 887 it is 116,704,364. So n1 = 886, i.e. Freddo can play a tournament of up to 886 machines. (d) Having despaired of realising his dream of a complete 3-player tournament, Freddo hears of a similar tournament game, known as Krazy Koalas. His friend Choco tells him that he can also run a 100-machine tournament in 42.42 seconds, but the Koala tournament “only” requires n6/(1000000) matches. Given Freddo’s time limit of 8 hours, what is the largest Koala tournament he can run? Show your working. We will call this number n2. Answer: From the previous answer we know that Freddo can run up to 116, 571, 345 matches. When n = 221, we have n6/(1000000) = (221)6/(1000000) = 116, 507, 435, and when n = 222, it is 119, 706, 531. So n2 = 221, i.e. Freddo can play a tournament of up to 221 machines. (e) Freddo, being an optimist, decides he wants to investigate the two types of tournament a little further. Given he knows it takes just under 8 hours to run a Platypus tournament with n1 machines and a Koala tournament of n2 machines, how long will it take to run a Platypus tournament with n2 machines? And how long will it take to run a Koala tournament with n1 machines? Show your working in each case. Answer: A Platypus tournament with n2 = 221 machines will take 1,823,471 matches, which will take 450.5 seconds, i.e. 7.5 minutes. A Koala tournament with n1 = 886 machines will take 483,729,230,338 matches which will take 119, 509, 574.55 seconds, i.e. 3.78 years. (f) Freddo’s activities attract the attention of a spambot (secretly installed on the family desk- top), and gets an unsolicited offer from Hammy Spam Solutions to provide a host server for running his tournaments, at a cost of $(1.01)n for a Platypus tournament of n machines, where n could be as high as 10,000. After a small amount of thought, Freddo deletes the offer 5 and tells all his family and friends to avoid Hammy Spam Solutions at all times. Explain why Freddo did this, with particular reference to the cost for a tournaments involving 100, 1,000 and 10,000 machines. Answer: The cost is exponential, and sooner or later will become far too expensive. Freddo knows he can run a Platypus tournament of 886 machines at no cost (apart from 8 hours on the familiy desktop). Consider the table below.