Pattern Matching and Regular Expressions

Here are some interesting and important questions: How hard is it to determine whether a given string x matches a given pattern a? This is an important practical question. There are very efficient algorithms, as we will see.Is every set represented by some pattern? Answer: no. For example, the set is not represented by any pattern. We’ll prove this later.Patterns α and β are equivalent if L(α) = L(β). How do you tell whether α and β are equivalent? Sometimes it is obvious and sometimes notWhich operators are redundant? For example, we can get rid of ∈ since it is equivalent to ∼(#@) and also to φ*. We can get rid of @ since it is equivalent to #*. We can get rid of unary + since α+ is equivalent to αα*. We can get rid of #, since if Σ = {α₁, ..., α_n} then # is equivalent to the pattern {ie44-2}.