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 \# $$

  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation about the definition of the word subsequence has been moved to chat. $\endgroup$ 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.

  • 1
    $\begingroup$ "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.) $\endgroup$
    – rici
    Aug 6 '19 at 3:59
  • $\begingroup$ @rici Ah, I read "substring"! My bad, I'll correct my grammar. $\endgroup$
    – Draconis
    Aug 6 '19 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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