Given a set of strings $H$, I wish to find a minimal size set of strings $G$ that "generates" $H$ in the sense that any string in $H$ can be formed by concatenating strings from $G$ ($G$ can be $H$ itself, so we have $|H|$ as upper bound).
For example, if $H=<abef,abeg,acef,aceg,adef,adeg>$ then $G=<ab,ac,ad,ef,eg>$ generates $H$ and has size 5 which is minimal. $G'=<abe,ace,ade,f,g>$ is also a generating set with size 5.
If $H=<ab,ac,ad,bc,bd,cd>$ than $G=<a,b,c,d>$ generates $H$ and has size 4 which is minimal.
Is it NP hard?