Question

Let $\mathit{\Sigma }\mathbf{2}$ be the same as in Problem 1.33. Consider the top and bottom rows to be strings of 0s and 1s, and let$\mathit{E}\mathbf{=}\mathbf{\{}\mathit{w}\mathbf{\in }\mathbf{\sum }\mathbf{*}\mathbf{2}\mathbf{|}$ the bottom row of w is the reverse of the top row of w}. Show that is E not regular.

Short answer

The given language L is not a regular language.

Step-by-step solution

Consider the expression E is regular

Expression is not regular

Consider that

Proof:The bottom row of the string is the reverse of the top row of the string.

In order to prove that bottom row of string is the reverse of the top row of the string user need to prove this with the help of contradiction.

First it is to be assumed that the expression E is a regular language.

To prove that

Suppose, the constant variable p is associated with expression E

Choose the string. This is because $s\in L$.

Now, the string s is being partitioned into three pieces such that,

$s=xyz$where $p⩾q$

For any division of $y=uvw$, the value of $v={\left[\begin{array}{c}1\\ 0\end{array}\right]}^m$but the condition is that $0<m⩽p$

For any value of $i⩾0$, suppose value of i is assumed to be 2.

$s=xyz$

Now, putting the value of y here,

Because$m>0$and$1^{p+m}{0}^p\ne (0^{p+m}{1}^p{)}^R$

By the above contradiction, it is being proved that the top row of the string is not the reverse of the bottom row of the string.

This implies,$xu{v}^{2}wz\in L$

Thus, by the pumping lemma of proof by contradiction, it is being proved that the given language L is not a regular language.