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