Finding Regular Expressions
Context: FIT2014_MOC · going from a description of a language to a regular expression for it · the assessable half of Regular Expressions (Assignment 1) Problem it solves: given English like “all strings that start and end with ”, produce a correct regular expression.
Quick Revision
- 🎯 Trigger: an English description of a string set ➔ identify the shape (contains / starts / ends / order / count), then assemble from the recipe table.
- ⚡ Key Constraint: check the smallest strings — especially and single letters. Most wrong answers fail on the shortest cases, not the long ones.
📐 Recipe table (over )
| Language description | Regular expression |
|---|---|
| all strings (universal language) | |
| contains the substring | |
| starts with | |
| ends with | |
| starting at the third letter | |
| starts with and ends with | |
| starts and ends with | ⚠ |
| two different adjacent letters (contains or ) | |
| any number of s followed by any number of s |
- The starred trap ➔ alone is wrong: it needs two s, so it misses the single-letter string , which does start and end with . Hence the extra alternative .
🧠 Five tips (from the lecture)
- Look for interactions ➔ between the patterns used to define the language; conditions can overlap or conflict.
- Check the very smallest strings ➔ especially , , .
- Read the description carefully ➔ be sure what each part means in terms of strings.
- Watch the ordering ➔ for multiple patterns, check whether the wording constrains their order.
- Ask how strings are built up ➔ this reveals which operation was applied last, which is the top of the parse tree.
✍️ Practice
Practice 1: EVEN-EVEN — all strings where and each occur an even number of times.
Reference solution
- Key move: either add a pair of the same letter (/, keeping both parities), or two mixed blocks that each flip both parities, with same-letter pairs allowed between them. The outer (including zero copies) supplies .
Practice 2: Build a regular expression for a floating-point number — one or more digits, optionally signed with , optionally containing a decimal point.
Reference solution
Build it up in named layers:
- Key move: name intermediate expressions (, , ) and compose. (not ) enforces “one or more”. Enumerate where the point may sit.
Practice 3: All strings that start and end with .
Reference solution
- Key move: the same edge case as “starts and ends with ” — the string itself satisfies both conditions with a single occurrence, so it needs its own alternative.
⚠️ Common Mistakes
- 💡 Overlapping start/end conditions ➔ “starts and ends with ” is satisfied by alone; a naive demands two copies. Add the alternative.
- 💡 silently admits ➔ if the description says “one or more”, use .
- 💡 “Followed by” means concatenation, not union ➔ is ordered; it does not describe strings with equal counts, nor arbitrary interleavings.
- 💡 Fixed positions need explicit letters ➔ ” starting at the third letter” needs two explicit placeholders, not a star.
🧠 Active Recall
Why is wrong for "strings that start and end with "?
Answer
- Short answer: it forces two distinct s (one at each end), so it excludes the one-letter string — which does start with and end with . Correct: .
- Why: Check the smallest strings ➔ when two positional conditions can be met by the same symbol, the minimal case needs its own alternative — the single most common source of lost marks.