Quick sketching....
You could have a game to teach people regular expressions. It might even actually be fun. I don't know if anything like this has already been done (a very quick look doesn't seem to show anything like it), but here's one way it could be done.
It might be a war between alien forces. You are commanding one side.
The enemy march in a single line in from the right side of the screen, and as the commander of your side your goal is to stop their troops reaching the left side of the screen. You can send out troops from the left side to attack the right side.
There are some number of diff types of enemy troops, and at your disposal you have specialist troops, each one of which can pick of a particular type of enemy troop.
So if the front of their line of troops is a 'green' alien, you send out a 'green' soldier. your troops will always win, as long as you send out the right type.
So you could just play by sending out the right sequence of troop colours...
But then their troops start moving faster and it gets harder to take our their troops one by one.
Luckily there are patterns in the troops... the front of their line might be one green soldier, followed by five blue soldiers, ending with a red soldier
So if you can set up a single command for 'one green', 'one or more blue', 'one red'.
What i'm talking about so far is like a regular expression where you are matching specific characters; they can also match classes of characters, like 'whitespace' or 'word characters' or you can have character classes...
And the game could gently introduce the ability for the player to have such higher-level control... e.g. some of the enemy might be carrying shields... blue ones with shields, red ones with shields and so on... so your 'attack specification' could allow the player to deal with more abstract classes like this.
Ideally, the game would give the player a gentle ramp up to the sort of abstraction regular expressions afford. the player could handle things fully manually... by manually specifying the pattern to meet... and then they would appreciate the ability to handle it in a higher-level way.
The player should be rewarded by being able to take out as many enemy as possible in the one command (the one reg-ex)... the more they take out, the more spectacular it should look, and perhaps the more points they would get (if there were points).
Here's some other ideas.
I can even imagine building a 'search and replace' mechanism into the game... perhaps the 'search' pattern could be use to specify what to target and the 'replace' pattern what weapons to use on each of those targets.
In addition to the idea of a game based around the idea of regular expressions, I might be actually use them to provide powerful input mechanisms in existing sorts of games... real-time strategy games strike me as a possibility.