Regular Languages Closed Under Homomorphism

Here we show that the regular languages are closed under homomorphism, which is a function from Sigma* to itself that has a nice "splitting" property. We use this property in the proof by constructing an NFA for the desired "homomorphism" language, by breaking up every transition into many smaller transitions.
#easytheory #nfa #dfa #gate #gateconcept #theoryofcomputing #turingmachine #nfatoregex #cfg #pda #undecidable #ricestheorem
Contribute:
Patreon: / easytheory
Discord: / discord
Live Streaming (Sundays 2PM GMT, 2 hours):
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
Ultimate Supporters: (none)
Diamond Supporters: (none)
Platinum Supporters: (none)
Gold Supporters: Anonymous (x1), Micah Wood, Ben Pritchard
Silver Supporters: Timmy Gy
Supporters: Yash Singhal
▶ADDITIONAL QUESTIONS◀
1. Construct an NFA for the example homomorphism given in the video applied to a "starter" DFA.
2. Can it be possible for a finite language L to have h(L) be infinite?
3. Can it be possible for an infinite language L to have h(L) be finite?
▶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.

[@denikhalikov5178]

Hey dude dont stop these please, we're sharing you on Reddit to get more exposure, these are REALLY helpful!

[@EasyTheory]

Will do :) (sorry for the delay in responding)

[@denikhalikov5178]

@@EasyTheory no worries and thanks!

[@deveshnandan323]

Thanks a lot man , your videos are really helpfull for aspirants preparing for gate exam :)

[@naydernn4725]

You explain this stuff sooooooo much better than my teacher ever could! Thank you!!

[@christiansinger2497]

Really helped, since I was able to use the same idea to show that regular languages are closed under the application of a finite-state transducer.

[@trevormartin1944]

Thank you for uploading this video, I really appreciate it.

[@marekvargovcik2651]

commenting so you get more recognition. introduction to theory of computation is a life saver! thanks

[@attafriski5901]

Thanks a lot, helps me understand this subject

[@PewPewFishing]

that pre test study help !

[@EasyTheory]

You're welcome! :)

[@i3badiix]

thanks bro ♥, you deserve more views !

[@turkirob]

Fantastic , really very good explanation

[@vimalathithand917]

Thanks a lot!

[@jeremiahbullock2677]

Life saver! Thank you boss!

[@EasyTheory]

You're welcome! :)

[@30benasabu65]

Sir what is the exact application of this homomorphism like I dont understand where it is usefull

[@stijnjongbloed1]

Thanks for the video!

[@peleghatuka6074]

very helpful man, thanks a lot!

[@wincash584]

Worth it to watch on - 18/01/2022

[@piotrgorczyca5548]

(comment supporting channel growth)

[@SebasMederos]

great video! keep on!

[@bemsorcaabay8509]

Good explanation... Better if there is a concrete example.

[@bionictran]

Please do decision properties of CFL's. Otherwise, great video!

[@EasyTheory]

I think I did that already, it's the "all closure properties" video.

[@samjudelson]

Thanks!

[@samjudelson]

Next?

[@tirthpatel20]

good1