8: Tutorial Stuff Flashcards
How do you find the time complexities of an algorithm?
??
How do you show if a language is decidable?
Show there is a decider TM that accepts it.
How do you convert a language to an NFA?
??
How do you convert from a language to a regular expression?
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.
What is Kleene’s theorem?
A language is described by a regular expression if and only if there is a DFA which defines it.
What is the proof of Kleene’s theorem?
??
How can you use Kleene’s theorem to convert from automata to regular expressions (of the languages they accept)?
??
How can you use Kleene’s theorem to convert from languages to automata?
??
How do you prove if a language is regular?
Find a regular expression to express it to show it to be regular, or use the pumping lemma to show it isn’t.
How do you show whether a language is context-free?
??
What are derivations of CFGs?
??
How do you find CFG derivations?
??
How can you tell if the Master Theorem applies to an algorithm?
If it is of the general form of 𝑇(𝑛) = 𝑎 ⋅ 𝑇 (𝑛 / 𝑏) 𝑓 (𝑛)
Where 𝑎 ≥ 1 and 𝑏 > 1 are constants, and 𝑓 (𝑛) is asymptotically positive.
How do you convert from a CFG to a PDA?
??
How do you convert from a language to a TM?
??
How do you prove a TM is a decider?
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.
How do you encode a DFA and its input words?
??
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).
??
What is Rice’s theorem?
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.
How do you prove a language is in P?
??
How can you use the Master Theorem to find a Θ(n) bound for the growth rate of an algorithm to which it applies?
??
How do you show a graph is in P?
??
What does it mean for a set of algorithms to be closed?
A set is closed under an operation if the operation returns a member of the set when evaluated on members of the set.
What does PSPACE mean?
PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of asymptotic space.
What does PSPACE-hard mean?
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.
How do you find a reduction between 2 algorithms?
??
