FINAL REVIEW
RegularLanguages
PEF Q ot states regular if a DFA M St M A
alphapet Ʃ the problemencoded bylang A can
initial state be solved by a DFA
subset F of acceptingstates
transitionfunction 8 Qx Ʃ Q
LCM set of strings w
that M accepts
Distinguishable LowerBound on States
twostrings U v are distinguishable wrt A find a set of k pairwisedistinguishablestrings
if there is string w st only one of K number of states
V W and v w is in A
then 8 90 0
8 190 V
NFA Determinization NFA DFA
generalization of DFA convertanyNFA into DFA
transitionfunction Δ Qx
Ʃ 29 input a b
mapsto a set of states 903
acceptsstring if at
least one 5
execution leads to accepting state
acceptonlyregularlanguages can have exponentialblow up in size
E NFAstate can change w oinput
RegularLanguages RegularExpressions
operations on RegularLanguages
A is regular if
closedunderoperation theresult of
the operation is regular if both languages
are regular
2,8T 5ththat I
3 E NFAM suchthat L M A
prove construct DFA M such that 4 regex r such that h r A
LCM A operation A2
regexoperators
closedunder intersection union romp 1 o or morerepetitions
use productconstruction Q Q Q2 Feltre 2 concert
3 U union
ProvingNon regularity
prove no DFA can accept provenofinite
number of statessufficeto acceptA
supposeinfiniteset of pairwise dist strings with
assumeA is regular K pairwise dist strings
and k numberof strings number of states
is cannot be infinite contradiction
TM Hatting Decidable
finite set of States Q w go go 9r if for every input w TM M is finite term
tapealphabet F w blank symbol_ guaranteed to not enter finite loops
input alphabet Ʃ decidablelanguage A if there ishaltingTM
transitionfunction 8 Q t Q xp yp A hats on9 a 9r
such that L M
Sgo g 8 L R decidable solvable
tangentingghete
trite Trovent goin everyregularlanguage is decidable
ClosureProperties
NTM decidablelanguages are closed under
transition function Δ Qxt 2 ext x L R intersection union comp
Visualize as execution tree either so or 8 prove there existshaltingTM st
doesnot change decidability M accepts inputwhen both M and Ma do
simulate M and Mz
simulatingNTMby PTM causes exponentia
slowdown
Problems DFAS
membership ADFA CM WS M is a DFA and M accepts w 9th w
decidable
1 checkif inputM encodes a DFA
2 exelute M on w and check ifaccepts
emptiness Epf 4M M is a DFA and LCM is empty
decidable
equivalence EQ p M M's M and M are DFAs and LCM 2114
decidable
checkif LCM Arlen empty and
M n LCM empty
take product with negation
Problems Turing Machines
ATM caws M is a TMand M accepts w
needto simulate M on w w universal TM U
if M doesnot halt on w then U does not halt
is decidable
cannotconclude U is halting cannotconclude Any
HALT µ MW I M is aTM and Mhalts on w
undecidable
when M is aTM there is noknownbound on howmanysteps the executionneeds
ATM Erm EQTM HALTTM
all undecidable
Recognizable classify a Problem
if there is TM M St LCM A decidable find haltingTM for it
TM can check if input is [Link] recognizable find TM that acceptsit
maynot terminate
closed under union
M may not terminate ProblemReduction
fix simulate parallelism by alternatingsteps undecidable show
on the two tapes Atmreducesto it
constructTMfor
Theorem if A and NA are is decidable
Attyusing
recognizable Problemmy as subroutine
decidable recognizable
ATM Mins M accepts w
I It s Interightaberdecidable _GivenMin construct in stm
exactlywhen
4 Ep Mx
Classp class up Unrecognizable proof by contrad
show nA to be recognizable
if 1 M decidesA LCM A it NTMaccepts A then both are decidable
2 timecomplexity is o nk in poly time
solvable in poly time if deterministicV st
wis in A iff V accepts CW CS
nondeterministic can guesspossible executions
Boolean Formulas
NP complete CONP
Yoshikiheteres i n D Aisin ND iff nA is in NP
truthassignmentp p Oort 2 A is NP hard B pA B in NP
valid hard UNSAT
SAT 4 63 is satisfiable 1 SAThard INVALID
in NP INVALID in NP
show polytimereduction
CNF AND of clauses ORs
30nF each clause has only 3 literals [Link] ffffltibPutw
ClassPSPACE class NPSPACE NPSPACE PSPACE
if TM M acceptsA acceptedbynondeterministicTM ofspaceO nk
spacetomplexity is o nk prove deterministic non polyspace algo
use guesses and LBR vertex gagr
p PSPACE
QBF Booleanformulas w quantifiers LengthBoundedReachability
TQBF is NP hard PSPACE iomplete is there path set of length K
Recursion LBR S V K 2 and LBR V t K 2
Markovchain foreachsubset T of Q
if T doesnot contain anystate in F 19a
M Q Do T thenif LBR 90 T 2n 1 then reject
TransitionmatrixTfgq probabilityq79 spacecomplexity O na
Markovianprocess Xo Xi X2 if
t dependsonly on Xt 1
Marginalprobability Dtime state
BE it
Transient Recurrent SCCs
willbeabandoned will return every pair u v and usu
allstatesnot in P Xt 9 Xo g 1 maximal
BSCC BottomSCC BSC novertex in U hasoutgoingedge
iff belongstoBSOC
in 1 SCCeitherallrecurrent property everyvertexbelongsto 1 80
or all transient
Reducible
Irreducible Periodicity
possibletimeswhen the process is again in
otherwise hasonly1 SCC state with positiveprobability
if irreducible all period GCD of visit timesV19
statesare recurrent
aperiodic period 1 self loop
sameSCC same period
SteadyStateDistribution LimitingDistribution
if Ds T Ds
Diim116 D1D2
focuson irreducible 1 SCLMC
steadystatedistr is unique maynotalwaysexist in periodicirreducible MC
Ds di dads irreducible exists and unique
diedTat aperiodicand irreducible exists and equals Ds
data Anthi