Non-regular Languages
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Non-regular Languages as PDF for free.
More details
- Words: 853
- Pages: 39
Non-regular languages
1
n n
Non-regular languages
{a b : n ≥ 0} R
{vv : v ∈ {a, b}*}
Regular languages
a *b
b*c + a
b + c ( a + b) * etc... 2
How can we prove that a language is not regular?
L
Prove that there is no DFA that accepts
L
Problem: this is not easy to prove Solution: the Pumping Lemma !!! 3
The Pigeonhole Principle
4
4 pigeons
3 pigeonholes
5
A pigeonhole must contain at least two pigeons
6
n
pigeons ...........
m
pigeonholes
n>m
........... 7
The Pigeonhole Principle
n
pigeons
m
pigeonholes
n>m
There is a pigeonhole with at least 2 pigeons
........... 8
The Pigeonhole Principle and DFAs
9
DFA with
b
q1
4
states
b
b
a
q2
b
a
q3
b
q4
a 10
In walks of strings:
b
q1
a aa aab
no state is repeated
b
b
a
q2
a a
q3
b
q4
a 11
In walks of strings:
b
q1
a state aabb is repeated bbaa abbabb abbbabbabb...
b
b
a
q2
a a
q3
b
q4
a 12
If string
w
has length
| w | ≥ 4:
Then the transitions of string w are more than the states of the DFA Thus, a state must be repeated
b
q1
b
b
a
q2
a a
q3
b
q4
a 13
In general, for any DFA:
≥
String
w
has length
A state
q
must be repeated in the walk of
walk of
number of states
w
w ......
q
......
Repeated state
14
In other words for a string
w:
a
transitions are pigeons
q
states are pigeonholes
walk of
w ......
q
......
Repeated state
15
The Pumping Lemma
16
Take an infinite regular language L
There exists a DFA that accepts
L
m
states
17
Take string
w
with
w∈ L
There is a walk with label
w:
......... walk
w
18
If string
w
has length
| w| ≥ m
(number of states of DFA)
then, from the pigeonhole principle: a state is repeated in the walk
...... walk
q
w
w
...... 19
Let q be the first state repeated in the walk of w
...... walk
q
w
...... 20
Write
w= x y z y
......
x
q
......
z
21
Observations:
length length
| x y | ≤ m number of states of DFA
| y | ≥1
y
......
x
q
......
z
22
Observation:
The string is accepted
xz
y
......
x
q
......
z
23
Observation:
The string is accepted
xyyz
y
......
x
q
......
z
24
Observation:
The string is accepted
xyyyz
y
......
x
q
......
z
25
In General:
The string is accepted
i
xy z i = 0, 1, 2, ...
y
......
x
q
......
z
26
In General:
i
xy z ∈ L
i = 0, 1, 2, ...
Language accepted by the DFA
y
......
x
q
......
z
27
In other words, we described:
The Pumping Lemma !!!
28
The Pumping Lemma: • Given a infinite regular language • there exists an integer • for any string • we can write • with
w∈ L
L
m
with length
| w|≥ m
w= x y z
| x y | ≤ m and | y | ≥ 1
• such that:
i
xy z ∈ L
i = 0, 1, 2, ... 29
Applications of the Pumping Lemma
30
n n
Theorem: The language L = {a b : n ≥ 0} is not regular
Proof:
Use the Pumping Lemma
31
n n
L = {a b : n ≥ 0}
Assume for contradiction that L is a regular language
Since L is infinite we can apply the Pumping Lemma 32
n n
L = {a b : n ≥ 0} Let
m
be the integer in the Pumping Lemma
Pick a string
w
such that:
w∈ L length
We pick
| w|≥ m
m m
w=a b
33
Write:
m m
a b =xyz
From the Pumping Lemma it must be that length | x
y | ≤ m, | y |≥ 1
m m m
xyz = a b
= a...aa...aa...ab...b
x Thus:
m
y
z
k
y = a , k ≥1
34
k
m m
y = a , k ≥1
x y z=a b
From the Pumping Lemma:
i
xy z ∈ L i = 0, 1, 2, ...
Thus:
2
xy z ∈ L 35
k
m m
y = a , k ≥1
x y z=a b
From the Pumping Lemma:
2
xy z ∈ L
m+k
m
2
xy z = a...aa...aa...aa...ab...b ∈ L
x Thus:
a
y
y
z
m+ k m
b ∈L 36
a
BUT:
m+ k m
b ∈L
k≥ 1
n n
L = {a b : n ≥ 0}
a
m+ k m
b ∉L
CONTRADICTION!!! 37
Therefore:
Our assumption that L is a regular language is not true
Conclusion: L
is not a regular language
38
Non-regular languages
n n
{a b : n ≥ 0}
Regular languages
39
1
n n
Non-regular languages
{a b : n ≥ 0} R
{vv : v ∈ {a, b}*}
Regular languages
a *b
b*c + a
b + c ( a + b) * etc... 2
How can we prove that a language is not regular?
L
Prove that there is no DFA that accepts
L
Problem: this is not easy to prove Solution: the Pumping Lemma !!! 3
The Pigeonhole Principle
4
4 pigeons
3 pigeonholes
5
A pigeonhole must contain at least two pigeons
6
n
pigeons ...........
m
pigeonholes
n>m
........... 7
The Pigeonhole Principle
n
pigeons
m
pigeonholes
n>m
There is a pigeonhole with at least 2 pigeons
........... 8
The Pigeonhole Principle and DFAs
9
DFA with
b
q1
4
states
b
b
a
q2
b
a
q3
b
q4
a 10
In walks of strings:
b
q1
a aa aab
no state is repeated
b
b
a
q2
a a
q3
b
q4
a 11
In walks of strings:
b
q1
a state aabb is repeated bbaa abbabb abbbabbabb...
b
b
a
q2
a a
q3
b
q4
a 12
If string
w
has length
| w | ≥ 4:
Then the transitions of string w are more than the states of the DFA Thus, a state must be repeated
b
q1
b
b
a
q2
a a
q3
b
q4
a 13
In general, for any DFA:
≥
String
w
has length
A state
q
must be repeated in the walk of
walk of
number of states
w
w ......
q
......
Repeated state
14
In other words for a string
w:
a
transitions are pigeons
q
states are pigeonholes
walk of
w ......
q
......
Repeated state
15
The Pumping Lemma
16
Take an infinite regular language L
There exists a DFA that accepts
L
m
states
17
Take string
w
with
w∈ L
There is a walk with label
w:
......... walk
w
18
If string
w
has length
| w| ≥ m
(number of states of DFA)
then, from the pigeonhole principle: a state is repeated in the walk
...... walk
q
w
w
...... 19
Let q be the first state repeated in the walk of w
...... walk
q
w
...... 20
Write
w= x y z y
......
x
q
......
z
21
Observations:
length length
| x y | ≤ m number of states of DFA
| y | ≥1
y
......
x
q
......
z
22
Observation:
The string is accepted
xz
y
......
x
q
......
z
23
Observation:
The string is accepted
xyyz
y
......
x
q
......
z
24
Observation:
The string is accepted
xyyyz
y
......
x
q
......
z
25
In General:
The string is accepted
i
xy z i = 0, 1, 2, ...
y
......
x
q
......
z
26
In General:
i
xy z ∈ L
i = 0, 1, 2, ...
Language accepted by the DFA
y
......
x
q
......
z
27
In other words, we described:
The Pumping Lemma !!!
28
The Pumping Lemma: • Given a infinite regular language • there exists an integer • for any string • we can write • with
w∈ L
L
m
with length
| w|≥ m
w= x y z
| x y | ≤ m and | y | ≥ 1
• such that:
i
xy z ∈ L
i = 0, 1, 2, ... 29
Applications of the Pumping Lemma
30
n n
Theorem: The language L = {a b : n ≥ 0} is not regular
Proof:
Use the Pumping Lemma
31
n n
L = {a b : n ≥ 0}
Assume for contradiction that L is a regular language
Since L is infinite we can apply the Pumping Lemma 32
n n
L = {a b : n ≥ 0} Let
m
be the integer in the Pumping Lemma
Pick a string
w
such that:
w∈ L length
We pick
| w|≥ m
m m
w=a b
33
Write:
m m
a b =xyz
From the Pumping Lemma it must be that length | x
y | ≤ m, | y |≥ 1
m m m
xyz = a b
= a...aa...aa...ab...b
x Thus:
m
y
z
k
y = a , k ≥1
34
k
m m
y = a , k ≥1
x y z=a b
From the Pumping Lemma:
i
xy z ∈ L i = 0, 1, 2, ...
Thus:
2
xy z ∈ L 35
k
m m
y = a , k ≥1
x y z=a b
From the Pumping Lemma:
2
xy z ∈ L
m+k
m
2
xy z = a...aa...aa...aa...ab...b ∈ L
x Thus:
a
y
y
z
m+ k m
b ∈L 36
a
BUT:
m+ k m
b ∈L
k≥ 1
n n
L = {a b : n ≥ 0}
a
m+ k m
b ∉L
CONTRADICTION!!! 37
Therefore:
Our assumption that L is a regular language is not true
Conclusion: L
is not a regular language
38
Non-regular languages
n n
{a b : n ≥ 0}
Regular languages
39
Related Documents
Languages
November 2019 27
Io313g-languages
November 2019 11
Pidgin Languages
May 2020 10
Learning Languages
June 2020 14
0809 Languages
July 2020 8