>> Yes, AFAIK it's impossible to match ".*%b()" in linear time. That
>> message was regarding FSA to match "%b()". So I was wrong. It's possible to match ".*%b()" in linear time.
It is almost equivalent of matching "()". Thank you for showing it!
You can match this particular _expression_ in linear time going from right to left, because the language of the reverse string ("^%b().*$") is a LR(1) language.
Here's another problem:
This won't match if the number of b's is larger than the sum of the numbers of a's and c's. And "%bab" matches "a-+abb", for instance, whereas "a*" won't match any letters except 'a'.
So of course there's an ad-hoc linear time algorithm to match this, but the point is: can we come up with a matching algorithm that writes that ad-hoc algorithm automatically, i.e. can we solve the general case?