Teaching students how to construct regular expressions (and other "translation" style problems)

Question

I'm currently helping teach a unit about languages as a part of a discrete math course -- we're currently focusing on regular expressions, NFAs, DFAs, CFGs, grammars, and the like.

One of the skills we'd like students to be able to acquire is the ability to translate English into equivalent regular expressions -- e.g. translate phrases like "match all strings containing an even number of the character 'a'" or "match all binary strings that do not contain the string '1001'".

Some students seem to easily pick up the "knack" of performing these sorts of translations, but many more of them seem to struggle.

Unfortunately, I'm not sure how to best help these students. Constructing regular expressions isn't usually something I find particularly difficult, so I've been finding it difficult to "get into the mindset" of the students who find writing regular expressions to be less obvious.

I've spent some time introspecting and trying to pick apart what strategies I subconsciously tend to use when faced with a new problem, but that's mostly yielded a list of ad-hoc strategies rather then anything fundamental.

---

Something I feel I should note is that I don't think unfamiliarity with syntax is likely to be the culprit. We're starting by studying specifically regular expressions (not regex) and have restricted ourselves to using a very minimal toolset: union, concatenation, the Kleene star, and epsilons -- so, no backreferences, no captures, nothing like that.

Rather, it seems what students find most difficult is the inherent act of interpreting and translating an English sentence and formalizing it into some logical form.

I've seen this same sort difficulty of manifest appear in other scenarios: for example, earlier this quarter, we asked students to translate English into propositional or predicate logic: I also found it difficult to teach students how to do this in any kind of systematic way. As another example, in other courses, I've observed many students find it challenging to translate English into SQL queries (and here I have some more sympathy, since I also find constructing certain kinds of SQL queries to be challenging).

The best I've been able to do so far is just have students do a bunch of practice/walk through a bunch of examples, but that doesn't strike me as being a particularly efficient strategy (though I don't dispute that practice is essential).

---

This brings me to the core of my question: How can I more effectively help students master the meta-skill of "translation"/"formalization"? I'd welcome both answers focusing on strategies for helping students more effectively construct regular expressions as well as answers focusing on helping students acquire this meta-skill in a more general sense. Answers that can give me more nuanced insight what sorts of things students find difficult about these types of problems would also be welcome.

Note: somebody asked a similar question to this one about helping students who are familiar with Java learn regex. However, that question seems to focus more on how to best teach the nuts and bolts of regex-the-language; my question is more about how to teach the meta-skill of "translation/formalization".

Answer 1

This is the stuff of math teachers' nightmares. The problems here, from my experience teaching about grammars¹, are two-fold:

1. You said that syntax is probably not the culprit here. Students may be able to follow a grammar that has been presented to them, but may not be able to generate an appropriate grammar for a given series of test cases.

2. Students may not be able to generate appropriate test cases from the word problem itself.

The good news is that, by breaking it down into these two steps instead of one, you can actually help to isolate the problem that your students are having.

If you see your students frequently (as I do), here's a fix-up strategy that you can do in about 30 minutes of class time over three days. Create a worksheet with a series of word problems, and ask the students, as homework, to generate test cases for these hypothetical machines. They are not to create the grammars themselves, only create a series of test cases that should be accepted or not accepted. Emphasize that redundancy is not a goal; you want a minimal set of test cases that could guarantee that some grammar is entirely correct.

The next day, spend about 15 minutes going over two of the problems, round-robin style, at the board. Ask a student to write a test case for the first problem. Turn to the second student, and ask them to write another test on the board that could potentially uncover new ground. On to the third student, fourth student, etc., until you are satisfied that you have a good testing set. Ask if anyone else has any important tests remaining.

Do the same for the second problem, and then discuss the importance (in general) of creating good test sets upon encountering a word problem. Point out that they will receive word problems on their assessment at the end of the unit, and you expect them to be able to figure out a good set of test cases with which to design a grammar at that time.

Their homework for that second day is to fix up their tests (if they need more work), and to create the appropriate grammars. I suspect that when you get this homework back on day 3, you'll have much stronger results.

^{1 - I am using "grammar" as a stand in for "grammars, regexes, FSAs, or whatever type of expression/machine you are trying to get them to create at some particular moment."}

Answer 2

This suggestion is, I'm afraid, highly speculative and untried. But I'd be tempted at least to give out an assignment of the following form, perhaps using a structure like that suggested by @BenI. here.

Prepare a numbered list of exercises from quite simple (in your estimation) to quite complex. The numbers correlate directly to the difficulty. Tell the students that they can do any number of them (say at least three) that they wish and that the grade will depend only on the most difficult one they get correct.

The justification for the structure is that the students who get these easy will just work on a few of the harder ones and the ones that struggle will start farther down your list and work until they feel a bit confident. The students who need the most work will, hopefully, get the most practice. The rating by difficulty can also help them get "into the flow."

In the exercises I'd also stress a variety of vocabulary for things so that they get some practice in matching human language to the technical forms. You could even try to state each exercise two different ways to help students with the correlations, but you need to be careful that your explanations of the requirements really are equivalent.