Undecidable Languages - Easy Theory

Currently Playing: Minimal Context-Free Grammars are Undecidable

Here we show that minimal CFGs are recognizable and undecidable via a reduction from the Post Correspondence Problem. NOTE: in the explanation of G being minimal at the end, I meant to add that we only need to consider strings not in L1 that do not contain a $ symbol, as the inverse homomorphism of L2 will insert rules into G2 of the form X goes to $X | epsilon. What is a context-free grammar? It is a set of 4 items: a set of "variables," a set of "terminals," a "start variable," and a set of rules. Each rule must involve a single variable on its "left side", and any combination of variables and terminals on its right side. See https://www.youtube.com/watch?v=h1OSmLSacNA&ab_channel=EasyTheory for more details. 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.