CS21 Decidability and Tractability
Lecture 3 January 8, 2024
NFA diagrams (single) start state
• At each step, several choices for next state – if possible to reach accept, then input accepted
Copyright By PowCoder代写 加微信 powcoder
January 8, 2024 CS21 Lecture 3 2
transitions:
(several) accept states
• may have several with a given label (or none)
• may be labeled with ε
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 8, 2024 CS21 Lecture 3 3
symbols or ε
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 8, 2024 CS21 Lecture 3 4
• Recall: want to show the set of languages
recognized by NFA is closed under: – union “C = (A ∪ B)”
– concatenation “C = (A ∘ B)”
– star “ C = A* ”
January 8, 2024 CS21 Lecture 3 5
January 8, 2024
Closure under union
C = (A ∪ B) = {x : x ∈ A or x ∈ B} ε
CS21 Lecture 3 6
Closure under concatenation
C = (A ∘ B) = {xy : x ∈ A and y ∈ B}
January 8, 2024
CS21 Lecture 3 7
January 8, 2024
CS21 Lecture 3
Closure under star
C=A*={x1x2x3…xk:k≥0andeachxi ∈A} C
NFA, FA equivalence Theorem: a language L is recognized by a
FA if and only if L is recognized by a NFA.
Must prove two directions:
(⇒) L is recognized by a FA implies L is
recognized by a NFA.
(⇐) L is recognized by a NFA implies L is
recognized by a FA.
(usually one is easy, the other more difficult)
January 8, 2024 CS21 Lecture 3 9
NFA, FA equivalence
(⇒) L is recognized by a FA implies L is recognized by a NFA
Proof: a finite automaton is a nondeterministic finite automaton that happens to have no ε-transitions, and for which each state has exactly one outgoing transition for each symbol.
January 8, 2024 CS21 Lecture 3 10
NFA, FA equivalence
(⇐) L is recognized by a NFA implies L is recognized by a FA.
Proof: we will build a FA that simulates the NFA (and thus recognizes the same language).
– alphabet will be the same
– what are the states of the FA?
January 8, 2024 CS21 Lecture 3 11
NFA, FA equivalence
– given NFA M = (Q, Σ, δ, q0, F)
– construct FA Mʼ = (Qʼ, Σʼ, δʼ, q0ʼ, Fʼ)
– same alphabet: Σʼ = Σ
– states are subsets of Mʼs states: Qʼ = P (Q)
– if we are in state R ∈ Qʼ and we read symbol a ∈ Σʼ, what is the new state?
January 8, 2024 CS21 Lecture 3 12
NFA, FA equivalence
1 0,ε 1 0,1
– given NFA
– construct FA
M = (Q, Σ, δ, q0, F)
Mʼ = (Qʼ, Σʼ, δʼ, q0ʼ, Fʼ)
δʼ(R, a) = ∪!∈# E(δ(r, a))
Helpful defʼn: E(S) = {q ∈ Q : q reachable from S by traveling along 0 or more ε-transitions}
– new transition fn:
= “all nodes reachable from R by following an
a-transition, and then 0 or more ε-transitions” January 8, 2024 CS21 Lecture 3 13
NFA, FA equivalence
– given NFA M = (Q, Σ, δ, q0, F)
– construct FA Mʼ = (Qʼ, Σʼ, δʼ, q0ʼ, Fʼ)
– new start state: q0ʼ = E({q0}) – new accept states:
Fʼ = {R ∈ Qʼ : R contains an accept state of M) January 8, 2024 CS21 Lecture 3 14
NFA, FA equivalence
• We have proved (⇐) by construction.
Formally we should also prove that the construction works, by induction on the number of steps of the computation.
– at each step, the state of the FA Mʼ is exactly the set of reachable states of the NFA M…
January 8, 2024 CS21 Lecture 3 15
Theorem: the set of languages recognized by NFA is closed under union, concatenation, and star.
Theorem: a language L is recognized by a FA if and only if L is recognized by a NFA.
Theorem: the set of languages recognized by FA is closed under union, concatenation, and star.
January 8, 2024 CS21 Lecture 3 16
• Describe the set of languages that can be built up from:
– concatenations – star operations
• Called “patterns” or regular expressions
• Theorem: a language L is recognized by a FA if and only if L is described by a regular expression.
January 8, 2024 CS21 Lecture 3 17
Regular expressions
• R is a regular expression if R is – a, for some a ∈ Σ
– ε, the empty string
– Ø, the empty set
– (R1 ∪ R2), where R1 and R2 are reg. exprs. –(R1 ∘R2),whereR1 andR2 arereg.exprs. – (R1*), where R1 is a regular expression
A reg. expression R describes the language L(R). January 8, 2024 CS21 Lecture 3 18
Regular expressions • example: R = (0∪1)
– if Σ = {0,1} then use “Σ” as shorthand for R
• example:R=0∘Σ*
– shorthand: omit “∘” R = 0Σ*
– precedence: *, then ∘ then ∪, unless override by parentheses
– in example R = 0(Σ*), not R = (0Σ)*
January 8, 2024 CS21 Lecture 3 19
Some examples
• {w:whasatleastone1}
alphabet Σ = {0,1}
• {w : w starts and ends with same symbol}
= 0Σ*0 ∪ 1Σ*1 ∪ 0 ∪ 1 • {w:|w|≤5}
= (ε ∪ Σ)(ε ∪ Σ)(ε ∪ Σ)(ε ∪ Σ)(ε ∪ Σ)
• {w : every 3rd position of w is 1 starting with the first position}
= (1ΣΣ)*(ε ∪ 1 ∪ 1Σ)
January 8, 2024 CS21 Lecture 3 20
Manipulating regular expressions
• The empty set and the empty string:
– Rε = εR = R
– RØ = ØR = Ø
–∪and∘behavelike+,x; Ø,εbehavelike0,1
• additional identities:
–R∪R=R (here +and∪differ) – (R1*R2)*R1* = (R1∪ R2)*
– R1(R2R1)* = (R1R2)*R1
January 8, 2024 CS21 Lecture 3 21
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com