LIMITATIONS OF REGULAR LANGUAGES
PRINCIPLES OF PROGRAMMING LANGUAGES
Norbert Zeh Winter 2021
Dalhousie University
1/7
ROAD MAP
• Regular languages
• Regular expressions
• Deterministic finite automata (DFA)
• Non-deterministic finite automata (NFA)
• Expressive power of DFA and NFA
• Equivalence of regular expressions, DFA, and NFA
• Building a scanner
• Regular expression → NFA → DFA • Minimizing the DFA
• Limitations of regular languages
2/7
HOW GENERAL ARE REGULAR LANGUAGES?
If R and S are regular languages, then so are
3/7
HOW GENERAL ARE REGULAR LANGUAGES?
If R and S are regular languages, then so are
• RS,R∪S,R∗ By definition
3/7
HOW GENERAL ARE REGULAR LANGUAGES?
If R and S are regular languages, then so are
• RS, R∪S, R∗ By definition
• Σ∗ \R (the complement of R)
Build a DFA for Σ∗ \ R from a DFA for R by making accepting states non-accepting and vice versa.
3/7
HOW GENERAL ARE REGULAR LANGUAGES?
If R and S are regular languages, then so are
• RS, R∪S, R∗ By definition
• Σ∗ \R (the complement of R)
Build a DFA for Σ∗ \ R from a DFA for R by making accepting states non-accepting and vice versa.
←−
• R ={σ |σ∈R},where σ isσ
←− ←− written backwards
A regular expression for R “written
backwards” is a regular expression
for R.
3/7
←−
HOW GENERAL ARE REGULAR LANGUAGES?
If R and S are regular languages, then so are • RS, R∪S, R∗
By definition
• R ∩ S
R∩S = Σ∗ \((Σ∗ \R)∪(Σ∗ \S))
• Σ∗ \R (the complement of R)
Build a DFA for Σ∗ \ R from a DFA for R by making accepting states non-accepting and vice versa.
←−
• R ={σ |σ∈R},where σ isσ
←− ←− written backwards
A regular expression for R “written
backwards” is a regular expression
for R.
3/7
←−
HOW GENERAL ARE REGULAR LANGUAGES?
If R and S are regular languages, then so are • RS, R∪S, R∗
By definition
• R ∩ S
R∩S = Σ∗ \((Σ∗ \R)∪(Σ∗ \S))
• R\S
R\S = R∩(Σ∗ \S)
• Σ∗ \R (the complement of R)
Build a DFA for Σ∗ \ R from a DFA for R by making accepting states non-accepting and vice versa.
←−
• R ={σ |σ∈R},where σ isσ
←− ←− written backwards
A regular expression for R “written
backwards” is a regular expression
for R.
3/7
←−
NOT ALL LANGUAGES ARE REGULAR
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
4/7
NOT ALL LANGUAGES ARE REGULAR
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
⇒ThelanguageL={0n1n |n≥0}is not regular!
4/7
NOT ALL LANGUAGES ARE REGULAR
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
⇒ThelanguageL={0n1n |n≥0}is not regular!
• Assume L is regular.
4/7
NOT ALL LANGUAGES ARE REGULAR
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
⇒ThelanguageL={0n1n |n≥0}is not regular!
• Assume L is regular. • Letσ=0nL1nL ∈L.
4/7
NOT ALL LANGUAGES ARE REGULAR
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
⇒ThelanguageL={0n1n |n≥0}is not regular!
• Assume L is regular.
• Letσ=0nL1nL ∈L.
• Thenσ=αβγwith|αβ|≤nL and |β| > 0 and αββγ ∈ L.
4/7
NOT ALL LANGUAGES ARE REGULAR
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
⇒ThelanguageL={0n1n |n≥0}is not regular!
• Assume L is regular.
• Letσ=0nL1nL ∈L.
• Thenσ=αβγwith|αβ|≤nL and |β| > 0 and αββγ ∈ L.
• Since|αβ|≤nL,wehaveα=0k and β = 0m, where m = |β| > 0.
4/7
NOT ALL LANGUAGES ARE REGULAR
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
⇒ThelanguageL={0n1n |n≥0}is not regular!
• Assume L is regular.
• Letσ=0nL1nL ∈L.
• Thenσ=αβγwith|αβ|≤nL and |β| > 0 and αββγ ∈ L.
• Since|αβ|≤nL,wehaveα=0k and β = 0m, where m = |β| > 0.
• Thus, αββγ = 0m+nL 1nL ∈/ L, ⇒⇐.
4/7
PROOF OF THE PUMPING LEMMA
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
5/7
PROOF OF THE PUMPING LEMMA
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
Proof:
Let D = (S,Σ,δ,s0,F) be a DFA such that L = L(D).
5/7
PROOF OF THE PUMPING LEMMA
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
Proof:
Let D = (S,Σ,δ,s0,F) be a DFA such that L = L(D).
Let nL = |S|+1.
5/7
PROOF OF THE PUMPING LEMMA
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
Proof:
Let D = (S,Σ,δ,s0,F) be a DFA such that L = L(D).
Let nL = |S|+1.
start
5/7
PROOF OF THE PUMPING LEMMA
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
Proof:
Let D = (S,Σ,δ,s0,F) be a DFA such that L = L(D).
Let nL = |S|+1.
start
5/7
PROOF OF THE PUMPING LEMMA
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
Proof:
Let D = (S,Σ,δ,s0,F) be a DFA such that L = L(D).
Let nL = |S|+1.
start
5/7
PROOF OF THE PUMPING LEMMA
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
Proof:
Let D = (S,Σ,δ,s0,F) be a DFA such that L = L(D).
Let nL = |S|+1.
β
start
α
γ
5/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
• L={(m)m |m≥0}isnotregular.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
• L={(m)m |m≥0}isnotregular. Same structure as L′ = {0n1n | n ≥ 0}.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
• L={ap |pisaprimenumber}isnot regular.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
• L={ap |pisaprimenumber}isnot regular.
• Assume L is regular.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
• L={ap |pisaprimenumber}isnot regular.
• Assume L is regular.
• Choose prime number p ≥ nL + 2
⇒σ=ap ∈L.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
• L={ap |pisaprimenumber}isnot regular.
• Assume L is regular.
• Choose prime number p ≥ nL + 2
⇒σ=ap ∈L.
• σ=αβγ,whereα=aa,β=ab,
a+b≤nL andb>0.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
• L={ap |pisaprimenumber}isnot regular.
• Assume L is regular.
• Choose prime number p ≥ nL + 2
⇒σ=ap ∈L.
• σ=αβγ,whereα=aa,β=ab,
a+b≤nL andb>0. • αβcγ ∈ L, where
c = |αγ| = p − b ≥ 2.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyσ∈Lwith|σ|≥nL canbe written as σ = αβγ with
• |αβ|≤nL,
• |β|>0,and
• αβkγ ∈Lforallk≥0.
• L={ap |pisaprimenumber}isnot regular.
• Assume L is regular.
• Choose prime number p ≥ nL + 2
⇒σ=ap ∈L.
• σ=αβγ,whereα=aa,β=ab,
a+b≤nL andb>0.
• αβcγ ∈ L, where
c = |αγ| = p − b ≥ 2.
• |αβcγ| = (b + 1)c, which is not prime
because b + 1 ≥ 2 and c ≥ 2, ⇒⇐.
6/7
SUMMARY
• Parsing is complex.
7/7
SUMMARY
• Parsing is complex.
• Lexical analysis turns character stream into
more compact token stream.
7/7
SUMMARY
• Parsing is complex.
• Lexical analysis turns character stream into
more compact token stream.
• Regular languages are general enough to capture the structure of tokens but not general enough to capture the structure of programming languages.
7/7
SUMMARY
• Parsing is complex.
• Lexical analysis turns character stream into
more compact token stream.
• Regular languages are general enough to capture the structure of tokens but not general enough to capture the structure of programming languages.
• There exist languages that are not regular.
7/7
SUMMARY
• Parsing is complex.
• Lexical analysis turns character stream into
more compact token stream.
• Regular languages are general enough to capture the structure of tokens but not general enough to capture the structure of programming languages.
• There exist languages that are not regular.
• Describe regular languages using regular expressions, recognize using DFA.
7/7
SUMMARY
• Parsing is complex.
• Lexical analysis turns character stream into
more compact token stream.
• Regular languages are general enough to capture the structure of tokens but not general enough to capture the structure of programming languages.
• There exist languages that are not regular.
• Describe regular languages using regular expressions, recognize using DFA.
• DFA are very simple machines that can be implemented very efficiently.
7/7
SUMMARY
• Parsing is complex.
• Lexical analysis turns character stream into
more compact token stream.
• Regular languages are general enough to capture the structure of tokens but not general enough to capture the structure of programming languages.
• There exist languages that are not regular.
• Describe regular languages using regular expressions, recognize using DFA.
• DFA are very simple machines that can be implemented very efficiently.
• NFA are mainly a tool for translating regular expressions to DFA.
7/7
SUMMARY
• Parsing is complex.
• Lexical analysis turns character stream into
more compact token stream.
• Regular languages are general enough to capture the structure of tokens but not general enough to capture the structure of programming languages.
• There exist languages that are not regular.
• Describe regular languages using regular expressions, recognize using DFA.
• DFA are very simple machines that can be implemented very efficiently.
• NFA are mainly a tool for translating regular expressions to DFA.
• Lexical analysis requires simple extensions to DFA: which token we accepted,
support greediness/backtracking.
7/7