9: Past Paper Stuff

Question 1

What is co-NP?

Answer 1

The set of problems whose complement is in NP.

Question 2

Why is the collection of Turing-recognisable languages is closed under union?

Answer 2

??

Question 3

How do you determine whether a language is context-free?

Answer 3

??

Question 4

How do you determine if a problem is NP-complete?

Answer 4

Prove that the problem is in NP, and then that any problem in NP can be reduced/transformed to it (in practice only need to show 1 problem can be transformed into it since, in turn, all others must be able to transform into that 1 problem).

Question 5

Prove that if L is a regular language then there is an NFA N with a single accept state such that L ( N ) = L. Fully justify your claim that the languages L ( N ) and L are equal.

Answer 5

??

Question 6

How do you determine if a language can be recognised by a PDA?

Answer 6

??

Question 7

What is Turing-completeness?

Answer 7

A programming language is said to be Turing-complete if we can simulate every Turing machine in it, or equivalently that you can simulate the Universal Turing Machine on it.

Question 8

How do you determine if an algorithm falls within the Master Theorem?

Answer 8

If it is of the general form of 𝑇(𝑛) = 𝑎 ⋅ 𝑇 (𝑛 / 𝑏) 𝑓 (𝑛)

where 𝑎 ≥ 1 and 𝑏 > 1 are constants, and 𝑓 (𝑛) is asymptotically positive

Question 9

How can you use the master Theorem to find the time complexity of an algorithm to which it applies?

Answer 9

??

Question 10

What does it mean for a problem to be decidable, and semi-decidable?

Answer 10

A language L is Turing-decidable if there exists a decider TM, M with L = L(M). A decider TM is one that always halts and never infinitely loops. So, equivalently, a decidable problem is one that has an algorithm to resolve it to a yes/no answer.
A semi-decidable language is one which accepts all inputs of words in the language and either rejects or infinitely loops on input words not in the language. So the difference between semi and fully decidable languages is the absence of guaranteed halting found with fully decidable languages, since TMs running for semi-decidable words may infinitely loop when the input is a word no in the language.

Question 11

How can you determine if a problem is decidable, semi-decidable, or undecidable?

Answer 11

??

Question 12

How can you design a DFA to recognise a specific language?

Answer 12

??

Question 13

How can you convert from a DFA to a regular expression?

Answer 13

??

Question 14

How do you prove a language to be irregular?

Answer 14

??

Question 15

How do you prove a language to be regular?

Answer 15

??

Question 16

How do you convert from a language to a TM?

Answer 16

??

Question 17

What does it mean for a set of languages to be closed under union?

Answer 17

??

Question 18

What is EXPTIME?

Answer 18

The set of decision problems that can be solved by a deterministic Turing machine within exponential asymptotic time.

Question 19

Is the complement of a regular language regular? Why?

Answer 19

??

Question 20

How can you solve a recurrence relation?

Answer 20

??

Question 21

How do you convert from a language to a CFG?

Answer 21

??

Question 22

What is the complement of a language?

Answer 22

For a language X ⊆ Σ* then the complement of X, denoted X̄, is the language of all words in Σ* that are not in X.
So X is the language built from all of the words of the alphabet Σ, and the complement of X, X̄, is the language made of all remaining words in Σ* (all words built from the alphabet Σ) that are not in X.

Question 23

What is Rice’s theorem?

Answer 23

Let P be a nontrivial property of the languages recognised by Turing machines. Then the following language is undecidable:
LP = { | M satisfies P}.
That is, there is no algorithm to decide whether a TM satisfies P.

Question 24

What are the relationships between NP, co-NP, P, NP-complete, PSPACE, and co-NEXP problems?

Answer 24

??

Question 25

How can you determine if it is decidable if an NFA accepts a given language?

Answer 25

??

Question 26

How can you determine if a problem is in NP?

Answer 26

It is in NP if you can provide a certificate allowing the problem to be verified by a nondeterministic TM within polynomial asymptotic time complexity.