Application of the Pumping Lemma: Not All Languages are Regular (Theory of Computation)

Channel:
Canada PageWizard Games, Learning & Entertainment
Subscribers:
780
Published on ● Video Link: https://www.youtube.com/watch?v=QefKX9iGPBM


Duration: 23:14
13 views
2

In today's lecture we see how to prove a language is not regular. We use the pumping lemma to do this, via contradiction! We can view this prospect like a 2-player game, which I would like to attribute to Hopcroft et al. in their classic text.

Time Stamps:
0:00 Recap
0:06 Exploiting the propositional form of the Pumping Lemma, to derive a way to prove a language is not regular.
10:28 Proving our first non-regular language, the language where binary strings have equal numbers of 0s and 1s.
22:54 Closing

Have a beautiful day!

Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
Draikou
Patreon Supporters (Basic Support):
Patreon Supporters (Supporter Access!):
Eric R
-----------------------------------------------------------
Become a supporter today! To support my work and mission to provide free or accessible Computer Science education (especially in theory), subscribe to the channel, share my videos. Please donate and contribute to support my work for more content:
PATREON: https://www.patreon.com/PageWizard
SUBSCRIBESTAR: https://www.subscribestar.com/drpage
PAYPAL: https://paypal.me/pagewizard

Follow also at:
FACEBOOK: https://www.facebook.com/DanielRPage
TWITTER: https://twitter.com/PageWizardGLE
QUORA: https://www.quora.com/profile/Daniel-R-Page
TWITCH: https://www.twitch.tv/pagewizard

#ComputerScience
#pumpinglemma
#automatatheory



Other Videos By PageWizard Games, Learning & Entertainment


2023-04-21Language of Palindromic Strings is not Regular (Theory of Computing)
2023-04-19Language with Prime-Length Strings is not Regular [using Pumping Lemma] (Theory of Computing)
2023-04-19It's Poppin' Time!
2023-04-19Pushdown Automata
2023-04-17Tips on Using the Pumping Lemma to Prove Languages are Not Regular (Theory of Computing)
2023-04-14Caesar Cipher, Shift Cipher Cryptanalysis (Introductory Cryptography)
2023-04-14Dan Plays Chrono Trigger (April 13, 2023)
2023-04-12Shift Cipher (Introductory Cryptography)
2023-04-11Context-Free Grammars and Languages II
2023-04-10Cryptography: Basic Terminology, Communication Channel (Introductory Cryptography)
2023-04-07Application of the Pumping Lemma: Not All Languages are Regular (Theory of Computation)
2023-04-05The Pumping Lemma for Regular Languages [FULL PROOF] (Theory of Computing)
2023-04-03Pumping Lemma for Regular Languages: A Gentle Introduction (Theory of Computing)
2023-04-01Dan Plays Chrono Trigger (March 31, 2023 - Part 2)
2023-04-01Dan Plays Chrono Trigger (March 31, 2023 - Part 1)
2023-03-31Algebraic Laws of Regular Expressions and More! (Theory of Computing)
2023-03-29Applying Kleene's DFA to Regex Construction (Theory of Computing)
2023-03-28Exploring Properties of Regular Languages
2023-03-27Converting DFAs/NFAs to Regular Expressions - Kleene's Construction (Kleene's Theorem (Part 2))
2023-03-26The State of Academic Freedom in Canada
2023-03-24Converting Regular Expressions to ε-NFAs - Thompson's Construction (Kleene's Theorem (Part 1))


Tags:
Computer Science
Algorithms
Data Structures
Education
CompSci
CS
PageWizard
Mathematics
Accessibility
University
COMPSCI
COMP
CSCI
Western
Manitoba
StFX
Regina
pumping lemma
not regular
proof language is not regular
dfa
nfa
regex