Schützenberger’s Theorem: First-order definability of regular languages
Date:
I gave this talk for the McMaster-Waterloo Joint Model Theory Seminar. I introduced some basic background in the theory of formal languages and presented a proof of Schützenberger’s Theorem which demonstrates that a regular string language is first-order definable if and only if it is definable by a star-free regular expression.