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,RS,R By definition
3/7
HOW GENERAL ARE REGULAR LANGUAGES?
If R and S are regular languages, then so are
RS, RS, 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, RS, 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, RS, R
By definition
R S
RS = (( 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, RS, R
By definition
R S
RS = (( R)( S))
RS
RS = 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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
4/7
NOT ALL LANGUAGES ARE REGULAR
Pumping Lemma
For every regular language L, there exists a constant nL such that everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
ThelanguageL={0n1n |n0}is not regular!
4/7
NOT ALL LANGUAGES ARE REGULAR
Pumping Lemma
For every regular language L, there exists a constant nL such that everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
ThelanguageL={0n1n |n0}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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
ThelanguageL={0n1n |n0}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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
ThelanguageL={0n1n |n0}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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
ThelanguageL={0n1n |n0}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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
ThelanguageL={0n1n |n0}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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
5/7
PROOF OF THE PUMPING LEMMA
Pumping Lemma
For every regular language L, there exists a constant nL such that everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
L={(m)m |m0}isnotregular.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
L={(m)m |m0}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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
L={ap |pisaprimenumber}isnot regular.
Assume L is regular.
Choose prime number p nL + 2
=ap L.
=,where=aa,=ab,
a+bnL andb>0.
6/7
PUMPING LEMMA: MORE APPLICATIONS
Pumping Lemma
For every regular language L, there exists a constant nL such that everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
L={ap |pisaprimenumber}isnot regular.
Assume L is regular.
Choose prime number p nL + 2
=ap L.
=,where=aa,=ab,
a+bnL 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 everyLwith||nL canbe written as = with
||nL,
||>0,and
k Lforallk0.
L={ap |pisaprimenumber}isnot regular.
Assume L is regular.
Choose prime number p nL + 2
=ap L.
=,where=aa,=ab,
a+bnL 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
Reviews
There are no reviews yet.