Deterministic Context-Free Languages Closed under Complement

Here we show that deterministic context-free languages (DCFLs) are closed under complement. They are "deterministic" so the "swap final and non-final states" idea for closure under complement for DFAs is a good idea. However, this doesn't directly work since there are epsilon transitions, and it's possible (because of the stack) that the DPDA becomes "stuck" in a state. So we fix these problems by (1) putting a $ at the beginning and going to two special states whenever we encounter the $ at a later point (these states either accept immediately or reject and read the rest of the string), (2) ensure the entire input is read, and then (3) breaking up transitions into "reading" ones and "non-reading" ones, and ensuring that once we enter a final state, we don't "leave" a final state until we encounter another reading transition.

A deterministic context-free language is the language of a deterministic pushdown automaton (DPDA). The essential idea is that a DPDA is equivalent to a PDA, except that there can only be one "choice" of transition from any state on any input, with anything on the stack. See https://www.youtube.com/watch?v=GzR5FiiIogY&ab_channel=EasyTheory for more details.

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

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=f5d1hJQZTAs