There are given:
- alphabet $Σ$ with some symbols $a,b$.
- list of forbidden patterns
Result: Is there exists word of form $a\Sigma^*b$ such that it doesn't contains (as subword) any of word from list (list contains many words, expressed by patterns). Show that this problem is in $PSPACE$.
Example to better understand patterns: $bbaaacb$ contains a word $a??c$, but $aacba$ doesn't contain $a??c$, where $?$ is some special symbol in $\Sigma$
So patterns are like words with holes (?)
My approach is follwing:
Let $k$ will be max length among all patterns. There is no sense to consider longer words than $k$ because if exists word longer than $k$ such that it contain none of words from forbidden list then also exists word of length $k$.
So, using the fact that $PSPACE = NPSPACE$ we can guess word of length $i=1...k$ and check if it contains subword from forbidden list. Matching is easy to do in $NPSPACE$.
I am not sure about corectness of using nondeterminism. What do you think ?