CS21 Decidability and Tractability
Lecture 2 January 5, 2024
Terminology
• finite alphabet Σ : a set of symbols
Copyright By PowCoder代写 加微信 powcoder
• language L ⊆ Σ∗: subset of strings over Σ
• a machine takes an input string and either
– accepts, rejects, or
– loops forever
• a machine recognizes the set of strings
that lead to accept
• a machine decides a language L if it
accepts 𝑥 ∈ 𝐿 and rejects 𝑥 ∉ 𝐿
January 5, 2024 CS21 Lecture 2 2
What is computation?
input machine • reject
• loop forever
• Wewantthesimplestmathematical formalization of computation possible.
• Strategy:
– endow box with a feature of computation
– try to characterize the languages decided
– identify language we “know” real computers can
decide that machine cannot
– add new feature to overcome limits
January 5, 2024 CS21 Lecture 2 3
Finite Automata
• simple model of computation
• reads input from left to right, one symbol at
• maintains state: information about what seen so far (“memory”)
– finite automaton has finite # of states: cannot remember more things for longer inputs
• 2 ways to describe: by diagram, or formally January 5, 2024 CS21 Lecture 2 4
(single) start state
0,1 alphabet Σ = {0,1}
(several) accept states transition for each symbol
FA diagrams
• read input one symbol at a time; follow arrows; accept if end in accept state
January 5, 2024 CS21 Lecture 2 5
FA operation • Example of FA operation:
January 5, 2024
CS21 Lecture 2
input: 01 0 1 not accepted
FA operation • Example of FA operation:
January 5, 2024
What language does this FA decide?
L={x:x∈ 0,1∗,x”=1}
CS21 Lecture 2 7
input: 101 accepted
Example FA
• What language does this FA decide?
L={x:x∈ 0,1 ∗,xhaseven#of1s}
• illustrates fundamental feature/limitation of FA:
– “tiny” memory
– in this example only “remembers” 1 bit of info. January 5, 2024 CS21 Lecture 2 8
Example FA
Σ = {A,B,C}
A,B,C A,B,C
5 10 15 rej
AA BBBBBBB CCBC
January 5, 2024
CS21 Lecture 2
“35 cents”
FA formal definition
A finite automaton is a 5-tuple
(Q, Σ, δ, q0, F)
– Q is a finite set called the states
– Σ is a finite set called the alphabet
– δ:Q x Σ → Q is a function called the transition function
– q0 is an element of Q called the start state – F is a subset of Q called the accept states
January 5, 2024 CS21 Lecture 2 10
FA formal definition
• Specification of this FA in formal terms:
– Q = {even, odd} – Σ = {0,1}
– F = {even}
January 5, 2024
function δ:
δ(even, 0) = even δ(even, 1) = odd δ(odd, 0) = odd δ(odd, 1) = even
CS21 Lecture 2 11
Formal description of FA operation
finite automaton
M = (Q, Σ, δ, q0, F)
accepts a string
w = w1w2w3…wn ∈ Σ*
if ∃ sequence r0,r1,r2,…,rn of states for which –r0 =q0
– δ(ri, wi+1) = ri+1 for i = 0,1,2, …, n-1
January 5, 2024 CS21 Lecture 2 12
• We have a model of computation
(Maybe this is it. Maybe everything we can do
with real computers we can do with FA…)
• try to characterize the languages FAs can recognize
– investigate closure under certain operations
• show that some languages not of this type
January 5, 2024 CS21 Lecture 2 13
Characterizing FA languages
• We will show that the set of languages recognized by FA is closed under:
– union “C = (A ∪ B)”
– concatenation “C = (A ∘ B)” – star “ C = A* ”
• Meaning: if A and B are languages recognized by a FA, then C is a language recognized by a FA
January 5, 2024 CS21 Lecture 2 14
Characterizing FA languages • union“C=(A∪B)”
(A ∪ B) = {x : x ∈ A or x ∈ B or both} • concatenation “C = (A ∘ B)”
(A ∘ B) = {xy : x ∈ A and y ∈ B}
• star“C=A*” (note:εalwaysinA*)
A* = {x1x2x3…xk: k ≥ 0 and each xi ∈A}
January 5, 2024 CS21 Lecture 2 15
Concatenation attempt
(A ∘ B) = {xy : x ∈ A and y ∈ B}
What label do we put on the new transitions?
January 5, 2024 CS21 Lecture 2 16
Concatenation attempt
• Needittohappen“forfree”:labelwithε(?)
• allowsconstructwithmultipletransitionswiththe
same label (!?)
January 5, 2024 CS21 Lecture 2 17
Nondeterministic FA
• We will make life easier by describing an
additional feature (nondeterminism) that helps us to “program” FAs
• We will prove that FAs with this new
feature can be simulated by ordinary FA
– same spirit as programming constructs like procedures
• The concept of nondeterminism has a significant role in TCS and this course.
January 5, 2024 CS21 Lecture 2 18
NFA diagrams (single) start state
• At each step, several choices for next state – if possible to reach accept, then input accepted
January 5, 2024 CS21 Lecture 2 19
transitions:
(several) accept states
• may have several with a given label (or none)
• may be labeled with ε
NFA operation • Example of NFA operation:
alphabet Σ = {0,1}
January 5, 2024
input: 010 not accepted
CS21 Lecture 2
NFA operation • Example of NFA operation:
alphabet Σ = {0,1}
January 5, 2024
input: 110 accepted
CS21 Lecture 2
NFA operation
• One way to think of NFA operation:
• string x = x1x2x3…xn accepted if and only if – there exists a way of inserting εʼs into x
x1εεx2 x3…εxn
– so that there exists a path of transitions from
the start state to an accept state
January 5, 2024 CS21 Lecture 2 22
NFA formal definition
“powerset of Q”: transitions
A nondeterministic FA is a 5-tuplethe set of all labeled with
subsets of Q (Q, Σ, δ, q0a,lpFh)abet
– Q is a finite set called the states
– Σ is a finite set called the alphabet
– δ:Q x (Σ ∪ {ε}) → P(Q) is a function called the
transition function
– q0 is an element of Q called the start state – F is a subset of Q called the accept states
January 5, 2024 CS21 Lecture 2 23
symbols or ε
NFA formal definition
s1 1 s2 0,ε s3 1 s4
• Specification of this NFA in formal terms:
–Q={s1,s2,s3,s4} – Σ = {0,1}
δ(s3, 0) = { } δ(s3, 1) = {s4} δ(s3, ε) = { } δ(s4, 0) = {s4} δ(s4, 1) = {s4} δ(s4, ε) = { }
January 5, 2024
δ(s1, 0) = {s1} δ(s1, 1) = {s1, s2} δ(s1, ε) = { } δ(s2, 0) = {s3} δ(s2, 1) = { }
δ(s2, ε) = {s3}
CS21 Lecture 2
Formal description of NFA operation
NFA M=(Q,Σ,δ,q0,F)
accepts a string w = w1w2w3…wn ∈ Σ∗ if w can be written (by inserting εʼs) as:
y = y1y2y3…ym ∈ (Σ ∪ {ε})*
and ∃ sequence r0,r1,…,rm of states for which
– ri+1 ∈ δ(ri, yi+1) for i = 0,1,2, …, m-1 –rm ∈F
January 5, 2024 CS21 Lecture 2 25
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com