Year 2 Term 1 Exams Flashcards

1
Q

formal definition of a DFA

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

transition function of a DFA

A

δ : Q x ∑ -> Q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

union, intersection, concatenation, kleene star

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

how do you prove regularity (4 steps)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

formal definition of an NFA

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

transition function of an NFA

A

Δ : Q x ∑ -> 2^Q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

what is non-deterministic acceptance

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

formal definition of an εNFA

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

transition function of an εNFA

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

kleene’s theorem

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

games with the demon - regular langauges

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

why can’t CFLs be recognised by finite automata

A

they may include nesting or recrusive structures

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

formal definition of a CFG

A

G = (N, ∑, P, S)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

CFG productions

A

P : N x (N ∪ ∑)*

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

what are CFGs used for

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

games with the demon - CFGs

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

CFL closure

A

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

20
Q

formal definition of a NPDA

A

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

21
Q

transition function of a NPDA

A

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

22
Q

formal definition of a TM

A

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

23
Q

transition function of a TM

A

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

24
Q

recursively enumerable definition

A

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

25
recursive definition
when a set of strings is recursively enumerable & co-recursively enumerable
26
relationship between recrusive and recrusively enumerable set
every recursive set is recursively enumerable, but not vice versa
27
how to prove a recursive set
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
28
decidable definition
a property is decidable if, for any input, you can determine if it has the propety of not
29
semi-decidable definition
a property is semi-decidable if an algorithm runs indefinitely if the input doesn't have the property
30
process of a universal TM
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
31
can we prove if a set is recursive
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
32
HP r and re
not recursive recursively enumerable
33
HP^C r and re
not recursive not recursively enumerable
34
reduction use
to prove a set is not recursive or recursively enumerable
35
how to check if 2 DFAs are the same
check if symmetric difference is empty
36
big-o f and g relation
f(n) < cg(n) for n > n0
37
small-o f and g relation
as n -> inf, f(n)/g(n) = 0
38
what is time t(n)
the collection of languages decidable by an O(t(n)) time TM
39
t(n) time multi-tape TM to single-tape TM time
O(t^2(n))
40
how does a single-tape TM simulate a multi-tape TM
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
41
when is a langauge recursively enumerable
when an NTM accepts it
42
when is a language recursive
when a DTM decides it
43
how to convert NTM to DTM
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
44
t(n) time NTM to DTM time
2^(O(t(n)))
45
difference between time complexity of different DTMs
at most polynomial
46
difference between time complexity of DTMs & NTMs
exponential