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