= Solution
Take
$$
G=(\{a,b,c\},\{S,A,B\},
\{S\to AB,\ A\to a,\ B\to b\},S)
$$
and
$$
G'=(\{a,b,c\},\{T\},\{T\to c\},T).
$$
These are variable based and have disjoint variable sets. They satisfy
$$
L(G)L(G')=\{abc\}.
$$
In $H^{\mathrm{reg}}$, however, both terminal productions of $G$ are replaced:
$$
A\to aT,\qquad B\to bT.
$$
Consequently its only terminal derivation is
$$
S\Rightarrow AB\Rightarrow aTB\Rightarrow aTbT
\Rightarrow acbc,
$$
so
$$
L(H^{\mathrm{reg}})=\{acbc\}\ne\{abc\}.
$$
This realizes the <failure of the regular concatenation construction for a nonregular grammar>: two different terminal productions introduce two copies of $T$.
Back to article page
