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

  • 1
    $\begingroup$ This is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – FrankW Mar 20 '14 at 0:34
  • $\begingroup$ Not my intent -- I'm actually working on improving the question right now and working towards a solution. I tend to edit my posts heavily afterwards, I can never settle on what to put in a first draft. $\endgroup$ – Musicode Mar 20 '14 at 0:46
  • $\begingroup$ Cross-posted on cstheory.se: cstheory.stackexchange.com/questions/21636/…. $\endgroup$ – Yuval Filmus Mar 20 '14 at 2:19
  • $\begingroup$ Please try to finish your post in one sitting; having many revisions is bad (see e.g. this discussion). I think we'll keep your question closed until you finish writing up 2. and actually pose a question. See here for helpful tools. $\endgroup$ – Raphael Mar 20 '14 at 13:36
  • $\begingroup$ Regarding your attempt 1., think closely about which language you accept if you add loops to all states. Is it really $L_+$? $\endgroup$ – Raphael Mar 20 '14 at 13:37

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$.

| cite | improve this answer | |
  • $\begingroup$ Why not? The new PDA isn't aware of the distinction. $\endgroup$ – Yuval Filmus Oct 10 '17 at 6:01

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$.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.