Closure Properties of Regular Languages + Proofs

Here we prove five closure properties of regular languages, namely union, intersection, complement, concatenation, and star. We utilize results such as NFAs = DFAs, and give proofs for *why* all of these properties are closed for regular languages.

▶ADDITIONAL QUESTIONS◀
1. What about for context-free languages?
2. What about symmetric difference? (Set of strings that are in one of the two languages but not both)
3. What about majority of three languages A, B, C? (i.e., A, B, C are all regular and I want all strings that are in at least two of A, B, C)

▶SEND ME THEORY QUESTIONS◀

▶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.

[adamshaar]

you know a video is good when it makes you feel bad for paying tuition

[Minakreaj]

professor you are saving me right now from losing my scholarship and home that I can stay

[vimalathithand]

Really surprised that the video's have less views.you are doing a great job! And u are soo underrated.thanks a lot

[waynee]

We need to insert a new starting state for Kleene-Star because making the original starting state final might change the original language. E.g. DFA for words of odd length. We would change the language if we made the starting state final.
There might be a more generic answer to this but this was came to my mind first.

[lewkyb]

What advice do you have for students that have problems creating CFG/PDA/TM from descriptions of the language? I'm feeling like I've memorized the exercises from Sipser's and am having trouble finding more practice questions.

[mareloraby]

To prove that a language is closed under Difference, is it sufficient to say that the difference of two regular languages L1, L2 is L1 (intersection) with (Complement of L2) ?

[kunikoshindou]

These theories are so abstract, I don't understand what is the meaning to study them? Can you give some examples that how these theories are implemented in real life? Are there any practical meaning to study them? such as they can be used in making a program?

[unsunghero]

Just want to know what is that symbol you put at end the of the mathematical statement of the L2 machine "wi+1 ... w?" Is that n or ^ ?

[yunussozeri]

Can we somehow prove this without using the epsilon transitions?