# Context-free grammar of the concatenation of a string S and subsequence of reversed S

I have to find a Context-Free grammar that generates the language:

$$L_1 = \{x\#y\ |\ y$$ is a subsequence of $$x^R$$, and $$x\in\{a,b\}^*\}$$, $$\Sigma=\{a,b,\#\}$$

The concatenation of two mutually reversed strings are pretty simple, but I just can't figure out how to express "plugging in random terminals in $$x$$" so that $$x^R$$ could contain $$y$$ as its subsequence.

Let me start with a grammar for the language of words of the form $$x\#x^R$$: $$S \to aSa \mid bSb \mid \#$$ This is our starting point. Now there are two interpretations of the term subsequence. Under the first interpretation, a subsequence is obtained by removing any number of symbols. This just means that we can omit the second side of each production of the form $$S \to \sigma S \sigma$$, resulting in the grammar $$S \to aSa \mid bSb \mid aS \mid bS \mid \#$$ Under the second interpretation, the subsequence must be contiguous. Each derivation should therefore be in three steps: first only on the left side, then on both sides, then finally again only on the left side. This requires three nonterminals, and results in the following grammar: $$S \to aS \mid bS \mid T \\ T \to aTa \mid bTb \mid U \\ U \to aU \mid bU \mid \#$$

• Comments are not for extended discussion; this conversation about the definition of the word subsequence has been moved to chat. Aug 6 '19 at 21:14

"Plugging in random terminals in $$x$$" is the right approach.

To implement that, we need to understand clearly how we have achieved "the concatenation of two mutually reversed strings" first. It is done by growing a string from both ends with the same symbol repeatedly, a characteristic technique for context-free grammar, as illustrated below.

$$\begin{array}{ccc} &\#&\\ &a\#a&\\ &ba\#ab&\\ &bba\#abb\\ &abba\#abba\\ &babba\#abbab \end{array}$$

To plugging in random terminals on the left hand side, we can grow the left hand side without growing the right hand side.

Starting from $$\#$$, we will either add the same symbol to both side, or add a symbol to the left hand side only. Hence the following simple grammar.

$$S\to\#\mid aSa\mid bSb\mid aS\mid bS$$

Here is an easy exercise.

Exercise. find a context-free grammar that generates this language, $$\{xy\mid x,y\in\{a,b\}^*$$ $$\text{where }x$$ $$\text{with some }a\text{'s removed is the same as}$$ $$y\text{ with some}$$ $$b\text{'s removed}\}$$.

Here's how I'd approach this:

• Make a grammar that can produce palindromes
• Make a grammar that can produce "any sequence of as and bs followed by #"
• Make a grammar that can produce "any sequence of as and bs"

Then combine the three. $$L_1$$ is:

• Any sequence of as and bs
• The first half of a palindrome
• Any sequence of as and bs followed by #
• The second half of the palindrome

Giving something like this:

S → G P ; gibberish, followed by modified palindrome

P → a P a ; standard palindrome grammar
P → b P b
P → G # ; but instead of ∅ in its center, it has gibberish followed by #

G → a G ; produces any sequence of a's and b's
G → b G
G → ∅


(There are a few different notations for CFGs, so in case this isn't the one you're used to: S is always the starting symbol, ∅ means the empty string, and everything after a ; is a "comment" that doesn't affect the grammar.)

EDIT: It's been pointed out that you want a reversed subsequence, not a reversed substring. But this is easy to fix: just allow adding arbitrary gibberish on the left side of the "palindrome" part.

P → G P


You can then simplify the starting rule:

S → P


Everything else should remain the same.

• "Subsequence" usually means "a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements." (Quote taken from Wikipedia.)
– rici
Aug 6 '19 at 3:59
• @rici Ah, I read "substring"! My bad, I'll correct my grammar. Aug 6 '19 at 15:40