2
$\begingroup$

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

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

Your Answer

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

Browse other questions tagged or ask your own question.