Write a CFG acceptor
Python 2.7, 325 chars

R=['S','SaSb']
I='aaabbb'

L=len(I)
def P(x,y,n):
 if n&lt;3:return[[x,y]][:n&gt;1or x==y]
 return[[x]+w for z in range(x,y+1)for w in P(z,y,n-1)]
S={(i,i+1,c):1for i,c in enumerate(I)}
T=0
while S!=T:
 T=dict(S)
 for r in R:
  for a,x,y,b in P(0,L,4):
   if any(all(t in S for t in zip(p,p[1:],r[1:]))for p in P(x,y,len(r))):S[x,y,r[0]]=1
print(0,L,'S')in S


The rules are listed in R and the input is in I.

The code uses dynamic programming, similar to the Earley algorithm.  S contains tuples (i,j,N) if the symbol N can generate the input from indexes i to j.  We iterate through all rules and indexes looking for new entries we can put in S.

P is a helper function that calculates all possible partitions of the range [x,y] into n-1 ranges (assigning one symbol in the rule to each).  For instance, P(0,7,4) contains, among many others, [0,3,6,7].

The run time is exponential in the longest rule, but shouldn't be too bad in the number of rules and length of the input.