Year 2 Term 1 Exams Flashcards
formal definition of a DFA
M = (Q, ∑, δ, s, F)
transition function of a DFA
δ : Q x ∑ -> Q
for 2 langauges to be regular, what 4 combinations must be regular
union, intersection, concatenation, kleene star
how do you prove regularity (4 steps)
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
formal definition of an NFA
M = (Q, ∑, Δ, s, F)
transition function of an NFA
Δ : Q x ∑ -> 2^Q
what is non-deterministic acceptance
when an NFA reaches at least one accepting state after processing the entire input
formal definition of an εNFA
M = (Q, ∑, θ, s, F)
transition function of an εNFA
θ : Q x (∑ ∪ {ε}) -> 2^Q
how to convert an εNFA to an NFA (3 steps)
1) remove ε-transitions
2) states with ε-transitions to final states become final
3) new transitions added to preserve language
kleene’s theorem
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
games with the demon - regular langauges
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
why can’t CFLs be recognised by finite automata
they may include nesting or recrusive structures
formal definition of a CFG
G = (N, ∑, P, S)
CFG productions
P : N x (N ∪ ∑)*
what are CFGs used for
specifying syntax of programming langauges
compilers use parsers constructed from CFGs to verify inputs
if an input is of length n, how many variables in a CNF CFG
at most 2^(n+1) - n+1 is the length of each derivation
games with the demon - CFGs
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)
CFL closure
closed under union (2 CFLs)
closed under intersection (CFL & RL)
closed under concatenation (2 CFLs)
not closed under complement
formal definition of a NPDA
M = (Q, ∑, Γ, δ, s, ⊥, F)
transition function of a NPDA
δ : (Q x (∑ ∪ {ε}) x Γ) x (Q x Γ*)
formal definition of a TM
M = (Q, ∑, Γ, ⊢, ⊔, δ, s, t, r)
transition function of a TM
δ : Q x Γ -> Q x Γ x {L,R}
recursively enumerable definition
when a set of strings in equal to the langauge generated by a TM
recursive definition
when a set of strings is recursively enumerable & co-recursively enumerable
relationship between recrusive and recrusively enumerable set
every recursive set is recursively enumerable, but not vice versa
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
decidable definition
a property is decidable if, for any input, you can determine if it has the propety of not
semi-decidable definition
a property is semi-decidable if an algorithm runs indefinitely if the input doesn’t have the property
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
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
HP r and re
not recursive
recursively enumerable
HP^C r and re
not recursive
not recursively enumerable
reduction use
to prove a set is not recursive or recursively enumerable
how to check if 2 DFAs are the same
check if symmetric difference is empty
big-o f and g relation
f(n) < cg(n) for n > n0
small-o f and g relation
as n -> inf, f(n)/g(n) = 0
what is time t(n)
the collection of languages decidable by an O(t(n)) time TM
t(n) time multi-tape TM to single-tape TM time
O(t^2(n))
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
when is a langauge recursively enumerable
when an NTM accepts it
when is a language recursive
when a DTM decides it
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
t(n) time NTM to DTM time
2^(O(t(n)))
difference between time complexity of different DTMs
at most polynomial
difference between time complexity of DTMs & NTMs
exponential
