Regular Languages Closed Under Reversal
ฝัง
- เผยแพร่เมื่อ 11 ม.ค. 2025
- Here we show that regular languages are closed under reversal, and give some tips on why the "usual" proof is not quite right. The main idea is to take a DFA for the language, and reverse all of its transitions. The problem is that the resulting machine may not necessarily be a DFA or even an NFA. But by observing what the resulting language should be (the reverse of all the strings), we can make some adjustments to it to make it work, which we cover in the video.
#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. How large will the "reverse" DFA be in relation to the original one? (after converting from an NFA to DFA)
2. What if we ask all strings such that some substring of it is reversed?
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶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.
Thanks for this excellent explanation! I am finishing a course on Theory of Computation (I actually have an exam tomorrow). I tried the DFA idea first but I saw that didn't work, thought using an NFA might be better but didn't get it to quite work out. Then I never got a solution from my teachers. So thank you! That helped!
I cannot thank you enough good sir. You have helped me multiple times now and I have finally happily subscribed.
Welcome to the group! :)
You are a life saver ❤ thank you for covering this huge amount of concepts in complexity theory ❤
Thank you so much sir.
You are doing a great service .
Ritesh Yadav you're very welcome!
Thanks for the video!
Awesome sir ! thanks a lot
Thanks!
how would you convert that NFA into a DFA? is there an easy trick?
Can you use pumping lemma theorem to prove that regular languages are closed under reversal?
Not sure how that would be possible. Note that to apply the pumping lemma we have to know the language L is regular to start with. But even under that case, suppose a string w is in L and |w| >= p. Then w can be decomposed into xyz. I suppose you now know that z^R y^R x^R is in the "reversal" language, but that can be deduced from the fact that xyz is in L anyways.
Next?