Quotient Languages (Cool Regular Language Closure Property!)

Here we look at "quotient languages" and show an advanced topic in theory of computation - that we can show a DFA exists without knowing how to produce it. Moreover, we show that regular languages are closed under quotient, but also closed under quotient with any language at all!

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀

▶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.

[jackmccarthy]

Correct me if I'm wrong, but this doesn't really seem like a non-constructive proof. You're still showing that the quotient language is regular by constructing a DFA. It's true that the resulting DFA is dependent on the given language L, but that is to be expected—just as the product construction, powerset construction, etc. all depend on the input languages. They still are "constructive" in the sense that they demonstrate an algorithm for constructing the DFA.

A truly non-constructive proof would not even attempt to create a DFA based on R and L, but would simply show that a DFA must theoretically exist due to certain mathematical necessities.

[davidruiz]

Thank you so much! Very cool proof and very well explained.