Theories of computation Flashcards
what is a regexp?
a regular expression defines a language which is a subset of Σ* which is the set of all words (combinations of letters in the alphabet)
if E and F are regexps, what does EF, E|F and E* mean?
EF: a word that is a concatenation of a word that matches E and a word that matches F
E|F: a word that matches either E or F
E* a word that is made of 0 or more words that match E
what is the precedence of juxtaposition (two regexps next to each other), | and *?
highest to lowest:
* , | , justaposition
what is an NFA and DFA?
they are both ways of representing a regexp. they show states that can be accepting or non-accepting to show whether the word is valid or not. a DFA is partial if there isn’t always a state that comes after adding a new letter. NFAs can have multiple paths from a state with the same letter and can also have multiple initial states. all DFAs are NFAs and all NFAs can be converted into DFAs
what is Kleene’s theorem?
every regular language can be converted into a DFA and every DFA can be converted into a regular language
how do you go about proving by course-of-values induction that if a graph is connected, V(G) ≤ E(G) + 1 where V(G) is number of vertices and E(G) is number of edges?
show that it works for a graph with only one vertex and no edges
show that it works by taking away an edge if the result is another connected graph or if it splits into two graphs Gₓ and Gᵧ
how do you convert a natural language to a DFA?
dont need to know
first convert it into a εNFA shown below:
EF: make all ending points of E unstable and point to the start point of F with an ε-edge
E*: make the start point of E point to a new arbitrary state which points to where the start point pointed to and the end points link to the arbitrary state with ε-edges
E|F is just E and F unconnected next to each other
then convert the εNFA into an NFA and then into a DFA
what is a generalised NFA?
an NFA where each arrow might not just represent a letter like a but might represent a regexp like (aa)b*
how to you turn a generalised NFA into a regexp?
if there is no loop on each vertex, add a 0 loop
if there is no arrow from x to y add a 0 arrow
make a start point that connects to the previous initial vertices with an ε-edge and a 0-edge to the others
make an end point and connect every previous end point to it with an ε-edge and every other vertex to it with a 0 arrow
remove each vertex (V) one-by-one by making a new arrow to replace each two arrows that went from x to v to y and then combine the arrows from x to y with an |.
do this until the graph is just a start and end joined with a single arrow and that will be labelled with the regexp.
how do you find the complement of a language?
flip the state of each vertex in the equivalent DFA and convert back
how do you minimise a DFA (remove unnecessary parts)
remove unreachable states (states that have a path from initial state)
remove hopeless states (states that do not have a path to an accepting state)
combine equal states (states that have the same set of words that come off from it) and combine arrows that go to and from the same states.
how do you represent the resulting state of adding the letter a to the state s?
𝛿(s,a)
what does aa* mean in a regexp?
at least one a because a* can be empty
how do you check if two DFAs represent the same language?
make an initial compound state a,b of the two initial states of the DFAs. add arrows for each of the letters (l) in the language to a state with x,y where l takes the first DFA from a to x and the second from b to y. If the state xy already exists, make the arrow point to that. keep doing this until all states have arrows for each letter of the language. They represent the same language if each state is double accept or double reject.
what does it mean for a set to be countably infinite?
when there is a bijection (one to one correspondence) with the infinite set of natural numbers. integers (by ordering them 0, -1, 1, 2, -2 …) and regexps are countable but real numbers and languages are uncountable for example
what is a context free language?
a language that can be defined using Backus-Naur form (A ::= a|b|c) made of a 4-Tuple: (V,Σ,R,S) representing (variables/ non-terminals, terminals, rules, starting variable)
what is a derivation/parse tree?
a tree stemming from the starting variable that branches out to what it transforms into in each stage of the generation of the word using the BNF. the leaves make up the final word
how do you turn a regexp into a CFG?
- Create a variable Rᵢ for each state qᵢ of the DFA.
- Add the rule Rᵢ ::= aRⱼ to the CFG, if δ(qᵢ, a) = qⱼ is a transition in the DFA.
- Add the rule Rᵢ ::= ε, if qᵢ is an accepting state of the DFA.
- Add the rule Rᵢ ::= aRᵢ if there is a loop
- Make R₀ the start variable of the grammar, where q₀ is the start state of the machine.
do questions on course of values induction
watch video on np=p
what is Chomsky Normal Form?
a type of CFG that only allows rules in the form
A ::= BC
A ::= a
S ::= ε (if S is the starting variable)
all non-empty words are derivable in 2n-1 steps where n is the length of the word
how do you convert a CFG into a CNF?
- Introduce a new start symbol (variable) to the grammar.
- Remove all of the ε-rules of the form A ::= ε. and add a clause to all rules that have a clause using A that is the same but without the A
- Remove all of the unit productions of the form A ::= B replacing it with the clauses that
B could turn into. - We may need to patch-up/fix the grammar to make sure that it still produces the original language.
- Convert the remaining rules into proper form.
why is checking if two CFGs have the same set of accepting words an undecidable problem?
because checking if a CFG accepts every word in an alphabet is undecidable because there are infinite words in an alphabet
why are not all languages context-free?
because regexps are countable and regexps are one-to-one with CFGs, CFGs are countable and languages are uncountable. therefore there are non-context-free languages.
what is the formula for:
1→n Σx
0→n-1 Σb^x
0→n Σb^x
n/2 (n+1)
(b^x -1) / (b-1)
(b^[x+1] -1) / (b-1)
why is it useful to know whether a program is polynomial or not?
because anything slower (exponential) means that the program is unsolvable for large values of n
what do the following mean?
f(n) is O(g(n))
f(n) is Ω(g(n))
f(n) is θ(g(n))
- Multiplied by some constant, f(n) is always less that g(n)
- Multiplied by some constant, f(n) is always greater that g(n)
- Multiplied by some constant, f(n) is always less that g(n) and with another constant, is always greater than g(n)
what is a Turing machine?
has finite number of states (some being accepting/ rejecting and one being initial) and has memory in the form of an infinite tape that stores the input at the start. also has a set of valid outputs and an alphabet of characters that can be in the tape including a blank character.
valid operations are write any valid character, read, move left/right, return valid output and no-operation.
what is a macro?
a state in a Turing machine that represents a whole other operation that can be represented with another Turing machine.
what is an auxiliary alphabet and an two-tape Turing machine?
auxiliary alphabet: characters that can’t appear in the input or final state of the tape but can be used mid-way
two-tape TM: a TM with an additional blank tape and the same instructions that can be done to either tape. the additional tape must finish blank
what is a two-dimensional Turing machine?
a TM with a sheet instead of a tape
how do you convert a fancy-TM to a regular TM?
- make a relation of positions of the simple TM and the fancy TM
- convert using a program the fancy input to regular position
- make a macro for each fancy instruction on the simple TM set up and replace the instructions
- give a program to convert the result of simple TM to the fancy TM result
if a program is polynomial in the fancy TM, it will be polynomial in the simple TM
how do you convert a two tape TM to a regular TM?
turn it into a single tape fancy TM first by representing both tapes contents and head positions using auxiliary characters for example using 4 characters for one space. the first is whether the main head is at this position, the second being the main contents, the third being if the aux head is here and the forth being the contents of the aux tape
what is a non deterministic turing machine and a deterministic turing machine?
NDTM: a TM that has different paths to different outputs depending on the input.
DTM: a TM that doesn’t split at any point. only has one path from start to end.
when is an NDTM polytime?
when the machine is guaranteed to terminate in time at most C × n^k with all words under a certain length, regardless of the choices made
what is the language of an NDTM?
the set of all words that are acceptable (may return true when entered into the machine)
what is NP and P?
NP: set of problems solvable in polytime by a NDTM meaning that solutions can be verified in polytime
P: set of problems solvable in polytime by a DTM meaning that solutions can be found in polytime
what are NP-hard problems?
problems that are at least as hard as the hardest problem in NP. These may be in NP themselves (NP-complete) or not. They can be verified to be NP-hard if all NP problems can be reduced to them in polytime.
what is a turing-complete language?
a language that can compute all problems computable on a turing machine
what is church’s thesis?
there is no language that can compute more problems than a turing machine
what is a semi decidable program?
a program that either returns true or runs forever. any decidable program is semi decidable. if a problem and its negation are both semi decidable, the problem is decidable
what is the halting problem?
the problem that checks if a problem is undecidable is undecidable
what is Rice’s theorem?
The problem that determines whether an arbitrary Turing machine has a non-trivial property is undecidable.
what is a non-trivial property
a property that doesn’t holds for some programs and not for others
what is a semantic property
a property may hold for some inputs but not others. for example:
how to convert ε-nfa to nfa:
draw a table with all nodes and what they connect to with a, b , … and ε
group all the nodes that connect either way with a ε
do the table again but with the nodes grouped and if a node points to one item in the group, it points to all items in the group
draw the diagram again from the combined table
how to convert an nfa to a dfa?
how to minimise a dfa?
when is a cfg ambiguous?
when there are multiple parse trees for a single word
what can be done with primitive java?
i=0
i++
i– (until i=o)
if i=0 {M} else {N}
repeat i times {M}
