Theories of computation

Question 1

what is a regexp?

Answer 1

a regular expression defines a language which is a subset of Σ* which is the set of all words (combinations of letters in the alphabet)

Question 2

if E and F are regexps, what does EF, E|F and E* mean?

Answer 2

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

Question 3

what is the precedence of juxtaposition (two regexps next to each other), | and *?

Answer 3

highest to lowest:
* , | , justaposition

Question 4

what is an NFA and DFA?

Answer 4

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

Question 5

what is Kleene’s theorem?

Answer 5

every regular language can be converted into a DFA and every DFA can be converted into a regular language

Question 6

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?

Answer 6

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ᵧ

Question 7

how do you convert a natural language to a DFA?
dont need to know

Answer 7

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

Question 8

what is a generalised NFA?

Answer 8

an NFA where each arrow might not just represent a letter like a but might represent a regexp like (aa)b*

Question 9

how to you turn a generalised NFA into a regexp?

Answer 9

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.

Question 10

how do you find the complement of a language?

Answer 10

flip the state of each vertex in the equivalent DFA and convert back

Question 11

how do you minimise a DFA (remove unnecessary parts)

Answer 11

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.

Question 12

how do you represent the resulting state of adding the letter a to the state s?

Answer 12

𝛿(s,a)

Question 13

what does aa* mean in a regexp?

Answer 13

at least one a because a* can be empty

Question 14

how do you check if two DFAs represent the same language?

Answer 14

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.

Question 15

what does it mean for a set to be countably infinite?

Answer 15

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

Question 16

what is a context free language?

Answer 16

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)

Question 17

what is a derivation/parse tree?

Answer 17

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

Question 18

how do you turn a regexp into a CFG?

Answer 18

1. Create a variable Rᵢ for each state qᵢ of the DFA.
2. Add the rule Rᵢ ::= aRⱼ to the CFG, if δ(qᵢ, a) = qⱼ is a transition in the DFA.
3. Add the rule Rᵢ ::= ε, if qᵢ is an accepting state of the DFA.
4. Add the rule Rᵢ ::= aRᵢ if there is a loop
5. Make R₀ the start variable of the grammar, where q₀ is the start state of the machine.

Question 19

do questions on course of values induction
watch video on np=p

Question 20

what is Chomsky Normal Form?

Answer 20

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

Question 21

how do you convert a CFG into a CNF?

Answer 21

1. Introduce a new start symbol (variable) to the grammar.
2. 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
3. Remove all of the unit productions of the form A ::= B replacing it with the clauses that
   B could turn into.
4. We may need to patch-up/fix the grammar to make sure that it still produces the original language.
5. Convert the remaining rules into proper form.

Question 22

why is checking if two CFGs have the same set of accepting words an undecidable problem?

Answer 22

because checking if a CFG accepts every word in an alphabet is undecidable because there are infinite words in an alphabet

Question 23

why are not all languages context-free?

Answer 23

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.

Question 24

what is the formula for:
1→n Σx
0→n-1 Σb^x
0→n Σb^x

Answer 24

n/2 (n+1)
(b^x -1) / (b-1)
(b^[x+1] -1) / (b-1)

Question 25

why is it useful to know whether a program is polynomial or not?

Answer 25

because anything slower (exponential) means that the program is unsolvable for large values of n

Question 26

what do the following mean?
f(n) is O(g(n))
f(n) is Ω(g(n))
f(n) is θ(g(n))

Answer 26

1. Multiplied by some constant, f(n) is always less that g(n)
2. Multiplied by some constant, f(n) is always greater that g(n)
3. Multiplied by some constant, f(n) is always less that g(n) and with another constant, is always greater than g(n)

Question 27

what is a Turing machine?

Answer 27

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.

Question 28

what is a macro?

Answer 28

a state in a Turing machine that represents a whole other operation that can be represented with another Turing machine.

Question 29

what is an auxiliary alphabet and an two-tape Turing machine?

Answer 29

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

Question 30

what is a two-dimensional Turing machine?

Answer 30

a TM with a sheet instead of a tape

Question 31

how do you convert a fancy-TM to a regular TM?

Answer 31

1. make a relation of positions of the simple TM and the fancy TM
2. convert using a program the fancy input to regular position
3. make a macro for each fancy instruction on the simple TM set up and replace the instructions
4. 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

Question 32

how do you convert a two tape TM to a regular TM?

Answer 32

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

Question 33

what is a non deterministic turing machine and a deterministic turing machine?

Answer 33

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.

Question 34

when is an NDTM polytime?

Answer 34

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

Question 35

what is the language of an NDTM?

Answer 35

the set of all words that are acceptable (may return true when entered into the machine)

Question 36

what is NP and P?

Answer 36

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

Question 37

what are NP-hard problems?

Answer 37

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.

Question 38

what is a turing-complete language?

Answer 38

a language that can compute all problems computable on a turing machine

Question 39

what is church’s thesis?

Answer 39

there is no language that can compute more problems than a turing machine

Question 40

what is a semi decidable program?

Answer 40

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

Question 41

what is the halting problem?

Answer 41

the problem that checks if a problem is undecidable is undecidable

Question 42

what is Rice’s theorem?

Answer 42

The problem that determines whether an arbitrary Turing machine has a non-trivial property is undecidable.

Question 43

what is a non-trivial property

Answer 43

a property that doesn’t holds for some programs and not for others

Question 44

what is a semantic property

Answer 44

a property may hold for some inputs but not others. for example:

Question 45

how to convert ε-nfa to nfa:

Answer 45

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

Question 46

how to convert an nfa to a dfa?

Question 47

how to minimise a dfa?

Question 48

when is a cfg ambiguous?

Answer 48

when there are multiple parse trees for a single word

Question 49

what can be done with primitive java?

Answer 49

i=0
i++
i– (until i=o)
if i=0 {M} else {N}
repeat i times {M}