# Determining if match is possible

I have a list of patterns with each pattern containing one or more wildcards. For example:

• abc*
• a*
• *a*z*
• *z

Wildcard (*) matches one or more characters. For example, any input string starting with 'a' would match a pattern a*.

How can I determine if there exists an input string that would match all of the provided patterns?

• Regular expressions are DFAs, what you are looking for is intersection of DFAs. Feb 5, 2020 at 4:03
• Patterns and automata correspond to languages, what you are looking for is (one property of one) intersection of languages. Feb 5, 2020 at 8:20

Convert each regexp to a DFA, then use the product construction to take the intersection of their languages. Check whether the resulting DFA accepts any word (i.e., whether its language is non-empty). This might take exponential time in the worst case.

Every pattern has the form $$\alpha \texttt{*} \beta \texttt{*} \gamma$$, where $$\alpha,\gamma$$ are (possibly empty) strings of letters (without wildcards), and where $$\beta$$ is a (possibly empty) pattern (i.e., a string of letters and wildcards). Let the patterns be $$\alpha_i \texttt{*} \beta_i \texttt{*} \gamma_i$$ for $$i=1,2,\dots,n$$. Find a string $$A$$ so that each $$\alpha_i$$ is a prefix of $$A$$; if no such string exists, output "NO" and terminate. Find a string $$C$$ so that each $$\gamma_i$$ is a prefix of $$C$$; if no such string exists, output "NO" and terminate. Find a string $$B$$ that matches $$\texttt{*} \beta_i \texttt{*}$$ for each $$i$$; this can always be done. Finally, output "YES" and the string $$ABC$$.

This is your exercise, so I'll let you figure out how to find each of $$A$$, $$B$$, and $$C$$ -- it's not hard.

• (Every pattern has the form $α*β*γ$ - can you help me see that for *a*z*?) Feb 5, 2020 at 8:18
• @greybeard, $\alpha$ is the empty string, $\gamma$ is the empty string, $\beta$ is a*z.
– D.W.
Feb 5, 2020 at 8:21
• For this case you won't get into exponential behavior. Building DFAs directly is straightforward, the product DFA will be of around the product of the lengths of the patterns, not too costly. Feb 5, 2020 at 23:29
• @vonbrand, the product of the lengths of the patterns is exponential (in the number of patterns), isn't it?
– D.W.
Feb 6, 2020 at 5:18