[Solved]: Proving that context-free languages are closed under inserting symbols

Problem Detail: 

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:

1. 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).

Asked By : Musicode

Answered By : Yuval Filmus

Two ways of proving this come to mind: using push-down automata and using grammars.

Using push-down automata

Consider a PDA for some context-free language. The idea is to modify the PDA so that it has to "swallow" one character at some arbitrary moment. Here we use the non-deterministic nature of PDAs. In order to implement this idea, duplicate the set of states of the PDA. Each set of states has the usual transitions, the initial state resides in the first set, and we retain the accepting states only in the second set. In addition, for each state $q$ we connect the copy of $q$ in the first set to its copy in the second set with an arc labelled $\Sigma$. This is the non-deterministic "swallowing" of one character.

Using grammars

We can do a similar thing using grammars. Consider a context-free grammar in Chomsky normal form for some language (the transformation is easier to describe for Chomsky normal form, but can also be done directly). Each non-terminal now comes in two flavors: unmarked $A$ and marked $A'$. The initial symbol is $S'$ (where $S$ is the initial symbol of the original grammar). For each transition $A \to BC$ we include the following transitions in the grammar: $$ \begin{align*} &A \to BC \\ &A' \to B'C \\ &A' \to BC' \end{align*} $$ For each transition $A \to a$ we include the following transitions in the grammar: $$ \begin{align*} &A \to a \\ &A' \to \sigma a | a \sigma \text{ for every } \sigma \in \Sigma \end{align*} $$ The marked version of each non-terminal codes that the extra character lies within the subtree generated by this non-terminal. The addition of the extra character itself is handled by the rules $A' \to \sigma a | a \sigma$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22834