# CS计算机代考程序代写 LIMITATIONS OF REGULAR LANGUAGES

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))

• 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 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