Here we ask the question about what "efficient" computation should be, as well as give definitions of P (deterministic polynomial time) and NP (nondeterministic polynomial time). Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs #easytheory Youtube Live Streaming (Sundays) - subscribe for when these occur. Social Media: Facebook Page: https://www.facebook.com/easytheory/ Facebook group: https://www.facebook.com/groups/easytheory/ Twitter: https://twitter.com/EasyTheory Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶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 many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=UhYWLzuYW54

Here we consider the problem of intersecting a CFL and a regular language without using a PDA! It turns out that it is possible to do this directly, with a CFG and a DFA. The idea is simple, but we have to make some modifications first (the CFG has to be in CNF, and the DFA has to be an NFA with exactly 1 final state). Then we do a product-type construction that is similar to the PDA to CFG conversion. The variables model pairs of states in the NFA (representing starting and destination states), as well as a variable in the original grammar. This "triplet" variable then should generate all strings that drive the NFA from the given start to the destination state, as well as a string that the given variable can generate. At the end, we generate the rules that come out of the intersection by considering the three cases that grammars in CNF can have. Patreon: https://www.patreon.com/easytheory Facebook: https://www.facebook.com/easytheory/ Twitter: https://twitter.com/EasyTheory If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶ADDITIONAL QUESTIONS◀ 1. What fundamental problems can arise with this method if we did a CFG intersect a CFG here? 2. Is it possible to remove the constraint for the DFA/NFA have exactly 1 final state? ▶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 ... https://www.youtube.com/watch?v=fiipLIVwR9o

Here we look at the product construction for DFAs, and show that it "ruins" everything! Specifically, about minimality and reachability of the two original DFAs. If they both had no unreachable states, we don't guarantee that about the resulting DFA. And the same is true of minimality. Patreon: https://www.patreon.com/easytheory Twitch: https://www.twitch.tv/easytheory Mixer: https://mixer.com/easytheory Discord: https://discord.gg/SD4U3hs Facebook: https://www.facebook.com/easytheory/ Twitter: https://twitter.com/EasyTheory Teespring: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶ADDITIONAL QUESTIONS◀ 1. What has to be true about the original DFAs for the product DFA to also be minimal? 2. What about for reachability? ▶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 ... https://www.youtube.com/watch?v=XBGgaXm94ew

Here we show that the equality problem for context-free grammars is undecidable, and its complement is recognizable. We utilize the fact that ALL_CFG is undecidable, and for the second proof that A_CFG is decidable. Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs #easytheory Youtube Live Streaming (Sundays) - subscribe for when these occur. Social Media: Facebook Page: https://www.facebook.com/easytheory/ Facebook group: https://www.facebook.com/groups/easytheory/ Twitter: https://twitter.com/EasyTheory Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 Gold Supporters: Micah Wood Silver Supporters: Timmy Gy ▶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 many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=13f-x7hUdu0