title: The Complexity of (simplified) Regex Matching
body: <p>I just wonder the complexity of this regex matching problem: given a string of small letters and a matching rule, determine whether the rule may match the WHOLE string. The rule is a simplified regex which only contains smaller letters and/or '.' (period) and/or '*' (asterisk). A period may match any small letter where an asterisk may match zero or more of the preceding element.</p>
  
  <p>Here are some examples:</p>
  
  <ul>
  <li>isMatch("aa","a") is false</li>
  <li>isMatch("aa","aa") is true</li>
  <li>isMatch("aaa","aa") is false</li>
  <li>isMatch("aa", "a*") is true</li>
  <li>isMatch("aa", ".*") is true</li>
  <li>isMatch("ab", ".*") is true</li>
  <li>isMatch("aab", "c*a*b") is true</li>
  </ul>
  
  <p>It is said that this problem could be solved in polynomial time. I just wonder how. By intuition, matching "aaaaaaaaaa" with a regex like ".*a.*" makes it hard to decide state transition when match with a finite deterministic machine. Any comments?</p>
  
  <p>Thank you. </p>