Regular Languages Closed Under Complement Proof

Here we show that regular languages are closed under complement, in that if L is a regular language, then L' (the set of all strings not in L) is also regular. We prove this by considering a DFA for L, then trying to construct a DFA for L' by swapping the final and non-final states.
Contribute:
Patreon: / easytheory
Discord: / discord
Live Streaming (Saturdays, Sundays 2PM GMT):
Twitch: / easytheory
(KZbin also)
Mixer: mixer.com/easy...
Social Media:
Facebook Page: / easytheory
Facebook group: / easytheory
Twitter: / easytheory
Merch:
Language Hierarchy Apparel: teespring.com/...
Pumping Lemma Apparel: teespring.com/...
If you like this content, please consider subscribing to my channel: / @easytheory
▶ADDITIONAL QUESTIONS◀
1. Are finite languages closed under complement?
2. What else about a DFA guarantees that swapping the final and non-final states works? (Hint: number of computations.)
▶SEND ME THEORY QUESTIONS◀
[e-mail]
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental theory of computer science. It sets out to define, mathematically, what exactly computation is, what is feasible to solve using a computer, and also what is not possible to solve using a computer. The main objective is to define a computer mathematically, without the reliance on real-world computers, hardware or software, or the plethora of programming languages we have in use today. The notion of a Turing machine serves this purpose and defines what we believe is the crux of all computable functions.
This channel is also about weaker forms of computation, concentrating on two classes: regular languages and context-free languages. These two models help understand what we can do with restricted means of computation, and offer a rich theory using which you can hone your mathematical skills in reasoning with simple machines and the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them are tractable, i.e. we can build efficient algorithms to reason with objects such as finite automata, context-free grammars and pushdown automata. For example, we can model a piece of hardware (a circuit) as a finite-state system and solve whether the circuit satisfies a property (like whether it performs addition of 16-bit registers correctly). We can model the syntax of a programming language using a grammar, and build algorithms that check if a string parses according to this grammar.
On the other hand, most problems that ask properties about Turing machines
are undecidable. This KZbin channel will help you see and prove that several tasks involving Turing machines are unsolvable---i.e., no computer, no software, can solve it. For example, you will see that there is no software that can check whether a
C program will halt on a particular input. To prove something is possible is, of course, challenging. But to show something is impossible is rare in computer
science, and very humbling.

[@EasyTheory]

Next video: Product construction for DFAs! kzbin.info/www/bejne/e36vpoGArJisq7s

[@HelloThere-xs8ss]

thank you

[@xiaoyilian9266]

Hi Professor, this is Kevin who took your 480 last Spring. I am currently taking my graduate course where I need to go over some of the stuff from Computer Theory and I randomly ran into your new channel! Your videos are of great help and I hope you are doing well!

[@EasyTheory]

Yes I remember - thanks Kevin! Hope you're doing well.

[@TheWiseflower]

thank you so much! this was super helpful for my homework. ive been trying to learn this stuff for ages but i think every explanation i came across was too theoretical for me. this was very concrete, and the way that you repeat conclusions a few times and speak slowly was super accessible for me to understand. THANK YOU!

[@benpritchard2716]

Great video, it answers my question from the other day on Discord

[@EasyTheory]

Ben Pritchard good to know!

[@yeesa99]

Very clear and easy-to-understand explanation. Great video, thank you!

[@samyakkhadse3780]

nice explanation man. Its going to help me a lot in my assignments.

[@nikolaradakovic5050]

Amazing ! You explained so clearly a topic that required me days of fruitless surfing

[@EasyTheory]

Nikola Radakovic you're very welcome - make sure to follow the theory lectures series to see more videos like this.

[@nikolaradakovic5050]

@@EasyTheory Just subscribed. Appreciate your effort to produce such a valuable content.

[@privateaccount4460]

If you think about a DFA, the "trash" states are really juts the complement states. I think this is kind of what this is going at

[@programmerJourney]

Hello professor you are actually a smart person you are great in teaching I wish you were my professor in university thanks a lot for your good videos I hope I can pass the exam in 3 of July and save my scholarship

[@samjudelson]

Clear thank you!

[@gowtham_pb]

Great video!!!

[@sugatasaha4423]

Amazing explanation.

[@EasyTheory]

Sugata Saha thanks!