2020 January 17,
Carleton College, Joshua R. Davis
It turns out that Python regular expressions (PREs) are more powerful than textbook regular expressions (TREs). That is, there exists a PRE such that, when you use it in the matches function from our Python regular expression tutorial, the strings that it matches do not constitute a regular language.
A. Working over the alphabet Σ = {0, 1}, find such a PRE. That is, your PRE should match no strings that contain any characters other than 0 and 1. Try to make your example small and simple. (Mine is seven characters.) Explain what language it matches. Prove that the language is not regular. Submit your answer on paper.
Want a hint? .egaugnal ralucitrap siht deiduts ton evah ew tub ,raluger-non eb ot ssalc ni devorp evah ew taht segaugnal ot ralimis si fo gnikniht m'I egaugnal ehT .puorg a esU