Year 2 Term 1 Exams

Question 1

formal definition of a DFA

Answer 1

M = (Q, ∑, δ, s, F)

Question 2

transition function of a DFA

Answer 2

δ : Q x ∑ -> Q

Question 3

for 2 langauges to be regular, what 4 combinations must be regular

Answer 3

union, intersection, concatenation, kleene star

Question 4

how do you prove regularity (4 steps)

Answer 4

1) define the langauge
2) construct a DFA
3) show acceptance of strings in the langauge
4) show rejection of strings not in the language

Question 5

formal definition of an NFA

Answer 5

M = (Q, ∑, Δ, s, F)

Question 6

transition function of an NFA

Answer 6

Δ : Q x ∑ -> 2^Q

Question 7

what is non-deterministic acceptance

Answer 7

when an NFA reaches at least one accepting state after processing the entire input

Question 8

formal definition of an εNFA

Answer 8

M = (Q, ∑, θ, s, F)

Question 9

transition function of an εNFA

Answer 9

θ : Q x (∑ ∪ {ε}) -> 2^Q

Question 10

how to convert an εNFA to an NFA (3 steps)

Answer 10

1) remove ε-transitions
2) states with ε-transitions to final states become final
3) new transitions added to preserve language

Question 11

kleene’s theorem

Answer 11

if a is a regexp, then L(a) is a regular language
if L is a regular language, then L = L(a) for some regexp a

Question 12

games with the demon - regular langauges

Answer 12

1) demon picks some k > 0
2) we pick x = _, y = _, z = _, s.t. |y| >= k
3) demon picks u,v,w s.t. y = uvw, v =/ ε
4) we pick i >= 0

Question 13

why can’t CFLs be recognised by finite automata

Answer 13

they may include nesting or recrusive structures

Question 14

formal definition of a CFG

Answer 14

G = (N, ∑, P, S)

Question 15

CFG productions

Answer 15

P : N x (N ∪ ∑)*

Question 16

what are CFGs used for

Answer 16

specifying syntax of programming langauges
compilers use parsers constructed from CFGs to verify inputs

Question 17

if an input is of length n, how many variables in a CNF CFG

Answer 17

at most 2^(n+1) - n+1 is the length of each derivation

Question 18

games with the demon - CFGs

Answer 18

1) demon picks some k > 0
2) we pick z = _
3) demon picks u,v,w,x,y s.t. z = uvwxy, |vx| > 0, |vwx| <= k
4) we pick i >= 0 (and show that, however the demon breaks up z, we can still pump it)

Question 19

CFL closure

Answer 19

closed under union (2 CFLs)
closed under intersection (CFL & RL)
closed under concatenation (2 CFLs)
not closed under complement

Question 20

formal definition of a NPDA

Answer 20

M = (Q, ∑, Γ, δ, s, ⊥, F)

Question 21

transition function of a NPDA

Answer 21

δ : (Q x (∑ ∪ {ε}) x Γ) x (Q x Γ*)

Question 22

formal definition of a TM

Answer 22

M = (Q, ∑, Γ, ⊢, ⊔, δ, s, t, r)

Question 23

transition function of a TM

Answer 23

δ : Q x Γ -> Q x Γ x {L,R}

Question 24

recursively enumerable definition

Answer 24

when a set of strings in equal to the langauge generated by a TM

Question 25

recursive definition

Answer 25

when a set of strings is recursively enumerable & co-recursively enumerable

Question 26

relationship between recrusive and recrusively enumerable set

Answer 26

every recursive set is recursively enumerable, but not vice versa

Question 27

how to prove a recursive set

Answer 27

1) build a TM N that runs M & M’ simultaneously
2) use marks to indicate head positions
3) find head in upper section and perform transition
4) if M accepts, N accepts
5) find head in lower section and perform transition
6) if M’ accepts, N rejects

Question 28

decidable definition

Answer 28

a property is decidable if, for any input, you can determine if it has the propety of not

Question 29

semi-decidable definition

Answer 29

a property is semi-decidable if an algorithm runs indefinitely if the input doesn’t have the property

Question 30

process of a universal TM

Answer 30

1) check M & x are correct encodings
2) simulate M on x
a) partition tape into 3 tracks
i) description of M
ii) content of M’s tape
iii) M’s current state & position
b) look at M’s current state & position
c) read tape content at position
d) read relevant transition
e) perform transition by updating tape, state, and head position
3) accept if M accepts, reject if M rejects

Question 31

can we prove if a set is recursive

Answer 31

no, by using cantor’s diagonalisation, we can see that we introduce new real numbers in 2^N that weren’t included in set N

Question 32

HP r and re

Answer 32

not recursive
recursively enumerable

Question 33

HP^C r and re

Answer 33

not recursive
not recursively enumerable

Question 34

reduction use

Answer 34

to prove a set is not recursive or recursively enumerable

Question 35

how to check if 2 DFAs are the same

Answer 35

check if symmetric difference is empty

Question 36

big-o f and g relation

Answer 36

f(n) < cg(n) for n > n0

Question 37

small-o f and g relation

Answer 37

as n -> inf, f(n)/g(n) = 0

Question 38

what is time t(n)

Answer 38

the collection of languages decidable by an O(t(n)) time TM

Question 39

t(n) time multi-tape TM to single-tape TM time

Answer 39

O(t^2(n))

Question 40

how does a single-tape TM simulate a multi-tape TM

Answer 40

markers identify heads in tracks
input copied into 1st track
for each step:
i) find position of heads
ii) read symbols at heads
iii) update tape content & head positions

Question 41

when is a langauge recursively enumerable

Answer 41

when an NTM accepts it

Question 42

when is a language recursive

Answer 42

when a DTM decides it

Question 43

how to convert NTM to DTM

Answer 43

tape 1: stores the input
tape 2: simulates a branch up to a depth
tape 3: remembers the branch being simulated
tape 4: remembers the branches halted

Question 44

t(n) time NTM to DTM time

Answer 44

2^(O(t(n)))

Question 45

difference between time complexity of different DTMs

Answer 45

at most polynomial

Question 46

difference between time complexity of DTMs & NTMs

Answer 46

exponential