Consider that the language L of all palindromes over $\Sigma = \{0,1\}^*$ is not context-free. The following is my attempt at a proof by contradiction.

I am new to proof writing and I am wondering if the proof is correct, and if it proceeds in a connected logical sequence. I think I have all the cases covered, but I am not too sure.

enter image description here

  • 3
    $\begingroup$ Could you explain why $uwy = 0^k1^{2k}o^k$? If I set $w = 1, v = x = 1$, then neither $x$ nor $v$ equals $\epsilon$, $|vwx| < p$ and $uv^iwx^iy \in L$, but $uwy$ is not of the form you state. Apart from that, there's a very simple grammar for palindromes: $w := "" | "1" | "0" | "1" w "1" | "0" w "0"$ that looks pretty context free to me $\endgroup$ – Ronald Dec 6 '18 at 0:33
  • $\begingroup$ @Ronald could you elaborate? Are you saying that the language of palindromes is context free? $\endgroup$ – SeesSound Dec 6 '18 at 1:02

If a context free grammar exists that produces the language, then the language itself is context free.

A context free grammar is a 4-tuple $G = (V, \Sigma, R, S)$ with the following properties:

  1. $V$ is a finite set; $v \in V$ is called a non-terminal symbol
  2. $\Sigma$ is a finite set of terminal symbols; $V \cap \Sigma =\emptyset$
  3. $R$ is a finite relation $V \rightarrow (V \cup \Sigma)^*$
  4. $S \in V$ is the start symbol

With $V = \{w\}$, $\Sigma = \{0, 1\}$, $S = w$ and the following map $R$:

$w \rightarrow \epsilon$
$w \rightarrow 0$
$w \rightarrow 1$
$w \rightarrow 0w0$
$w \rightarrow 1w1$

we've defined a context free grammar.

Note: if the empty string isn't considered to be a palindrome, the first production can be replaced by

$w \rightarrow 00$
$w \rightarrow 11$

Palindromes are, casually speaking, a special case of "well-formed parenthesis" (each opening parenthesis has a corresponding closing parenthesis) which is also known to be context free.

Context free languages can't "count" very well, but it isn't a problem to have an arbitrary number of matching pairs as this can be tested using a stack. But the famous language $a^nb^nc^n$ isn't context free because there's no way to count to $n$.

Strictly speaking I'll have to prove that the above grammar indeed produces the set of all palindromes.

First of all, if $w \in L$, which means that $w$ is a palindrome, then also $0w0$ and $1w1$ are palindromes and therefore member of $L$. Obviously $0, 1$ and $\epsilon$ are palindromes.
In other words, the production rules only produce palindromes.

Now assume $p$ is a palindrome. Then $p = s_1s_2...s_nms_ns_{n-1}...s_1$, with $s_i \in \{0, 1\}, i \in \{1, ..., n\}$ and $m \in \{\epsilon, 0, 1\}$.

In order to produce this palindrome, we start with $w = m$ and then consecutively add the symbols $s_n, s_{n-1}, ..., s_1$ on either side of $w$, which is allowed by the last two production rules.

This proves that $p$ can be produced by the grammar above.
Together with the fact that $G$ produces palindromes only, this proves that $G$ is a valid grammar for $L$.


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.