CS21 Decidability and Tractability
January 13, 2023
• Non-regular languages: Pumping Lemma
• Context-Free Grammars and Languages
Copyright By PowCoder代写 加微信 powcoder
January 12, 2024 CS21 Lecture 5 2
Non-regular languages
Pumping Lemma: Let L be a regular language. There exists an integer p (“pumping length”) for which every w ∈ L with |w| ≥ p can be written as
w = xyz such that 1. for every i ≥0, xyiz ∈L , and
2. |y|>0,and 3. |xy|≤p.
January 12, 2024 CS21 Lecture 5 3
Non-regular languages
• Using the Pumping Lemma to prove L is not regular:
– assume L is regular
– then there exists a pumping length p
– select a string w ∈ L of length at least p
– argue that for every way of writing w = xyz
that satisfies (2) and (3) of the Lemma,
pumping on y yields a string not in L.
– contradiction.
January 12, 2024 CS21 Lecture 5 4
Pumping Lemma Examples
• Theorem: L = {0i1j: i > j} is not regular. • Proof:
– let p be the pumping length for L – choose w = 0p+11p
w = 000000000…01111111…1 p+1 p
– w = xyz, with |y| > 0 and |xy| ≤ p.
January 12, 2024 CS21 Lecture 5 5
Pumping Lemma Examples
– 1 possibility:
w = 000000000…0111111111…1
– pumping on y gives strings in the language (?)
– this seems like a problem…
– Lemma states that for every i ≥ 0, xyiz ∈ L
– xy0z not in L. So L not regular.
January 12, 2024 CS21 Lecture 5 6
Proof of the Pumping Lemma
– Let M be a FA that recognizes L.
– Set p = number of states of M.
– Consider w ∈ L with |w| ≥ p. On input w, M
must go through at least p+1 states. There must be a repeated state (among first p+1).
CS21 Lecture 5
January 12, 2024
FA Summary
• A “problem” is a language
• A “computation” receives an input and
either accepts, rejects, or loops forever.
• A “computation” recognizes a language (it
may also decide the language).
• Finite Automata perform simple computations that read the input from left to right and employ a finite memory.
January 12, 2024 CS21 Lecture 5 8
FA Summary
• The languages recognized by FA are the
regular languages.
• The regular languages are closed under
union, concatenation, and star.
• Nondeterministic Finite Automata may
have several choices at each step.
• NFAs recognize exactly the same languages that FAs do.
January 12, 2024 CS21 Lecture 5 9
FA Summary
• Regular expressions are languages built up from the operations union, concatenation, and star.
• Regular expressions describe exactly the same languages that FAs (and NFAs) recognize.
• Some languages are not regular. This can be proved using the Pumping Lemma.
January 12, 2024 CS21 Lecture 5 10
Machine view of FA
input tape
011001110100101
finite control
January 12, 2024
CS21 Lecture 5 11
Machine view of FA
input tape
011001110100101
finite control
January 12, 2024
CS21 Lecture 5 12
Machine view of FA
input tape
011001110100101
finite control
January 12, 2024
CS21 Lecture 5 13
finite control
January 12, 2024
Machine view of FA
input tape
011001110100101
CS21 Lecture 5 14
A more powerful machine
• limitation of FA related to fact that they can only “remember” a bounded amount of information
• What is the simplest alteration that adds unbounded “memory” to our machine?
• Should be able to recognize, e.g., {0n1n: n ≥ 0} January 12, 2024 CS21 Lecture 5 15
finite control
January 12, 2024
input tape
011001110100101
0 (infinite) 1
stack 1 0 :
New capabilities:
• can push symbol onto stack
• can pop symbol off of stack
CS21 Lecture 5 16
finite control
input tape
001101110100101 q0
January 12, 2024
CS21 Lecture 5 17
$ (infinite) :
input tape
001101110100101 q1
finite control
January 12, 2024
0 (infinite) $
CS21 Lecture 5 18
input tape
001101110100101 q1
finite control
January 12, 2024
0 (infinite) 0
CS21 Lecture 5 19
input tape
001101110100101 q2
finite control
January 12, 2024
0 (infinite) $
CS21 Lecture 5 20
input tape
001101110100101 q2
finite control
January 12, 2024
(infinite) stack
CS21 Lecture 5
Note: often start by pushing $ marker onto stack so that we can detect “empty stack”
• We will define nondeterministic pushdown automata immediately
– potentially several choices of “next step” • Deterministic PDA defined later
– weaker than NPDA
• Two ways to describe NPDA
– formal definition
January 12, 2024 CS21 Lecture 5 22
tape alphabet Σ stack alphabet 𝚪
start state states
accept states
January 12, 2024
transition label: (tape symbol read, stack symbol popped → stack symbol pushed)
NPDA diagram
transitions
CS21 Lecture 5
NPDA operation
• Taking a transition labeled:
– read a from tape, or don’t read from tape if a = ε
– pop b from stack, or don’t pop from stack if b = ε – push c onto stack, or don’t push onto stack if c = ε
January 12, 2024 CS21 Lecture 5 24
– a ∈ (Σ ∪ {ε}) – b,c ∈ (Γ ∪ {ε})
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 0 0 1 1 January 12, 2024
Example NPDA
Stack contents: $
CS21 Lecture 5 25
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 0011 January 12, 2024
Example NPDA
Stackcontents: 0$
CS21 Lecture 5 26
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 0011 January 12, 2024
Example NPDA
Stackcontents: 00$
CS21 Lecture 5 27
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 0011 January 12, 2024
Example NPDA
Stackcontents: 00$
CS21 Lecture 5 28
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 0011 January 12, 2024
Example NPDA
Stackcontents: 0$
CS21 Lecture 5 29
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 0 0 1 1 accepted
January 12, 2024
Example NPDA
1, 0 → ε Stack contents: $
CS21 Lecture 5 30
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 0 0 1 January 12, 2024
Example NPDA
Stack contents: $
CS21 Lecture 5 31
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 0 0 1 January 12, 2024
Example NPDA
Stack contents: 0 $
CS21 Lecture 5 32
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 001 January 12, 2024
Example NPDA
Stackcontents: 00$
CS21 Lecture 5 33
Σ = {0, 1} 𝚪 = {0, 1, $}
• tape: 001 January 12, 2024
Example NPDA
Stackcontents: 00$
CS21 Lecture 5 34
Σ = {0, 1} 𝚪 = {0, 1, $}
Example NPDA
• tape: 0 0 1 Stack contents: 0 $
not accepted
January 12, 2024 CS21 Lecture 5 35
Σ = {0, 1} 𝚪 = {0, 1, $}
Example NPDA
• What language does this NPDA accept? January 12, 2024 CS21 Lecture 5 36
Formal definition of NPDA
• ANPDAisa6-tuple(Q,Σ,Γ,δ,q0,F) where:
– Q is a finite set called the states
– Σ is a finite set called the tape alphabet
– Γ is a finite set called the stack alphabet
– δ:Q x (Σ ∪ {ε}) x (Γ ∪ {ε}) → P(Q x (Γ ∪ {ε})) 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 12, 2024 CS21 Lecture 5 37
Formal definition of NPDA
• NPDAM=(Q,Σ,Γ, δ,q0,F)accepts string w ∈ Σ* if w can be written as
w1w2w3…wm ∈ (Σ ∪ {ε})*, and
• there exist states r0, r1, r2, …, rm, and
• there exist strings s0, s1, …, sm in (Γ ∪ {ε})*
–r0 =q0 ands0 =ε
– (ri+1, b) ∈ δ(ri, wi+1, a), where si = at, si+1 = bt
for some t ∈ Γ∗ –rm ∈F
January 12, 2024 CS21 Lecture 5 38
Example of formal definition
• Q={q0,q1,q2,q3} • Σ = {0,1}
• Γ={0,1,$}
• F={q0,q3}
January 12, 2024
ε, ε → $ q1
1, 0 → ε ε, $ → ε q2
• δ(q0,ε,ε)={(q1,$)} • δ(q1, 0, ε) = {(q1, 0)} • δ(q1, 1, 0) = {(q2, ε)} • δ(q2, 1, 0) = {(q2, ε)} • δ(q2, ε, $) = {(q3, ε)}
CS21 Lecture 5
other values of
δ(•, •, •) equal {}
Design a NPDA for the language
{aibjck :i,j,k≥0andi=jori=k}
January 12, 2024 CS21 Lecture 5 40
Context-free grammars and languages
• languages recognized by a (N)FA are exactly the languages described by regular expressions, and they are called the regular languages
• languages recognized by a NPDA are exactly the languages described by context-free grammars, and they are called the context-free languages
January 12, 2024 CS21 Lecture 5 41
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com