Question

Question: Let $\mathit{\Sigma }\mathbf{=}\left\{1,\#\right\}$and let

$\mathit{Y}\mathbf{=}\left\{w|w=x_1\#x_2\#···\#x_{k}fork⩾0,each{x}_i\in 1*,and{x}_i\ne x_{j}fori\ne j\right\}.$

Prove that Y is not regular.

Short answer

Answer:The given language is not regular language is proved by pumping lemma

Step-by-step solution

Pumping lemma for regular language.

Here the pumping lemma is used to find the language is regular language or not.

a. Assume B is regular language and their L is 0s and 1s. where, Z is belongs to L.

$$\begin{gathered} \left|z\right|⩾n \\ z=uvwxy \\ \left|v\right|⩾1 \end{gathered}$$

Here at least 1 is not null.

b. Find a suitable k so that so L is not regular language.

$$\begin{gathered} L=\left\{a^n{b}^n{c}^n\right|n⩾0\} \\ z=uvwxy, \\ z=a^n{b}^n{c}^n\{n=1,z=abc\left\} \\ \right|z|=3n>n \end{gathered}$$

If we equate both z then we get,

$$\begin{gathered} uvwxy=a^n{b}^n{c}^n \\ \left|vx\right|⩾1,\{n⩾|vx|⩾1\} \end{gathered}$$

Then after that,

Let v or x is a part of -

$$\begin{gathered} \left(a^i{b}^j\right)or\left(b^i{c}^j\right) \\ v=\left(a^i{b}^j\right) \\ {v}^2=\left(a^i{b}^j\right)\left(b^i{c}^j\right) \\ u{v}^{2}w{x}^{2}y=a^m{b}^m{c}^m \end{gathered}$$

From this equation, it is proof that

$u{v}^{2}w{x}^{2}y\notin L$

Therefore,L is not regular language.

Regular language or not proved by pumping lemma.

Here ,$\Sigma =\left\{1,\#\right\}$, This language is not regular language.

$Y=\left\{w|w=x_1\#x_2\#···\#x_{k}fork⩾0,each{x}_i\in 1*,and{x}_i\ne x_{j}fori\ne j\right\}.$

Suppose Y is regular. Let be the pumping length given by the pumping lemma.

Let,$s=1^p\#1^{p+1}\#···\#{12}^p$ .

Because $s\in Yand\left|s\right|⩾p$, by the pumping lemma we can split into three pieces

$s=xyzsuchthatfori⩾0xyiz\in Y.$

Becauserole="math" localid="1660622961343" $\left|xy\right|⩽pand\left|y\right|⩾0$ by the pumping lemma, y must consist of between one and p ones. The string $\left|xy\right|$would generate between $p+1and2p1s$before the first #. In each case, $xi=xjfori\ne j.$

This violates the pumping lemma, therefore Y is not regular.