際際滷

際際滷Share a Scribd company logo
1
2
mmm
cbaw 2
We pick
Let be the integer in the Pumping Lemma
Pick a string such that:
w Lw 
mw ||length
m
}0,:{ 鰹 
lncbaL lnln
and
3
Write
zyxcba mmm
2
it must be that length
From the Pumping Lemma
cccbcabaaaaaxyz ..................
x y z
m m m2
1||,|| 鰹 ymyx
1, 鰹 kay kThus:
4
From the Pumping Lemma:
Lzyx i

...,2,1,0i
Thus:
mmm
cbazyx 2

Lxzzyx =0
1, 鰹 kay k
5
From the Pumping Lemma:
Lcccbcabaaaxz  ...............
x z
km  m m2
mmm
cbazyx 2
 1, 鰹 kay k
Lxz 
Thus:
Lcba mmkm
 2
6
Lcba mmkm
 2
Lcba mmkm
 2
BUT:
CONTRADICTION!!!
}0,:{ 鰹 
lncbaL lnln
1k
7
Our assumption that
is a regular language is not true L
Conclusion: L is not a regular language
Therefore:
8
Regular languages
Non-regular languages
}0:{ !
鰹 naL n

More Related Content

More from Dr. ABHISHEK K PANDEY (20)

Multiplexing II
Multiplexing IIMultiplexing II
Multiplexing II
Dr. ABHISHEK K PANDEY
Est umts speech cells
Est umts speech cellsEst umts speech cells
Est umts speech cells
Dr. ABHISHEK K PANDEY
Digital to analog piyush sen
Digital to analog piyush senDigital to analog piyush sen
Digital to analog piyush sen
Dr. ABHISHEK K PANDEY
Adc
AdcAdc
Adc
Dr. ABHISHEK K PANDEY
Reguler grammar cfg
Reguler grammar cfgReguler grammar cfg
Reguler grammar cfg
Dr. ABHISHEK K PANDEY
Regular languag regular set
Regular languag regular setRegular languag regular set
Regular languag regular set
Dr. ABHISHEK K PANDEY
Regular expression for dfa
Regular expression for dfaRegular expression for dfa
Regular expression for dfa
Dr. ABHISHEK K PANDEY
Pumping lemma
Pumping lemmaPumping lemma
Pumping lemma
Dr. ABHISHEK K PANDEY
Pumping lemma for cfg
Pumping lemma for cfgPumping lemma for cfg
Pumping lemma for cfg
Dr. ABHISHEK K PANDEY
Power of authomata
Power of authomataPower of authomata
Power of authomata
Dr. ABHISHEK K PANDEY
Pda1
Pda1Pda1
Pda1
Dr. ABHISHEK K PANDEY
Pda
PdaPda
Pda
Dr. ABHISHEK K PANDEY
Pda numerical
Pda numericalPda numerical
Pda numerical
Dr. ABHISHEK K PANDEY
Pda numerical 2
Pda numerical 2Pda numerical 2
Pda numerical 2
Dr. ABHISHEK K PANDEY
Nondeterministic finite automaton
Nondeterministic finite automatonNondeterministic finite automaton
Nondeterministic finite automaton
Dr. ABHISHEK K PANDEY
Regular languag regular set
Regular languag regular setRegular languag regular set
Regular languag regular set
Dr. ABHISHEK K PANDEY
Regular expression for dfa
Regular expression for dfaRegular expression for dfa
Regular expression for dfa
Dr. ABHISHEK K PANDEY
Pda
PdaPda
Pda
Dr. ABHISHEK K PANDEY
Nfa(non deterministic finite automata)
Nfa(non deterministic finite automata)Nfa(non deterministic finite automata)
Nfa(non deterministic finite automata)
Dr. ABHISHEK K PANDEY
Moorey to mealy conversion
Moorey to mealy conversionMoorey to mealy conversion
Moorey to mealy conversion
Dr. ABHISHEK K PANDEY

Recently uploaded (20)

INTERNET OF THINGSSSSSSSSSSSSSSSSSSSSSSSSS.pptx
INTERNET OF THINGSSSSSSSSSSSSSSSSSSSSSSSSS.pptxINTERNET OF THINGSSSSSSSSSSSSSSSSSSSSSSSSS.pptx
INTERNET OF THINGSSSSSSSSSSSSSSSSSSSSSSSSS.pptx
bmit1
TASK-DECOMPOSITION BASED ANOMALY DETECTION OF MASSIVE AND HIGH-VOLATILITY SES...
TASK-DECOMPOSITION BASED ANOMALY DETECTION OF MASSIVE AND HIGH-VOLATILITY SES...TASK-DECOMPOSITION BASED ANOMALY DETECTION OF MASSIVE AND HIGH-VOLATILITY SES...
TASK-DECOMPOSITION BASED ANOMALY DETECTION OF MASSIVE AND HIGH-VOLATILITY SES...
samueljackson3773
Artificial intelligence based solar vehicle.pptx
Artificial intelligence based solar vehicle.pptxArtificial intelligence based solar vehicle.pptx
Artificial intelligence based solar vehicle.pptx
rrabin2
ESIT135 Problem Solving Using Python Notes of Unit-1 and Unit-2
ESIT135 Problem Solving Using Python Notes of Unit-1 and Unit-2ESIT135 Problem Solving Using Python Notes of Unit-1 and Unit-2
ESIT135 Problem Solving Using Python Notes of Unit-1 and Unit-2
prasadmutkule1
ESIT135 Problem Solving Using Python Notes of Unit-2 and Unit-3
ESIT135 Problem Solving Using Python Notes of Unit-2 and Unit-3ESIT135 Problem Solving Using Python Notes of Unit-2 and Unit-3
ESIT135 Problem Solving Using Python Notes of Unit-2 and Unit-3
prasadmutkule1
INVESTIGATION OF PUEA IN COGNITIVE RADIO NETWORKS USING ENERGY DETECTION IN D...
INVESTIGATION OF PUEA IN COGNITIVE RADIO NETWORKS USING ENERGY DETECTION IN D...INVESTIGATION OF PUEA IN COGNITIVE RADIO NETWORKS USING ENERGY DETECTION IN D...
INVESTIGATION OF PUEA IN COGNITIVE RADIO NETWORKS USING ENERGY DETECTION IN D...
csijjournal
Machine Vision lecture notes for Unit 3.ppt
Machine Vision lecture notes for Unit 3.pptMachine Vision lecture notes for Unit 3.ppt
Machine Vision lecture notes for Unit 3.ppt
SATHISHKUMARSD1
direct current machine first part about machine.pdf
direct current machine first part about machine.pdfdirect current machine first part about machine.pdf
direct current machine first part about machine.pdf
sahilshah890338
eng funda notes.pdfddddddddddddddddddddddd
eng funda notes.pdfdddddddddddddddddddddddeng funda notes.pdfddddddddddddddddddddddd
eng funda notes.pdfddddddddddddddddddddddd
aayushkumarsinghec22
Improving Surgical Robot Performance Through Seal Design.pdf
Improving Surgical Robot Performance Through Seal Design.pdfImproving Surgical Robot Performance Through Seal Design.pdf
Improving Surgical Robot Performance Through Seal Design.pdf
BSEmarketing
PPt physics -GD.pptx gd topic for physics btech
PPt physics -GD.pptx gd topic for physics btechPPt physics -GD.pptx gd topic for physics btech
PPt physics -GD.pptx gd topic for physics btech
kavyamittal2201735
Zero-Trust-Architecture-Reimagining-Network-Security.pptx
Zero-Trust-Architecture-Reimagining-Network-Security.pptxZero-Trust-Architecture-Reimagining-Network-Security.pptx
Zero-Trust-Architecture-Reimagining-Network-Security.pptx
yash98012
Defining the Future of Biophilic Design in Crete.pdf
Defining the Future of Biophilic Design in Crete.pdfDefining the Future of Biophilic Design in Crete.pdf
Defining the Future of Biophilic Design in Crete.pdf
ARENCOS
AIR FILTER system in internal combustion engine system.ppt
AIR FILTER system in internal combustion engine system.pptAIR FILTER system in internal combustion engine system.ppt
AIR FILTER system in internal combustion engine system.ppt
thisisparthipan1
惠悋惡 悋惠悋惶 悋悋愆悋悧 愆悛惠 悋悽惘愕悋悸
惠悋惡 悋惠悋惶 悋悋愆悋悧 愆悛惠 悋悽惘愕悋悸惠悋惡 悋惠悋惶 悋悋愆悋悧 愆悛惠 悋悽惘愕悋悸
惠悋惡 悋惠悋惶 悋悋愆悋悧 愆悛惠 悋悽惘愕悋悸
o774656624
Wireless-Charger presentation for seminar .pdf
Wireless-Charger presentation for seminar .pdfWireless-Charger presentation for seminar .pdf
Wireless-Charger presentation for seminar .pdf
AbhinandanMishra30
Common Network Architecture:X.25 Networks, Ethernet (Standard and Fast): fram...
Common Network Architecture:X.25 Networks, Ethernet (Standard and Fast): fram...Common Network Architecture:X.25 Networks, Ethernet (Standard and Fast): fram...
Common Network Architecture:X.25 Networks, Ethernet (Standard and Fast): fram...
SnehPrasad2
ESIT135 Problem Solving Using Python Notes of Unit-3
ESIT135 Problem Solving Using Python Notes of Unit-3ESIT135 Problem Solving Using Python Notes of Unit-3
ESIT135 Problem Solving Using Python Notes of Unit-3
prasadmutkule1
Indian Soil Classification System in Geotechnical Engineering
Indian Soil Classification System in Geotechnical EngineeringIndian Soil Classification System in Geotechnical Engineering
Indian Soil Classification System in Geotechnical Engineering
Rajani Vyawahare
Practice Head Torpedo - Neometrix Defence.pptx
Practice Head Torpedo - Neometrix Defence.pptxPractice Head Torpedo - Neometrix Defence.pptx
Practice Head Torpedo - Neometrix Defence.pptx
Neometrix_Engineering_Pvt_Ltd
INTERNET OF THINGSSSSSSSSSSSSSSSSSSSSSSSSS.pptx
INTERNET OF THINGSSSSSSSSSSSSSSSSSSSSSSSSS.pptxINTERNET OF THINGSSSSSSSSSSSSSSSSSSSSSSSSS.pptx
INTERNET OF THINGSSSSSSSSSSSSSSSSSSSSSSSSS.pptx
bmit1
TASK-DECOMPOSITION BASED ANOMALY DETECTION OF MASSIVE AND HIGH-VOLATILITY SES...
TASK-DECOMPOSITION BASED ANOMALY DETECTION OF MASSIVE AND HIGH-VOLATILITY SES...TASK-DECOMPOSITION BASED ANOMALY DETECTION OF MASSIVE AND HIGH-VOLATILITY SES...
TASK-DECOMPOSITION BASED ANOMALY DETECTION OF MASSIVE AND HIGH-VOLATILITY SES...
samueljackson3773
Artificial intelligence based solar vehicle.pptx
Artificial intelligence based solar vehicle.pptxArtificial intelligence based solar vehicle.pptx
Artificial intelligence based solar vehicle.pptx
rrabin2
ESIT135 Problem Solving Using Python Notes of Unit-1 and Unit-2
ESIT135 Problem Solving Using Python Notes of Unit-1 and Unit-2ESIT135 Problem Solving Using Python Notes of Unit-1 and Unit-2
ESIT135 Problem Solving Using Python Notes of Unit-1 and Unit-2
prasadmutkule1
ESIT135 Problem Solving Using Python Notes of Unit-2 and Unit-3
ESIT135 Problem Solving Using Python Notes of Unit-2 and Unit-3ESIT135 Problem Solving Using Python Notes of Unit-2 and Unit-3
ESIT135 Problem Solving Using Python Notes of Unit-2 and Unit-3
prasadmutkule1
INVESTIGATION OF PUEA IN COGNITIVE RADIO NETWORKS USING ENERGY DETECTION IN D...
INVESTIGATION OF PUEA IN COGNITIVE RADIO NETWORKS USING ENERGY DETECTION IN D...INVESTIGATION OF PUEA IN COGNITIVE RADIO NETWORKS USING ENERGY DETECTION IN D...
INVESTIGATION OF PUEA IN COGNITIVE RADIO NETWORKS USING ENERGY DETECTION IN D...
csijjournal
Machine Vision lecture notes for Unit 3.ppt
Machine Vision lecture notes for Unit 3.pptMachine Vision lecture notes for Unit 3.ppt
Machine Vision lecture notes for Unit 3.ppt
SATHISHKUMARSD1
direct current machine first part about machine.pdf
direct current machine first part about machine.pdfdirect current machine first part about machine.pdf
direct current machine first part about machine.pdf
sahilshah890338
eng funda notes.pdfddddddddddddddddddddddd
eng funda notes.pdfdddddddddddddddddddddddeng funda notes.pdfddddddddddddddddddddddd
eng funda notes.pdfddddddddddddddddddddddd
aayushkumarsinghec22
Improving Surgical Robot Performance Through Seal Design.pdf
Improving Surgical Robot Performance Through Seal Design.pdfImproving Surgical Robot Performance Through Seal Design.pdf
Improving Surgical Robot Performance Through Seal Design.pdf
BSEmarketing
PPt physics -GD.pptx gd topic for physics btech
PPt physics -GD.pptx gd topic for physics btechPPt physics -GD.pptx gd topic for physics btech
PPt physics -GD.pptx gd topic for physics btech
kavyamittal2201735
Zero-Trust-Architecture-Reimagining-Network-Security.pptx
Zero-Trust-Architecture-Reimagining-Network-Security.pptxZero-Trust-Architecture-Reimagining-Network-Security.pptx
Zero-Trust-Architecture-Reimagining-Network-Security.pptx
yash98012
Defining the Future of Biophilic Design in Crete.pdf
Defining the Future of Biophilic Design in Crete.pdfDefining the Future of Biophilic Design in Crete.pdf
Defining the Future of Biophilic Design in Crete.pdf
ARENCOS
AIR FILTER system in internal combustion engine system.ppt
AIR FILTER system in internal combustion engine system.pptAIR FILTER system in internal combustion engine system.ppt
AIR FILTER system in internal combustion engine system.ppt
thisisparthipan1
惠悋惡 悋惠悋惶 悋悋愆悋悧 愆悛惠 悋悽惘愕悋悸
惠悋惡 悋惠悋惶 悋悋愆悋悧 愆悛惠 悋悽惘愕悋悸惠悋惡 悋惠悋惶 悋悋愆悋悧 愆悛惠 悋悽惘愕悋悸
惠悋惡 悋惠悋惶 悋悋愆悋悧 愆悛惠 悋悽惘愕悋悸
o774656624
Wireless-Charger presentation for seminar .pdf
Wireless-Charger presentation for seminar .pdfWireless-Charger presentation for seminar .pdf
Wireless-Charger presentation for seminar .pdf
AbhinandanMishra30
Common Network Architecture:X.25 Networks, Ethernet (Standard and Fast): fram...
Common Network Architecture:X.25 Networks, Ethernet (Standard and Fast): fram...Common Network Architecture:X.25 Networks, Ethernet (Standard and Fast): fram...
Common Network Architecture:X.25 Networks, Ethernet (Standard and Fast): fram...
SnehPrasad2
ESIT135 Problem Solving Using Python Notes of Unit-3
ESIT135 Problem Solving Using Python Notes of Unit-3ESIT135 Problem Solving Using Python Notes of Unit-3
ESIT135 Problem Solving Using Python Notes of Unit-3
prasadmutkule1
Indian Soil Classification System in Geotechnical Engineering
Indian Soil Classification System in Geotechnical EngineeringIndian Soil Classification System in Geotechnical Engineering
Indian Soil Classification System in Geotechnical Engineering
Rajani Vyawahare

Pumping lemma numerical