8: Tutorial Stuff

Question 1

How do you find the time complexities of an algorithm?

Answer 1

??

Question 2

How do you show if a language is decidable?

Answer 2

Show there is a decider TM that accepts it.

Question 3

How do you convert a language to an NFA?

Answer 3

??

Question 4

How do you convert from a language to a regular expression?

Answer 4

By breaking down the parts of each word into atomic subsections before notating them as a regular expression. Note only regular languages can be converted into regular expressions.

Question 5

What is Kleene’s theorem?

Answer 5

A language is described by a regular expression if and only if there is a DFA which defines it.

Question 6

What is the proof of Kleene’s theorem?

Answer 6

??

Question 7

How can you use Kleene’s theorem to convert from automata to regular expressions (of the languages they accept)?

Answer 7

??

Question 8

How can you use Kleene’s theorem to convert from languages to automata?

Answer 8

??

Question 9

How do you prove if a language is regular?

Answer 9

Find a regular expression to express it to show it to be regular, or use the pumping lemma to show it isn’t.

Question 10

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

Answer 10

??

Question 11

What are derivations of CFGs?

Answer 11

??

Question 12

How do you find CFG derivations?

Answer 12

??

Question 13

How can you tell if the Master Theorem applies to an algorithm?

Answer 13

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

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

Question 14

How do you convert from a CFG to a PDA?

Answer 14

??

Question 15

How do you convert from a language to a TM?

Answer 15

??

Question 16

How do you prove a TM is a decider?

Answer 16

Show it halts within finite time; consider how it will iterate over its tape/s for different possible inputs and consider if there could ever be a condition in which it will loop repeatedly, at some point returning to the same state, tape contents, and tape head position. If not, it is a decider.

Question 17

How do you encode a DFA and its input words?

Answer 17

??

Question 18

Prove that given two DFAs, A and B, there exists a length N such that if A and B accept the same strings up to length N then L(A) = L(B).

Answer 18

??

Question 19

What is Rice’s theorem?

Answer 19

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 20

How do you prove a language is in P?

Answer 20

??

Question 21

How can you use the Master Theorem to find a Θ(n) bound for the growth rate of an algorithm to which it applies?

Answer 21

??

Question 22

How do you show a graph is in P?

Answer 22

??

Question 23

What does it mean for a set of algorithms to be closed?

Answer 23

A set is closed under an operation if the operation returns a member of the set when evaluated on members of the set.

Question 24

What does PSPACE mean?

Answer 24

PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of asymptotic space.

Question 25

What does PSPACE-hard mean?

Answer 25

A problem is PSPACE-hard if it has a reduction in polynomial time from every problem in PSPACE to the problem. This means that if we can solve the problem, then we can solve any other problem in PSPACE.

Question 26

How do you find a reduction between 2 algorithms?

Answer 26

??