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

572 Views Asked by At

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