際際滷

際際滷Share a Scribd company logo
1
2
 Given a infinite regular language
L
 there exists an integer
m
 for any string with length
Lw mw ||
 we can write
zyxw 
 with and
myx || 1|| y
 such that:
Lzyx i
 ...,2,1,0i
3
Regular languages
Non-regular languages
*}:{  vvvL R
4
Theorem: The language
is not regular
Proof: Use the Pumping Lemma
*}:{  vvvL R
},{ ba緒
5
Assume for contradiction
that L is a regular language
Since L is infinite
we can
apply the Pumping Lemma
*}:{  vvvL R

More Related Content

More from Dr. ABHISHEK K PANDEY (20)

PPTX
Osi modal
Dr. ABHISHEK K PANDEY
PPTX
Network topologies(chetan)
Dr. ABHISHEK K PANDEY
PPTX
Multiplexing II
Dr. ABHISHEK K PANDEY
PPTX
Est umts speech cells
Dr. ABHISHEK K PANDEY
PPTX
Digital to analog piyush sen
Dr. ABHISHEK K PANDEY
PPTX
Reguler grammar cfg
Dr. ABHISHEK K PANDEY
PPTX
Regular languag regular set
Dr. ABHISHEK K PANDEY
PPTX
Regular expression for dfa
Dr. ABHISHEK K PANDEY
PPTX
Pumping lemma numerical
Dr. ABHISHEK K PANDEY
PPT
Pumping lemma for cfg
Dr. ABHISHEK K PANDEY
PPTX
Power of authomata
Dr. ABHISHEK K PANDEY
PPTX
Pda numerical
Dr. ABHISHEK K PANDEY
PPTX
Pda numerical 2
Dr. ABHISHEK K PANDEY
PPTX
Nondeterministic finite automaton
Dr. ABHISHEK K PANDEY
PPTX
Regular languag regular set
Dr. ABHISHEK K PANDEY
PPTX
Regular expression for dfa
Dr. ABHISHEK K PANDEY
Network topologies(chetan)
Dr. ABHISHEK K PANDEY
Multiplexing II
Dr. ABHISHEK K PANDEY
Est umts speech cells
Dr. ABHISHEK K PANDEY
Digital to analog piyush sen
Dr. ABHISHEK K PANDEY
Reguler grammar cfg
Dr. ABHISHEK K PANDEY
Regular languag regular set
Dr. ABHISHEK K PANDEY
Regular expression for dfa
Dr. ABHISHEK K PANDEY
Pumping lemma numerical
Dr. ABHISHEK K PANDEY
Pumping lemma for cfg
Dr. ABHISHEK K PANDEY
Power of authomata
Dr. ABHISHEK K PANDEY
Pda numerical
Dr. ABHISHEK K PANDEY
Pda numerical 2
Dr. ABHISHEK K PANDEY
Nondeterministic finite automaton
Dr. ABHISHEK K PANDEY
Regular languag regular set
Dr. ABHISHEK K PANDEY
Regular expression for dfa
Dr. ABHISHEK K PANDEY

Recently uploaded (20)

PDF
13th International Conference of Security, Privacy and Trust Management (SPTM...
ijcisjournal
PPSX
OOPS Concepts in Python and Exception Handling
Dr. A. B. Shinde
PDF
MODULE-5 notes [BCG402-CG&V] PART-B.pdf
Alvas Institute of Engineering and technology, Moodabidri
PDF
Artificial Neural Network-Types,Perceptron,Problems
Sharmila Chidaravalli
PDF
A Brief Introduction About Robert Paul Hardee
Robert Paul Hardee
PPTX
Introduction to File Transfer Protocol with commands in FTP
BeulahS2
PDF
Module - 5 Machine Learning-22ISE62.pdf
Dr. Shivashankar
PPTX
darshai cross section and river section analysis
muk7971
PDF
Designing for Tomorrow Architectures Role in the Sustainability Movement
BIM Services
PPTX
Comparison of Flexible and Rigid Pavements in Bangladesh
Arifur Rahman
PDF
13th International Conference on Artificial Intelligence, Soft Computing (AIS...
ijait
PPTX
FSE_LLM4SE1_A Tool for In-depth Analysis of Code Execution Reasoning of Large...
cl144
PPTX
Alan Turing - life and importance for all of us now
Pedro Concejero
PDF
Tesia Dobrydnia - An Avid Hiker And Backpacker
Tesia Dobrydnia
PDF
William Stallings - Foundations of Modern Networking_ SDN, NFV, QoE, IoT, and...
lavanya896395
PDF
June 2025 Top 10 Sites -Electrical and Electronics Engineering: An Internatio...
elelijjournal653
PPTX
Electrical_Safety_EMI_EMC_Presentation.pptx
drmaneharshalid
PPTX
Precooling and Refrigerated storage.pptx
ThongamSunita
PDF
CLIP_Internals_and_Architecture.pdf sdvsdv sdv
JoseLuisCahuanaRamos3
PPTX
Computer network Computer network Computer network Computer network
Shrikant317689
13th International Conference of Security, Privacy and Trust Management (SPTM...
ijcisjournal
OOPS Concepts in Python and Exception Handling
Dr. A. B. Shinde
MODULE-5 notes [BCG402-CG&V] PART-B.pdf
Alvas Institute of Engineering and technology, Moodabidri
Artificial Neural Network-Types,Perceptron,Problems
Sharmila Chidaravalli
A Brief Introduction About Robert Paul Hardee
Robert Paul Hardee
Introduction to File Transfer Protocol with commands in FTP
BeulahS2
Module - 5 Machine Learning-22ISE62.pdf
Dr. Shivashankar
darshai cross section and river section analysis
muk7971
Designing for Tomorrow Architectures Role in the Sustainability Movement
BIM Services
Comparison of Flexible and Rigid Pavements in Bangladesh
Arifur Rahman
13th International Conference on Artificial Intelligence, Soft Computing (AIS...
ijait
FSE_LLM4SE1_A Tool for In-depth Analysis of Code Execution Reasoning of Large...
cl144
Alan Turing - life and importance for all of us now
Pedro Concejero
Tesia Dobrydnia - An Avid Hiker And Backpacker
Tesia Dobrydnia
William Stallings - Foundations of Modern Networking_ SDN, NFV, QoE, IoT, and...
lavanya896395
June 2025 Top 10 Sites -Electrical and Electronics Engineering: An Internatio...
elelijjournal653
Electrical_Safety_EMI_EMC_Presentation.pptx
drmaneharshalid
Precooling and Refrigerated storage.pptx
ThongamSunita
CLIP_Internals_and_Architecture.pdf sdvsdv sdv
JoseLuisCahuanaRamos3
Computer network Computer network Computer network Computer network
Shrikant317689
Ad

Pumping lemma