CS21 Decidability and Tractability
Lecture 4 January 10, 2024
Regular expressions
• R is a regular expression if R is – a, for some a ∈ Σ
Copyright By PowCoder代写 加微信 powcoder
– ε, 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 10, 2024 CS21 Lecture 4 2
Regular expressions and FA
• Theorem: a language L is recognized by a FA if and only if L is described by a regular expression.
Must prove two directions:
(⇒) L is recognized by a FA implies L is
described by a regular expression
(⇐) L is described by a regular expression
implies L is recognized by a FA.
January 10, 2024 CS21 Lecture 4 3
Regular expressions and FA (⇐) L is described by a regular expression
implies L is recognized by a FA
Proof: given regular expression R we will
build a NFA that recognizes L(R).
then NFA, FA equivalence implies a FA for L(R).
January 10, 2024 CS21 Lecture 4 4
Regular expressions and FA • R is a regular expression if R is
– a, for some a ∈ Σ – ε, the empty string – Ø, the empty set
January 10, 2024 CS21 Lecture 4
Regular expressions and FA
–(R1 ∪R2),whereR1 andR2 arereg.exprs. ε
–(R1 ∘R2),whereR1 andR2 arereg.exprs. ε
– (R1*), where R1 is a regular expression
January 10, 2024 CS21 Lecture 4
Regular expressions and FA
• Theorem: a language L is recognized by a FA if and only if L is described by a regular expression.
Must prove two directions:
(⇒) L is recognized by a FA implies L is
described by a regular expression
(⇐) L is described by a regular expression
implies L is recognized by a FA.
January 10, 2024 CS21 Lecture 4 7
Regular expressions and FA
(⇒) L is recognized by a FA implies L is described by a regular expression
Proof: given FA M that recognizes L, we will 1. buildanequivalentmachine“Generalized
Nondeterministic Finite Automaton” (GNFA) 2. converttheGNFAintoaregularexpression
January 10, 2024 CS21 Lecture 4 8
Regular expressions and FA • GNFA definition:
– it is a NFA, but may have regular expressions labeling its transitions
– GNFA accepts string w ∈ Σ* if can be written w = w1w2w3… wk
where each wi ∈ Σ*, and there is a path from the start state to an accept state in which the ith transition traversed is labeled with R for which wi ∈L(R)
January 10, 2024 CS21 Lecture 4 9
Regular expressions and FA • Recall step 1: build an equivalent GNFA
• OurFAMisaGNFA.
• We will require “normal form” for GNFA to
make the proof easier:
– single accept state qaccept that has all possible
incoming arrows
– every state has all possible outgoing arrows;
exception: start state q0 has no self-loop
January 10, 2024 CS21 Lecture 4 10
Regular expressions and FA
• converting our FA M into GNFA in normal form:
January 10, 2024
CS21 Lecture 4
0 ∪0 , 1 1 ε
Regular expressions and FA
• On to step 2: convert the GNFA into a regular expression
– if normal-form GNFA has two states:
the regular expression R labeling the single transition describes the language recognized by the GNFA
January 10, 2024 CS21 Lecture 4 12
Regular expressions and FA – if GNFA has more than 2 states:
– select one “qrip”; delete it; repair transitions so that machine still recognizes same language.
– repeat until only 2 states.
January 10, 2024 CS21 Lecture 4 13
Regular expressions and FA – how to repair the transitions:
– for every pair of states qi and qj do
qj (R1 )(R2 )*(R3) ∪ (R4)
January 10, 2024
CS21 Lecture 4
R1 R3 qi qrip
Regular expressions and FA
– summary:
FA M → k-state GNFA → (k-1)-state GNFA
→ (k-2)-state GNFA →…→ 2-state GNFA → R – want to prove that this procedure is correct,
i.e. L(R) = language recognized by M
• FA M equivalent to k-state GNFA
• i-state GNFA equivalent to (i-1)-state GNFA (we will prove…)
• 2-state GFNA equivalent to R January 10, 2024 CS21 Lecture 4
Regular expressions and FA – Claim: i-state GNFA G equivalent to (i-1)-
state GNFA Gʼ (obtained by removing qrip)
• if G accepts string w, then it does so by entering
states: q0, q1, q2, q3, … , qaccept
• if none are qrip then Gʼ accepts w (see slide)
• else, break state sequence into runs of qrip:
q0q1…qiqripqrip…qripqj…qaccept
• transition from qi to qj in Gʼ allows all strings taking
G from qi to qj using qrip (see slide)
• thus Gʼ accepts w
January 10, 2024 CS21 Lecture 4 16
Regular expressions and FA
January 10, 2024
qj (R1 )(R2 )*(R3) ∪ (R4) R1 R3 qi qj
CS21 Lecture 4 17
Regular expressions and FA
January 10, 2024
qj (R1 )(R2 )*(R3) ∪ (R4) R1 R3 qi qj
CS21 Lecture 4 18
Regular expressions and FA – Proof (continued):
• if Gʼ accepts string w, then every transition from qi to qj traversed in Gʼ corresponds to
a transition from qi to qj in G
transitions from qi to qj via qrip in G
• In both cases G accepts w.
• Conclude: G and Gʼ recognize the same language. January 10, 2024 CS21 Lecture 4 19
Regular expressions and FA
• Theorem: a language L is recognized by a
FA iff L is described by a regular expr.
• Languages recognized by a FA are called
regular languages.
• Rephrasing what we know so far:
– regular languages closed under 3 operations – NFA recognize exactly the regular languages – regular expressions describe exactly the
regular languages
January 10, 2024 CS21 Lecture 4 20
Limits on the power of FA
• Is every language describable by a sufficiently complex regular expression?
• If someone asks you to design a FA for a language that seems hard, how do you know when to give up?
• Is this language regular?
{w : w has an equal # of “01” and “10” substrings}
January 10, 2024 CS21 Lecture 4 21
Limits on the power of FA
• Intuition:
– FA can only remember finite amount of
information. They cannot count
– languages that “entail counting” should be
non-regular…
• Intuition not enough:
{w : w has an equal # of “01” and “10” substrings}
= 0Σ*0 ∪ 1Σ*1
but {w: w has an equal # of “0” and “1” substrings} is not regular!
January 10, 2024 CS21 Lecture 4 22
Limits on the power of FA
How do you prove that there is no Finite Automaton recognizing a given language?
January 10, 2024 CS21 Lecture 4 23
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 10, 2024 CS21 Lecture 4 24
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 10, 2024 CS21 Lecture 4 25
Pumping Lemma Examples
• Theorem: L = {0n1n : n ≥ 0} is not regular. • Proof:
– let p be the pumping length for L
– choose w = 0p1p
w = 000000000…0111111111…1 pp
– w=xyz,with|y|>0and|xy|≤p.
January 10, 2024 CS21 Lecture 4 26
Pumping Lemma Examples
– 3 possibilities:
w = 000000000…0111111111…1
w = 000000000…0111111111…1 xyz
w = 000000000…0111111111…1
– in each case, pumping on y gives a string not in language L.
January 10, 2024 CS21 Lecture 4 27
Pumping Lemma Examples
• Theorem:L={w:whasanequal#of0s and 1s} is not regular.
– let p be the pumping length for L
– choose w = 0p1p
w = 000000000…0111111111…1 pp
– w=xyz,with|y|>0and|xy|≤p.
January 10, 2024 CS21 Lecture 4 28
Pumping Lemma Examples
– 3 possibilities:
w = 000000000…0111111111…1
w = 000000000…0111111111…1 xyz
w = 000000000…0111111111…1 xyz
– first 2 cases, pumping on y gives a string not in language L; 3rd case a problem!
January 10, 2024 CS21 Lecture 4 29
Pumping Lemma Examples
– recall condition 3: |xy| ≤ p
– since w = 0p1p we know more about how it can be divided, and this case cannot arise:
w = 000000000…0111111111…1 xyz
– so we do get a contradiction.
– conclude that L is not regular.
January 10, 2024 CS21 Lecture 4 30
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com