1
$\begingroup$

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?

$\endgroup$
2
  • 3
    $\begingroup$ Regular expressions are DFAs, what you are looking for is intersection of DFAs. $\endgroup$
    – Apoorv
    Feb 5, 2020 at 4:03
  • $\begingroup$ Patterns and automata correspond to languages, what you are looking for is (one property of one) intersection of languages. $\endgroup$
    – greybeard
    Feb 5, 2020 at 8:20

1 Answer 1

1
$\begingroup$

The language-theoretic answer:

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.

The pragmatic answer:

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.

$\endgroup$
4
  • $\begingroup$ (Every pattern has the form $α*β*γ$ - can you help me see that for *a*z*?) $\endgroup$
    – greybeard
    Feb 5, 2020 at 8:18
  • 1
    $\begingroup$ @greybeard, $\alpha$ is the empty string, $\gamma$ is the empty string, $\beta$ is a*z. $\endgroup$
    – D.W.
    Feb 5, 2020 at 8:21
  • $\begingroup$ 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. $\endgroup$
    – vonbrand
    Feb 5, 2020 at 23:29
  • $\begingroup$ @vonbrand, the product of the lengths of the patterns is exponential (in the number of patterns), isn't it? $\endgroup$
    – D.W.
    Feb 6, 2020 at 5:18

Your Answer

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

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