Question

Let$\mathit{\Sigma }\mathbf{=}\left\{0,1,+,=\right\}$ and

ADD $\mathbf{=}\left\{x=y+z|x,y,zarebinaryintegers,andxisthesumofyandz\right\}\mathbf{.}$

Show that ADD is not regular.

Short answer

It is proved that ADD is not regular language.

Step-by-step solution

Define regular languages

A language L is regular, if the length of all the strings belonging to L is greater than or equal to n. Also, there exists u, v, w∈Σ∗, such that x = uvw. And the following properties should also hold:
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uvⁱw∈L

The context free language is generated by context free grammar.

These languages are accepted by Pushdown Automata. These are the superset of regular languages.

Consider context-free languages$L_1$ described as $G_1=(V_1,S,R_1,S_1).$

Consider context-free language $L_2$described as$G_2=(V_2,S,R_2,S_2).$

Proof that ADD is not regular language

Suppose ADD is regular. Let Pbe its pumping length.

$\Sigma =\left\{0,1,+,=\right\}$

ADD$=\left\{x=y+z|x,y,zarebinaryintegers,andxisthesumofyandz\right\}.$

Take w to be the string,

$1^p=1^p+0.$Then,

Let,$w=xyz$be a partition of W with$\left|xy\right|⩽pand\left|y\right|>0$

Note that$y=1^{k}forsome1⩽k⩽p$ and that $1^p=1^p+0.$is contained fully in Z.

Thus,

$x{y}^{2}zis{1}^{p+k}=1^k+0,$

Which is not in the language, contradicting the pumping lemma.

Thus, ADD is not regular.