联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp2

您当前位置:首页 >> Algorithm 算法作业Algorithm 算法作业

日期:2021-10-25 09:19

Computing Theory

COSC 1107/1105

Sample Exercise 2 Answers

1 Assessment details

1. Consider the grammar derivations below.

(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))Rorw(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 → xC | xD

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.

Machines Cost ($s)

100 2.70

1,000 20,959.16

2,000 439286205.05

3,000 9207067941189.81

4,000 192972369947324000.00

5,000 4044537935523770000000.00

6,000 84770100073685200000000000.00

7,000 1776709720877430000000000000000.00

8,000 37238335563086900000000000000000000.00

9,000 780484070759879000000000000000000000000.00

10,000 163,58,287,111,890,900,000,000,000,000,000,000,000,000,000.00

Enough said!

4. (a) Construct a Turing machine M1 which recognises your student number. This machine should

accept only your student number; it should reject any string of length 6 or less, and any

string of length 8 or more. The only string of length 7 which it should accept is your student

number.

Answer: We will assume your student number is 7654321. A Turing machine which

recognises this is below. There are others of course, but note that this machine rejects any

string of length 6 or less, as well as rejecting any string of lenth 8 or more.

(b) Which of the following machines could also be used to recognise your student number, as

above? Briefly justify each of your answers.

A non-deterministic PDA

A deterministic PDA

A non-deterministic finite state automaton (NFA)

A deterministic finite state automaton (DFA)

A linear-bounded automaton

Answer: All of these can be used to recognise your student number. There is no memory

required, and it is simple to write a DFA for it. This means that all other types of automata

can be used as well.

6

(c) Consider the following machine M2, where q2 is the first state of your machine M1 above (so

the states q0 and q1 below are added to your M1, with machine constructed this way starting

in q0).

Explain why M2 on input xxxxxxx will always eventually terminate with success, no matter

what your student number is.

Answer: This machine nondeterministically replaces every x on the input tape with one

of the digits 0-9. Given the input of xxxxxx to the machine, this has the effect of guessing

a 7-digit number, no matter what that number is.

(d) Given an input of xn (i.e. n consecutive x’s), calculate the maximum time it will take M2

to terminate, assuming that it can process 1 transition from the above machine in 3× 10?5

seconds. Show your working and explain your reasoning.

Show your answers for n = 7, 10, 15 and 20 in the table below. Use the most appropriate

units of time in each case.


n Transitions Time

Answer: As the deterministic execution of M2 may take up to n× 10n transitions to guess

the correct n-digit number, the maximum time for it to terminate will be n×10n×3×10?5 =

3n× 10n?5 seconds. Note that each number takes n transitions.

n Transitions Time

7 70,000,000 2100s = 35 minutes

10 1011 34.7 days

15 1.5× 1016 14,259 years

20 2× 1021 1,901,285,269 years

5. (a) Construct a Turing machine which given a seven-digit number as input, deletes the first

digit (whatever it is) and replaces the remaining six digits with their value modulo 3 (i.e. the

remainder when divided by 3, or if x is a digit, the value of x mod 3). For example, given the

input 7654321, the machine write a blank over the 7, and leave the string 021021 on the tape

after terminating. The machine must terminate on all strings over {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}?

(including the empty string), and only halt in an accepting state if the string has exactly 7

digits.

Answer: One such machine is below.

(b) Construct a Turing machine M3 which takes a string of digits over {0, 1, 2} with length at

least 3 as input, and halts in an accepting state with w#wR on the tape, where w is the

input string and wR is the reverse of the string w. If the input string w is of length 2 or less,

the machine must halt in a non-accepting state and leave w on the tape. This means that

the machine must halt on all inputs. Some example inputs and outputs are below.

Input Output Halt state

1211 1211#1121 accepting

22001 22001#10022 accepting

1 1 non-accepting

20 20 non-accepting


相关文章

版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp