Theory of Computation, Regular language

Question

Need help , to identify the regular languages

 

Comments

Only (A) is regular.

For (A), you can write, set $A$ as $\{1y, 11y,111y,…. \}$ where $y \in \{0+1\}^*$ and $y$ should contain at least $k$ $1s$ for every $k.$

So, $1y$ means $11,110,101,111,1001,1010,1100,1110,1101,1111,...$

$11y$ is concatenated by $1$ and elements $1y$ so elements $11y$ are $\{1111,110101,...\}$

Similarly for $111y,1111y,….$

Now, elements $1y$ starts with $1$ and having “at least” two $1s,$ It means elements $11y,111y,...$ are nothing but the some elements which are represented by $1y$ 

If we try to represent elements $1y$ in the form of regular expression then we should have to start with $1$ and then make zero or more than zero number of $0s$ then $1$ to make at least two $1s$ and then any number of $0s$ and $1s$. So, we can write in elements $1y$ in the form of regular expression as $10^*1(0+1)^*$

So, Regular Expression for set $A$ will be $10^*1(0+1)^*$ and hence, it is regular set.

Set $B$ is not regular set and we can prove it by pumping lemma.

Let, $B$ be a regular set and consider an element of set $B$ as $z = 1^p 001^p$ such that $|z| \geq p$ (p (pumping length) is a minimum number of states in the FSM for set B)

Now $\exists v,w,x$ such that $z = vwx= 1^{a}1^b 1^{p-a-b} 00 1^p$ where $v = 1^{a}, w=1^b, x=1^{p-a-b}001^{p}$ and $|vw| \leq p$ and $|w| \geq 1$ for all $i \geq 0$ [$p-a-b \geq 0 \implies a+b \leq p$] and $a,b \geq 0$

Now, according to pumping lemma, $\forall i \geq 0,$ $vw^ix$ should also be in $B$ .

But for $i=0,$ $z= vw^0 x = 1^{a} 1^{p-a-b}001^p = 1^{p-b}001^p$, Now here we can’t write $z$ in the form of $1^k y$ where $y \in \{0+1\}^*$ and $y$ is having at most $k$ $1s$ for every $k$ because for $b \geq 0, p-b \leq p$ Hence, $B$ is not a regular set. 

Puming Lemma 

---

Thanks for the explanation.

---

 

 (b.) → for proving B to be not regular,

               by  Myhill – Nerode Theorem,

 As,  B = { 1^ky | y belongs to (0+1)* and  y consists of at max k 1’s }

     Consider, S = { 1, 11, 111, … 1^k , 1^k+1 , .. }

         Now, take  two pairs of set S to prove that they are distinguishable  i.e, → 1^k , 1^k+1

        and,  z = { all strings consisting at most k 1’s  \\ k >=1}

  ---     As , (1^k+1)(z) →   { 1^k+1.( all strings consisting  k  1’s )  \\ k >=1 }

{ which is accepted by (B) }  

           and, (1^k)(z)  → { 1^k.( all strings consisting  k  1’s ) \\ k >=1 ) 

   VIOLATING CONDITION  – (  As, by def. of B, string y can’t have more than k 1’s)

  {  which is not accepted by (B) for every string of z }

          As, by def. of Myhill- Nerode Theorem,

there are infinite distinguishable equivalence strings { corresponding to elements in S }

results in  NOT REGULAR  nature of  B.

BUT<> using the same process I can prove A to be NOT regular,

can someonte tell me where I AM WRONG. ?

---

why did you consider two different sets S and z ? It should be a single set i.e. $\Sigma^*,$ right ?

---

why you think S and Z to be  single set  ( sigma* ) ?