Theory Of Computing

Front 1

Are regular languages closed under complement?

Back 1

Yes

Front 2

Are regular languages closed under union?

Back 2

Yes

Front 3

Regular languages closed under complement?

Back 3

Yes

Front 4

Regular languages closed under concatenation?

Back 4

Yes

Front 5

Regular languages closed under kleene star?

Back 5

Yes

Front 6

Do you remember how to do the product of two automata?

Back 6

Hopefully yes. M3 has states (a,b) where a is a state from M1 and b is a state from M2 for all combinations. So M3 = run M1 and M2 in parallel.

Front 7

Is the empty set regular?

Back 7

Yes

Front 8

Is the set of all strings regular? (Sum symbol stared)

Back 8

Yes

Front 9

Do you remember how to do subset construction? NFA to DFA?

Back 9

Hopefully yes.

Front 10

Epsilon NFA to regular NFA how is delta' redefined?

Back 10

Delta'(q,inp) = {q'|q(=>epsilon)(=>inp)q'}

Or transition state given input goes to any state where there is transition via that input (and epsilon) from given state to that new state.

Front 11

Epsilon NFA to regular how is F' redefined?

Back 11

F' = {q|exists: f in F and q(=>epsilon)f}

Final states are states already in F and states with a epsilon transition from them to a state in F

Front 12

What is kleene's theorem

Back 12

If a is a reg expression the L(a) is a regular language. If L is a regular languages then L=L(a) for some regex a.

Front 13

Do you remember how to make an automata for the union of two languages?

Back 13

Have a new start state with an epsilon transition to the start state of each language.

Front 14

Do you remember how to make an automata for the concatenation of two languages?

Back 14

If both are NFAs. Add an epsilon transition from M1s final states to M2s start state.

Or use Kleene's and turn them into regex

Front 15

Do you remember how to make an automata for kleene start of a language?

Back 15

Add a new state which accepts and is the start state. Add an epsilon transition from this to the original start state and also epsilon transitions from all original accept states to this state.

Front 16

Go an revise the automata to regex inductive process

Back 16

It's confusing

Front 17

Do you remember how to go from an epsilon NFA to a regular NFA? (General process)

Back 17

Make states with epsilon transitions to final states final.

Add new transitions where you can go somewhere with one input and any number of epsilon.

Front 18

How do you easily prove that not all strings are regular?

Back 18

With counting. There is countably many regular expressions over a language but uncountably many languages over the language.

Aka countably many strings but uncountably many sets of strings.

Front 19

Go practice the pumping lemma more

Back 19

You know you need to

Front 20

All finite languages are...

Back 20

Regular

Front 21

Easy way to prove a finite language is regular?

Back 21

Suppose L ={x1,....,xl} is a finite set of strings accepted by the language. Give the regular expression x1 + ... + xl that matches up with this set. Kleene's theorem states regular expressions define regular languages so having a regex for the language means it is regular.

Front 22

Time complexity of a Turing machine?

Back 22

The number of steps

Front 23

Space complexity on a Turing machine

Back 23

Amount of additional memory required, measured in cells on the tape

Front 24

Define a decision problem

Back 24

A problem where the answer is either yes or no

Front 25

Define asymptotic upper bound (big O)

Back 25

F(n) <= cg(n) for all n>=n0

Where c>0, n0>0

Front 26

Define strict asymptotic upper bound (small o)

Back 26

Lim n->infinity f(n)/g(n) = 0

So root n is strict o(n)

But (n-1)^2 is not strict o(n^2) even though it is O(n^2)

Front 27

Multi to single tape Turing machine what happens to time complexity

Back 27

Multi tape is t(n)

Then single tape is O(t^2(n))

Front 28

Multi to single tape Turing machine steps and why the time complexity changes the way it does

Back 28

K tape machine to single tape machine M'

Tape of M' structured into racks

Special markers on M' to mark tape heads

A single step of M requires:

Find positions of heads and read

Update tape content and head pos

M has at most t(n) steps

Running each step takes O(t(n)) time

So overall t(n) * O(t(n)) = O(t^2(n)) steps.

Note copying down take O(n) so is negligible

Front 29

Describe how to make a DTM from a NTM

Back 29

The deterministic machine checks all branches of the NTM breadth first. If it reaches a reject state it stops that branch and tries the next. If find accept, accept. If not will loop.

It has one tape for the input (Input tape)

One tape to simulate a branch up to a given depth (simulation tape)

And one tape to remember the branch being simulated. (Adress tape)

Front 30

What is the defenition of recursively enumerable

Back 30

A language is rec en if and only if some Non-deterministic TM accepts it

Front 31

Do all NTMs have equivalent DTMs

Back 31

Yes.

Front 32

How to modify a DTM made from a NTM so that it halts if all branches of N halt on the input

Back 32

Remember branches that halt on a 4th tape

Do not explore those branches again

If no branches left, reject.

With this method if N is a decider, the new machine is Total

Front 33

What is the defenition of a recursive language

Back 33

A language is recursive if and only if some non deterministic TM decides it

Front 34

What happens to time complexity when moving from a NTM to a DTM

Back 34

If the NTM runs in t(n) the DTM runs in 2^(O(t(n))) two to the big O t(n)

Front 35

How do you know the time complexity of a DTM made from a NTM

Back 35

1) how many branches will it need to simulate

2) how much time to simulate one branch

Each branch is at most length t(n)

Each node has at most b children

Hence b^(t(n)) leaves and O(b^(t(n))) nodes/ partial branches.

Multiply these: t(n) * b^(t(n))

Which is 2^(O(t(n)))

Front 36

What is the time complexity of a DTM made from a O(n) NTM

Back 36

2^O(n)

Front 37

Define P

Back 37

The class of languages which can be decided by a deterministic single tape Turing machine in polynomial time

Front 38

What is the church Turing thesis

Back 38

Any machine in a Turing complete computational model can be emulated by a machine in any other Turing complete computational model

Front 39

What is the strong church Turing hypothesis

Back 39

The basic operations of the first model can be emulated with a polynomial number of operations of the second model

Front 40

Algorithms vs Turing machines. Uh its that example of the church Turing stuff idk

Back 40

Copying a string of length n

Takes O(n) on a random access machine

Takes O(n^2) on a Turing machine

Key observation: copying the string on a RAM model can be emulated in polynomial time on a TM

Front 41

Define the PATH problem

Back 41

Given a directed graph does there exist a directed path connecting two given nodes

Front 42

Define HAMPATH problem

Back 42

Given a directed graph does there exist a directed path connecting two given nodes that goes through each node exactly once.

Front 43

Give the steps for polynomial time PATH

Back 43

On input G,s,t

1) place a mark on node s

2) repeat 3 until no additional nodes are marked

3) scab all edges of G. For each edge (a,b) if a is marked then mark b

4) If t is marked then accept otherwise reject.

Front 44

What is the time complexity of the HAMPATH verifier

Back 44

Polynomial

Front 45

Every language in P is...

Back 45

Recursive

Front 46

Every regular language is in...

Back 46

P

Front 47

Every context free language is...

Back 47

In P.

There is a proof for this learn if you have time?

Front 48

The problem RELPRIME is in... based on...

Back 48

P based on length of the encoding of the input

Front 49

Define a verifier (maths like)

Back 49

L = {w | V accepts (w,c) for some string c}

If V accepts w,c then c is called certificate of w in L

Front 50

Describe the algorithm for HAMPATH verifier

Back 50

1. Check for repetitions in the list of nodes in the candidate solution (c)

2. Check if the first node in c is the start and the last is the end

3. For each node check there is an edge connecting it and the next one

Front 51

Define the class NP

Back 51

Languages that have polynomial time verifiers e.g. HAMPATH

Or languages that can be decided by non deterministic Turing machines in polynomial time

Front 52

Non deterministic HAMPATH

Back 52

Use the verifier algorithm except instead of the candidate solution use non deterministicly chosen set of nodes

Front 53

Define NTIME

Back 53

All languages that can be decided by an O(t(n)) time non deterministic Turing machine

Front 54

Algorithm for SAT with a NTM

Back 54

Non deterministically choose values 0/1 for all variables

Evaluate using those values

If true accept otherwise reject

Front 55

Define the TSP(D) problem

Back 55

Travelling salesperson decision version: given a number D and n cities with given distances between them. Is there a circular route that visits each city exactly once with total distance of at most D

Front 56

What group is TSPD in

Back 56

NP

Front 57

What group is 3COL in

Back 57

NP

Front 58

Is HAMPATH NP complete

Back 58

Yes