8: Tutorial Stuff Flashcards
How do you convert an NFA to a DFA?
To make a DFA M from an NFA N = (A, S, F, s0, T). The alphabet of M is A.
- Begin with a new start state S0 labelled by {s0} ∪ {s : there exists a path labelled only by ϵ-arrows from s0 to s}.
- 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 . - Repeat Step 2 until every new state Si has one arrow leaving it for each letter a ∈ A.
- Make each state Si that contains at least one state from T into an accept state for M.
How do you convert from a regular expression to a language?
You can just define the language as being equal to the regular expression, e.g. L((a + b* + ϵ)(c + d)) or L2 = 010.
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 convert from a language to a PDA?
??
What are derivations of CFGs?
??
How do you find CFG derivations?
??
How do you convert from languages to CFGs?
??
How do you convert from a CFG to a PDA?
??
How do you show whether a language is context-free?
??
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).
??
How do you show if a language is decidable?
Show there is a decider TM that accepts it.
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 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 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 find the time complexities of an algorithm?
??
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?
??
