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
(TH-cam 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 TH-cam 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! th-cam.com/video/EMLuNJw3yuY/w-d-xo.html

[@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!

[@yeesa99]

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

[@benpritchard2716]

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

[@EasyTheory]

Ben Pritchard good to know!

[@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.

[@hardworkleaner]

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!

[@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

[@gowtham_pb]

Great video!!!

[@sugatasaha4423]

Amazing explanation.

[@EasyTheory]

Sugata Saha thanks!