Proving that context-free languages are closed under inserting symbols This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation.  This means basically that any context-free language which undergoes this operation would still be context-free.


  For a language $A$ which is a subset $\Sigma^*$, define the language $A_+$ as
  
  $\qquad\displaystyle A_+ = \{xyz | y\in \Sigma \wedge xz \in A\}$.
  
  Prove that the set of context-free languages is closed under the $+$ operator.


So $A_+$ contains all strings that can be obtained by inserting one symbol into a string in $A$.
Show that the class of context-free languages is closed under the operation $+$ (i.e.,     show that
if $A$ is context free, then $A_+$ is also context free).

Note that this is not a homework question.  Examples of closure proofs are sparse online and in my textbook.  

First, let's think about the different ways to prove closure of CFLs:  


Constructing a "template" Push Down Automata that can incorporate any other Push Down Automata and add on a part to the beginning, middle, or end of the PDA and still be able to accept the language accepted by the original CFL, with the new operation on it.  Basically, if for any given PDA P, if a PDA P' can be created which accepts the language of P with the new operation (in our case, the "+" operator) performed on it, then that operation must be under closure.  

Solving the problem in this manner is quite simple to think about.  Imagine a PDA P which accepts strings from the CFL L.  In application to our problem, this would be a PDA which can successfully read in the string 'xz', where x and z are simply any string conforming to our alphabet.  The PDA P' would similarly have the ability to read xz, but each state of the PDA could have an additional self loop which reads the character in the string y.


I have selected the answer which I find to be most appropriate for this question.  It simply involves using the "tempate PDA" strategy which I outline above; however, my construction did not achieve the goals of the new language (think about why before looking at the answer below).
Using closure under GSM mappings

Whenever possible, it may be faster to prove closure properties from
other known closure properties, That is why there has been a
systematic study of closure properties (see AFL, full AFL, trios,
...). This is somewhat developed in the Hopcroft-Ullman textbook,
ed. 1978).

For this problem, the insertion of a single character from the alphabet in the strings of a
language can be trivially performed by application of a
GSM-mapping. Since CF languages (and many others) are closed under
GSM-mapping, they are closed under the $+$ operator.

If you do not know about GSM mappings, you can do it with closure
under intersection with regular sets, homomorphism and inverse
homomorphism. That is actually how closure under GSM mapping is
proved.

Assuming your original alphabet is called $\Sigma$, you create a new
alphabet $\hat\Sigma=\{\hat a \mid a\in \Sigma\}$, i.e. a new set of
symbols in 1-1 correspondance with $\Sigma$.  Using the inverse of a
homomorphism (that simply erases $\hat\Sigma$), you insert an arbitrary
number of $\hat\Sigma$ symbols in the string.  Then you intersect the
result with the regular set $\{w\in (\Sigma\cup\hat\Sigma)^*\mid
|w|_{\hat\Sigma}=1\}$, so as to allow the insertion of only one
symbol from $\hat\Sigma$. Then you remove the hat with a homomorphism $\phi$ such
that $\forall \hat a \in \hat\Sigma,\, \phi(\hat a)= a$.