The Short Version of my Question

The following two regular expressions represent two sets of strings.


What regular expression (regex) represents the intersection of the two sets of strings?

Additional Explanation

When we allow many different abbreviations for the names of the states "IDAHO" and "ILLINOIS" which abbreviations do we have to worry about matching both state names?

In the United States, there are two states named "IDAHO" and "ILLINOIS".

People write many abbreviations for the state names on mailing envelopes and cardboard boxes.

For example, people usually write, "ID" for "IDAHO".

An example of a mailing address in shown below:

John & Jane Doe
123 Somewhere Lane
Doetown, ID  

If you accidentally delete a few letters when you try to write or type "IDAHO" or "ILLIONOIS", then at what point is your spelling of the state name unclear or ambiguous?


1 Answer 1


Answer: I?O?.

Simple justification: neither D, A, nor H appear in ILLINOIS, so they cannot appear in the intersection. That leaves only I,O.

Systematic solution: Let me teach you the general way to solve this kind of problem. Convert each regexp to a NFA, then compute the intersection of both NFAs using the product construction. Each of those two steps has standard algorithms that can be found in a good textbook on automata theory (or here on this site).

Realistic answer: The premise is faulty. No one would write AH as an abbreviation of IDAHO. It's unlikely that all but one the letters of IDAHO will be accidentally deleted/omitted, leaving only H. So a more practical solution might be to gather some data on common abbreviations of each state and build a more realistic model of in what way people write each state name.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.