# prove that your language is not regular by using the Pumping Lemma, $L = \{x \in \{0, 1\}^* | x = x^R \}$

prove that your language is not regular by using the Pumping Lemma, $$L = \{x \in \{0, 1\}^* | x = x^R \}$$

proof:

Let $$L = \{x \in \{0, 1\}^* | x = x^R \}$$

Suppose L is a regular language

let $$x = 0^n10^n$$

$$x \in L$$ because definition

$$(ii)$$ $$|x| = n + 1 + n = 2n + 1 \geq n$$

then pumping lemma tells us $$\exists u, v, w \in \{0, 1\}^*$$ such that

$$(i) = x = uvw$$

$$(ii) v \neq \epsilon$$

$$(iii) |uv| \leq n$$

$$(iv) uv^k w \in L$$ for all $$k \in \mathbb N$$

let $$u = 0^i, v = 0^j, w = 0^t10^n$$ where $$i \geq 0, j \geq 1, t \geq 0, i + j \leq n$$

$$i + j + t = n$$

let $$k = 2, uv^2w \in L$$

$$uvvw = 0^{i+j+j+t}10^n = 0^{n+j}10^n$$

since $$j \geq 1$$

$$(0^{n+j}10^n) = 0^n10^{n+j} \neq 0^{n+j}10^n$$

this is a contradiction, therefore L is not a regular language

• Is $x^R$ the reverse string of $x$? – Saucy O'Path Nov 5 '18 at 22:58
• Yes it does. abc = cba – Tree Garen Nov 5 '18 at 22:59
• Ok. More accurately, the operation defined by structural recursion as $\epsilon^R=\epsilon$ and $(Xc)^R=cX^R$ when $c$ is in the alphabet. – Saucy O'Path Nov 5 '18 at 23:11
• And what is your question? – Berci Nov 6 '18 at 1:05
• whether it's correct or not – Tree Garen Nov 6 '18 at 1:20