BU CS 332 – Theory of Computation
Lecture 6:
• NFAs ‐> Regular expressions • Context‐free grammars
• Pumping lemma for CFLs
Reading:
Mark Bun February 10, 2020
Sipser Ch 1.3, 2.1, 2.3
Regular Expressions – Syntax
A regular expression is defined recursively using the following rules:
1. , , and are regular expressions for every
2. If and are regular expressions, then so are
,,and∗ Examples: (over )
∗∗∗∗
2/10/2020 CS332 ‐ Theory of Computation 2
Regular Expressions – Semantics
1. 2. 3.
for every
6.
∗ ∗
the language a regular expression describes
∗∗
2/10/2020 CS332 ‐ Theory of Computation 3
Example:
Regular Expressions Describe Regular Languages
Theorem: A language is regular if and only if it is described by a regular expression
Theorem 1: Every regular expression has an equivalent NFA Theorem 2: Every NFA has an equivalent regular expression
2/10/2020 CS332 ‐ Theory of Computation 4
NFA ‐> Regular expression
Theorem 2: Every NFA has an equivalent regex
Proof idea: Simplify NFA by “ripping out” states one at a
time and replacing with regexes
0 01*0 0
1
2/10/2020 CS332 ‐ Theory of Computation 5
Generalized NFAs
• Every transition is labeled by a regex
• One start state with only outgoing transitions
• Only one accept state with only incoming transitions • Start state and accept state are distinct
2/10/2020
CS332 ‐ Theory of Computation
6
∗ 𝑠
𝑎
Generalized NFA Example
2/10/2020
CS332 ‐ Theory of Computation
7
∗ 𝑠
𝑎
𝑠 𝑎
…
NFA ‐> Regular expression
2/10/2020
CS332 ‐ Theory of Computation
8
NFA
GNFA
𝑘 2 states 𝑘 1 states
𝑘 states
GNFA
GNFA
2 states
Regex
NFA ‐> GNFA
• •
Add a new start state with no incoming arrows. Make a unique accept state with no outgoing arrows.
ε
ε ε
NFA
ε
2/10/2020 CS332 ‐ Theory of Computation 9
GNFA ‐> Regular expression
Idea: While the machine has more than 2 states, rip one out and relabel the arrows with regexes to account for the missing state
1
3
2/10/2020
CS332 ‐ Theory of Computation
10
∗ 1
23
GNFA ‐> Regular expression
Idea: While the machine has more than 2 states, rip one out and relabel the arrows with regexes to account for the missing state
1
3
2/10/2020
CS332 ‐ Theory of Computation
11
∗ 1
23
GNFA ‐> Regular expression
Idea: While the machine has more than 2 states, rip one out and relabel the arrows with regexes to account for the missing state
1
3
2/10/2020
CS332 ‐ Theory of Computation 12
∗ 1
23
GNFA ‐> Regular expression
Idea: While the machine has more than 2 states, rip one out and relabel the arrows with regexes to account for the
missing state
2 1
1
3
2/10/2020
CS332 ‐ Theory of Computation
13
1
3 23
4
Example
2/10/2020 CS332 ‐ Theory of Computation 14
2/10/2020 CS332 ‐ Theory of Computation 15
2/10/2020 CS332 ‐ Theory of Computation 16
Context‐Free Grammars
2/10/2020 CS332 ‐ Theory of Computation 17
Some History
An abstract model for two distinct problems
Rules for parsing natural languages
2/10/2020 CS332 ‐ Theory of Computation 18
Some History
An abstract model for two distinct problems
Specification of syntax and compilation for programming languages
1977 ACM Turing Award citation (John Backus)
For profound, influential, and lasting contributions to the design of practical high‐ level programming systems, notably through his work on FORTRAN, and for seminal publication of formal procedures for the specification of programming languages.
2/10/2020 CS332 ‐ Theory of Computation 19
Context‐Free Grammar (Informal)
Example Grammar
Derivation
2/10/2020 CS332 ‐ Theory of Computation 20
Context‐Free Grammar (Informal)
Example Grammar 𝐺
𝐸 →𝐸𝑇 𝐸→𝑇
𝑇 →𝑇𝐹 𝑇→𝐹
𝐹 →𝐸 𝐹→𝑎 𝐹→𝑏
Derivation
𝐿𝐺
2/10/2020
CS332 ‐ Theory of Computation 21
Socially Awkward Professor Grammar
2/10/2020
CS332 ‐ Theory of Computation 22
Socially Awkward Professor Grammar
2/10/2020 CS332 ‐ Theory of Computation 23
Context‐Free Grammar (Formal)
A CFG is a 4‐tuple
• • •
is a finite set of variables
is a finite set of terminal symbols (disjoint from
)
,
•
is a finite set of production rules of the form
where and
is the start symbol
∗
Example: where
2/10/2020 CS332 ‐ Theory of Computation
24
Context‐Free Grammar (Formal)
A CFG is a 4‐tuple
= variables
= terminals
(“ yields
= rules = start
• Wesay
the grammar
”)if isaruleof or there exists a
• We say ⇒∗ (“ sequence such that
”) if
derives
• Language of the grammar:
Example: where
2/10/2020 CS332 ‐ Theory of Computation
25
∗ ⇒∗
CFG Examples
Give context‐free grammars for the following languages 1. The empty language
2. Strings of properly nested parentheses
3. Strings with equal # of ’s and ’s
2/10/2020 CS332 ‐ Theory of Computation 26
Pumping Lemma II: Pump Harder
2/10/2020 CS332 ‐ Theory of Computation 27
Non context‐free languages?
• Could it be the case that every language is context‐free? 2/10/2020 CS332 ‐ Theory of Computation 28
Pumping Lemma for regular languages
Let be a regular language.
Then there exists a “pumping length”
such that where:
For every where , can be split into three parts
1.
2.
3. 𝑖 for all
2/10/2020
CS332 ‐ Theory of Computation
29
Pumping Lemma for context‐free languages
Let be a context‐free language.
Then there exists a “pumping length” such that
For every where , can be split into five parts
where:
1.
2.
3. 𝑖 𝑖 forall
2/10/2020
CS332 ‐ Theory of Computation 30
Example:
∗
Pumping Lemma for context‐free languages
Let be a context‐free language.
Then there exists a “pumping length” such that
For every where , can be split into five parts
where:
1.
2.
3. 𝑖 𝑖 forall
2/10/2020
CS332 ‐ Theory of Computation 31
Example:
∗
Pumping Lemma as a game
1. YOU pick the language 𝐿 to be proved non context‐free.
2. ADVERSARY picks a possible pumping length 𝑝.
3. YOU pick 𝑤 of length at least 𝑝.
4. ADVERSARY divides 𝑤 into 𝑢, 𝑣, 𝑥, 𝑦, 𝑧, obeying rules of the Pumping Lemma: |𝑣𝑦| 0 and |𝑣𝑥𝑦| 𝑝.
5. YOU win by finding 𝑖 0, for which 𝑢𝑣𝑖𝑥𝑦𝑖𝑧 is not in 𝐿.
If regardless of how the ADVERSARY plays this game, you
can always win, then is non context‐free
2/10/2020 CS332 ‐ Theory of Computation 32
Pumping Lemma example
Claim: Proof: Assume
is not regular
is regular with pumping length
1. Find
2. Show that
with
cannot be pumped
If =
with | |
, then…
2/10/2020
CS332 ‐ Theory of Computation
33