8: Tutorial Stuff

Question 1

How do you convert an NFA to a DFA?

Answer 1

To make a DFA M from an NFA N = (A, S, F, s0, T). The alphabet of M is A.

1. Begin with a new start state S0 labelled by {s0} ∪ {s : there exists a path labelled only by ϵ-arrows from s0 to s}.
2. For each newly constructed state Si, and for each a ∈ A:
   (a) For each s ∈ Si, find all states s’ that can be reached from s by reading (ϵ ^ i)a(ϵ ^ j) (for any i and j).
   (b) Let Sj be the set of all of these states s’. (The set Sj may be the empty
   set ∅) Put an arrow labelled a from Si to Sj .
3. Repeat Step 2 until every new state Si has one arrow leaving it for each letter a ∈ A.
4. Make each state Si that contains at least one state from T into an accept state for M.

Question 2

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

Answer 2

You can just define the language as being equal to the regular expression, e.g. L((a + b* + ϵ)(c + d)) or L2 = 010.

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 convert from a language to a PDA?

Answer 10

??

Question 11

What are derivations of CFGs?

Answer 11

??

Question 12

How do you find CFG derivations?

Answer 12

??

Question 13

How do you convert from languages to CFGs?

Answer 13

??

Question 14

How do you convert from a CFG to a PDA?

Answer 14

??

Question 15

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

Answer 15

??

Question 16

How do you convert from a language to a TM?

Answer 16

??

Question 17

How do you prove a TM is a decider?

Answer 17

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 18

How do you encode a DFA and its input words?

Answer 18

??

Question 19

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 19

??

Question 20

How do you show if a language is decidable?

Answer 20

Show there is a decider TM that accepts it.

Question 21

What is Rice’s theorem?

Answer 21

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 22

How do you prove a language is in P?

Answer 22

??

Question 23

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

Answer 23

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

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

Question 24

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

Answer 24

??

Question 25

How do you find the time complexities of an algorithm?

Answer 25

??

Question 26

How do you show a graph is in P?

Answer 26

??

Question 27

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

Answer 27

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

Question 28

What does PSPACE mean?

Answer 28

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

Question 29

What does PSPACE-hard mean?

Answer 29

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 30

How do you find a reduction between 2 algorithms?

Answer 30

??