My program knows your language. Does yours?
JavaScript, 118 bytes

m=&gt;g=c=&gt;(i=0,c=[...new Set([].concat(...c.map(n=&gt;[...n].find(x=&gt;k=m[o=x])?k.map(t=&gt;n.replace(o,t,i=1)):n)))],i?g(c):c)




f=

m=&gt;g=c=&gt;(i=0,c=[...new Set([].concat(...c.map(n=&gt;[...n].find(x=&gt;k=m[o=x])?k.map(t=&gt;n.replace(o,t,i=1)):n)))],i?g(c):c)

print = x =&gt; console.log(JSON.stringify(x))
print(f({S:['a','B'],B:['g','k']})(['S']))
print(f({S:['aE', 'bE', 'c'], E:['ab', 'aC'], C:['a', 'b', 'c']})(['S']))
print(f({A:['B','C','D'],B:['c','d'],C:['b','d'],D:['b','c']})(['A']))
print(f({'~':['`','^','/'],'/':['`^','``'],'^':['``','```']})(['~']))
print(f({A:['1','2','3'], '+':['A','B','C']})(['+']))